Binary Search Tree

Binary Search Tree

Definition

Binary search tree (BST), also known as sorted binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node.The BST data structure is the basis for a number of highly efficient sorting and searching algorithms, and it can be used to construct more abstract data structures including sets, multisets, and associative arrays.

BST Rules

For a node x in of a BST T,
–the left subtree of x contains elements that are smaller than those stored in x,
–the right subtree of x contains all elements that are greater than those stored in x,

Binary Search Tree Operations

Search() : find key in the BST 

Whenever an element is to be searched, start searching from the root node. Then if the data is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree. Follow the same algorithm for each node.

Insert() : insert new key into BST 

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

Remove() : remove key from BST

•There are 3 cases which should be considered:
If the key is in a leaf, just delete that node
If the key is in a node which has one child, delete that node and connect its child to its parent
If the key is in a node which has two children, find the right most child of its left sub tree (node P), replace its key with P’s key and remove P recursively. (or alternately you can choose the left most child of its right sub tree)





Comments

Post a Comment

Popular posts from this blog

AVL Tree And B Tree

Image
AVL Tree An AVL tree is a subtype of binary search tree. Named after it's inventors Adelson, Velskii and Landis, AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees. ~  Height of a node: -The height of an empty subtree is 0. -The height of a leaf is 1. -The height of an internal node is the maximum height of its children plus 1. ~ Balance factor: -The difference height of its LEFT subtree and its RIGHT subtree . The balance factor of all nodes in AVL tree should be at most 1. AVL Tree Example Right Rotation Left Rotation AVL Insertion Process If there is an imbalance in left child of right subtree, then you perform a left-right rotation. If there is an imbalance in left child of left subtree, then you perform a right rotation. If there is an imbalance in right child of right subtree, then you perform a left rotation. If there is an imbalance in right chi...
Read more

Linked List

Image
Linked List Linked List Definition A linked list is a dynamic data structure where a  node  is made up of two items - the data and a reference (or pointer) which points to the next node. A linked list is a collection of nodes where each node is connected to the next node through a pointer. The first node is called a  head  and if the list is empty then the value of head is NULL.For a real-world analogy of linked list, you can think of conga line, a special kind of dance in which people line up behind each other with hands on shoulders of the person in front. A Simple Linked List Circular Single Linked list In Circular Single Linked List, last node contains a pointer to the first node, We can have a circular singly linked list as well as a circular doubly linked list. There is no storing of NULL values in the list Implementation Insertion A node can be added in three ways: Insertion in an empty list Insertion at the beginning of the li...
Read more

Rangkuman Before UTS

Image
Linked List Linked List Definition A linked list is a dynamic data structure where a  node  is made up of two items - the data and a reference (or pointer) which points to the next node. A linked list is a collection of nodes where each node is connected to the next node through a pointer. The first node is called a  head  and if the list is empty then the value of head is NULL.For a real-world analogy of linked list, you can think of conga line, a special kind of dance in which people line up behind each other with hands on shoulders of the person in front. A Simple Linked List Circular Single Linked list In Circular Single Linked List, last node contains a pointer to the first node, We can have a circular singly linked list as well as a circular doubly linked list. There is no storing of NULL values in the list Implementation Insertion A node can be added in three ways: Insertion in an empty list Insertion at the beginning of the li...
Read more