Showing posts with label BinarySearchTree. Show all posts
Showing posts with label BinarySearchTree. Show all posts

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




Read more