Friday, August 7, 2015

Binary Search Tree

The search tree data structure supports many dynamic set operations:
               -  SEARCH
               - MINIMUM
               - MAXIMUM
               - PREDECESSOR
               - SUCCESSOR
               - INSERT
               - DELETE
and also can use search tree as "Dictionary" and "priority queue".

Binary Search tree
    We can represent such a tree by linked data structure in which each node is an object.
Each node contains attributes left, right, parent and element.



Figure: Binary search tree. 
       For any node x, the key in the left subtree of x are at most x.key, and the key in the right subtree of x are at least x.key. Different binary search trees can represent the same set of values. 
The worst-case running time for most search-tree operation is proportional to the height of the tree.
(a) A binary search tree on 9 nodes with height 3.
(b) A binary search tree on 9 nodes with height 6.

      There for, "Tree (a) is more efficient than Tree (b)".
    

Binary search tree property:
Let x be a node in a binary search tree. 
    - If y is a node in the left subtree of x, then y.key <= x.key.
    - If i is a node in the right subtree of x, then y.key >= x.key.

EX:

The binary-search-tree property allows us to print out all the key in a binary search tree in sorted order by a simple recursive algorithm, called an inorder tree walk.
To use the following procedure to print all the elements in a binary search tree T, we call INORDER-TREE-WALK(T.root).

TREE-WALK(x)
1    if x != NIL
2          TREE-WALK(x.left)
3          print x.key
4          TREE-WALK(x.right)

Here  Ө(n) time to walk an n nodes binary search tree.

Querying a binary search tree
Searching:
           Given a pointer to the root of the tree and a key k, TREE-SEARCH returns a pointer to a node with key k if one exists, otherwise, it returns NIL.

TREE-SEARCH (x , k)
1      if x == NIL or k == x.key
2            return x
3      if k < x.key
4           return TREE-SEARCH (x.left , k)
5      else return TREE-SEARCH (x.right , k)

The running time of TREE-SEARCH is O(h), where h is the height of the tree.
We can rewrite this procedure in an iterative fashion by "unrolling" the recursion into a while loop.

ITERATIVE-TREE-SEARCH (x , k)
1       while x != NIL and k != x.key
2              if k < x.key
3                     x = x.left
4              else x = x.right
5        return x

Minimum:
We can always find an element in a binary sear tree whose key is a minimum by following left child pointers from the root until we encounter a NIL.

TREE-MINIMUM (x)
1      while x.left != NIL
2             x = x.left
3       return x

Maximum:
We can always find an element in a binary sear tree whose key is a maximum by following right child pointers from the root until we encounter a NIL.

TREE-MAXIMUM (x)
1      while x.right != NIL
2             x = x.right
3       return x

the running time of both maximum and minimum is O(h).

Successor and predecessor:
Successor of a node x is the node with the smallest key greater than x.key.

TREE-SUCCESSOR (x)
1       if x.right != NIL
2              return  TREE-MAXIMUM (x.right)
3       y = x.p
4       while y != NIL and x == y.right 
5             x = y
6             y = y.p
7       return y

We break the code for TREE-SUCCESSOR into two cases.
       If the right subtree of node is nonempty, then the successor of x is just the leftmost node in x's right subtree, which is calling TREE-MINIMUM (x.right).
       On the other hand, if the right subtree of node x is empty and x has successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x.

Insertion and Deletion
Insertion:
To insert a new value v into a binary search tree T.
         take a node z for which,
          - z.key = v,
          - z.left = NIL,
          - z.right = NIL

TREE-INSERT(T,z)
1     y = NIL
2     x = T.root
3     while x != NIL
4            y = x
5            if z.key < x.key
6                      x = x.left
7            else    x = x.right
8     z.p = y
9     if y == NIL
10          T.root = y      // tree was empty
11   elseif  z.key < y.key
12           y.left = z
13   else  y.right = z




0 comments:

Post a Comment