Understanding Binary Search Trees With Algorithm

Binary Search Tree is as data structure which allow us to store the data in a binary tree. In a binary tree each node has a maximum of two children.  Binary search tree differs just a little bit from the binary tree.

1. Each node of the left subtree are less than the root node
2. Each node of the  right subtree are greater than the root  node
3. The subtree of each node also follow the above properties

The basic operations that can be performed on BST are Search, Insert, Delete, Minimum, Maximum, Predecessor, Successor.  The basic operations takes time O(logn) on average case and O(n) on worst case.

Searching

Searching in BST is fairly simple as we know that the left subtrees will contain only the elements that are less than root  element and the right subtree will contain the elements that are greater than root element. First we compare the given key with the root if the key matches we return the root, if the key is greater than root we recur to right subtree of the root node. otherwise recur for the left subtree

TREE-SEARCH(x,k)

1. if x = NIL or k = key[x]

2.    then return x

3. if k < key[x]

4.    then return TREE-SEARCH(left[x],k)

5.    else return TREE-SEARCH(right[x],k)

Insertion

To insert a new node in the tree, its key is first compared with that of the root. If its key is less than the root’s, it is then compared with the key of the root’s left child. If its key is greater, it is compared with the root’s right child. This process continues, until the new node is compared with a leaf node, and then it is added as this node’s right or left child, depending on its key: if the key is less than the leaf’s key, then it is inserted as the leaf’s left child, otherwise as the leaf’s right child.

TREE-INSERT(T,z)

1. y ⟵ NIL

2. x ⟵ root[T]

3. while x ≠ NIL

4. do y ⟵ x

5.    if key[z] < key[x]

6.       then x ⟵ left[x]

7.       else x ⟵ right[x]

8. p[z] ⟵ y

9. if y = NIL

10. then root[T] ⟵ z

11. else if key[z] < key[y]

12. then left[y] ⟵ z

13. else right[y] ⟵ z

Deletion

To delete a given node z from BST we need a pointer to z. The procedures follows like this: if z has no children we modify its parent to replace z with NIL as its child. If the node has one child, we splice out z by making a new link between its child and its parent. Finally, if the the node has two children, we splice out z’s successor y, which has no left child and replace z’s key and data with y’s key and data. 

TREE-DELETE(T,z)

1. if left[z] = NIL or right[z] = NIL

2. then y ⟵ z

3. else y ⟵ TREE-SUCCESSOR(z)

4. if left[y] ≠ NIL

5. then x ⟵ left[y]

6. else x ⟵ right[y]

7. if x ≠ NIL

8. then p[x] ⟵ p[y]

9. if p[y] = NIL

10. then root[T] ⟵ x

11. else if y = left[p[y]]

12.      then left[p[y]] ⟵ x

13.      else right[p[y]] ⟵ x

14. if y ≠ z

15. then key[z] ⟵ key[y]

16. return y

Successor

If all the keys are distinct, the successor of a node x is the node with the smallest key greater than key[x]. 

TREE-SUCCESSOR(x)

1. if right[x] ≠ NIL

2. then return TREE-MINIMUM(right[x])

3. y ⟵ p[x]

4. while y ≠ NIL and x = right[y]

5. do x ⟵ y

6.         y ⟵ p[y]

7. return y

Minimum

In BST the minimum can be found by following the left child from the root node until the NIL is encountered.

TREE-MINIMUM(x)

1. while left[x] ≠ NIL

2. x ⟵ left[x]

3. return x

Maximum

In BST the maximum can be found by following the right child from the root node until the NIL is encountered.

TREE-MAXIMUM(x)

1. while right[x] ≠ NIL

2. x ⟵ right[x]

3. return x