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.
Read more
- 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

