BST - Binary Search Tree

BST - Binary Search Tree

  12:31 PM    mayuravaani

---

For any node x,
    the keys in left sub tree of x are at most x.key and
    the keys in right sub tree of x are at least x.key.

Here the fisrt is BST but in the second 11 should not be in the left side of 10.

Binary Search Tree Property
   Let x be a node in BST.
   Let y be a node in left sub tree of x and
   Let z be a node in the right sub tree of y then
   y.key <= x.key and z.key > = x,key
Binary search average case-> O(lg n)
                       worst case -> O(n)
                       best case -> O(1)

Inorder tree walk
left --- root --- right

INORDER-TREE-WALK(x)
if(x ≠  NIL)
       INORDER-TREE-WALK(x.left)
       print x.key
       INORDER-TREE-WALK(x.right)

Preorder tree walk
root --- left --- right

PREORDER-TREE-WALK(x)
if(x ≠  NIL)
       print x.key
       PREORDER-TREE-WALK(x.left)
       PREORDER-TREE-WALK(x.right)

Postorder tree walk
left --- right --- root

POSTORDER-TREE-WALK(x)
if(x ≠  NILL)
       POSTORDER-TREE-WALK(x.left)
       POSTORDER-TREE-WALK(x.right)
       print x.key

INORDER TRAVERSAL
P, H, A, K, C, T, Q, M, R

PREORDER TRAVERSAL
C, H, P, K, A, M, T, Q,  R

POSTORDER TRAVERSAL
P,A, K, H, Q, T, R, M, C

If x is root of an n-node subtree, then the call INORDER-TREE-WALK(x) takes time O(n)

Searching

x- current node , k- search key

TREE-SEARCH(x, k)
if ( x == NIL or k == x.key)
       return x
if( k < x.key)
       return TREE-SEARCH(x.left, k)
else
       return TREE-SEARCH(x.right, k)

ITERATIVE TREE-SEARCH(x, k)
while( x ≠ NIL or k ≠ x.key)
         if( k < x.key)
                x = x.left
          else
                 x = x.right           return x

The running time of tree-search is O(h),  where h is height of tree.

Minimum


TREE-MINIMUM(x)
while(x.left ≠ NIL)
      x = x.left
return x

Maximum
     
TREE-MAXIMUM(x)
while(x.right ≠ NIL)
      x  =  x.right
return x

The running time of minimum and maximum is O(h),  where h is height of tree.

Successor

TREE-SUCCESSOR(x)
if(x.right ≠ NIL)
      return TREE-MINIMUM(x.right)
y = x.p
while( y  ≠  NIL and x == y.right)
       x = y
       y = y.p
return y

Maximum
   
TREE-PREDECESSOR(x)
if(x.left  ≠  NIL)
       return TREE-PREDECESSOR(x.left)
y = x.p
while( y  ≠  NIL and x == y.left)
        x = y
        y = y.p
return y

Simply, Inorder successor of the node x is the smallest value node of its right subtree and the inorder predecessor of the node x is the largest value of its right subtree.

INORDER SUCCESSOR OF C -> T

INORDER PREDECESSOR OF C -> K

Insertion

The new element will be inserted by considering left and right subtree values. 
T- binary tree, z-new node

TREE-INSERT(T, z)
y = NIL
x = T.root
while( x ≠ NIL)
       y = x
       if( z.key < x.key)
              x = x.left
        else
              x = x.right
z.p = y
if( y == NIL)
    T.root = z
else if( z.key < y.key)
     y.left = z
else
     y.right = z

Deletion

Deleting a node z from a binary search tree T has 3 cases:
If z has no children, then simply remove it by replacing with NIL
If z has only one child, then remove the z by replacing the child node of z with the z.
If z has two children then find the successor(y) and replace it with z. Original right and left subtrees of z becomes y's new subtrees.

TRANSPLANT(T, u, v)
if (u.p == NIL)
     T.root = v
else if (u == u.p.left)
      p.p.left = c
else if (u == u.p.right)
      u.p.right == v
if (v ≠ NIL)
      v.p = u.p

TREE-DELETE(T, z)
if (z.left == NIL)
       TRANSPLANT(T, z, z.right)
else if(z.right == NIL)
       TRANSPLANT(T, z, z.left)
else
       y = TREE-MINIMUM(z.right)
       if (y.p ≠ z)
             TRANSPLANT(T, y, y.right)
              y.right = z.right
              y.right.p = y
       TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y

Randomly build binary search tree