Binary Search Trees

Fast support of all dictionary operations is realized by binary search trees. A binary tree is a rooted tree where each node contains at most two children. Each child can be identified as either a left or right child. As shown in Figure , a binary tree can be implemented where each node has left and right pointer fields, an (optional) parent pointer, and a data field.  

 
Figure: Relationships in a binary search tree  

A binary search tree labels each node in a binary tree with a single key such that for any node labeled x, all nodes in the left subtree of x have keys < x while all nodes in the right subtree of x have keys > x. The search tree labeling enables us to find where any key is. Start at the root. If it does not contain the key we are searching for, proceed either left or right depending upon whether what we want occurs before or after the root key. This algorithm works because both the left and right subtrees of a binary search tree are binary search trees; the recursive structure yields a recursive algorithm. Accordingly, the dictionary Query operation can be performed in O(h) time, where h is the height of the tree.

BinaryTreeQuery(x, k)

		 if   

				    then return x

		 if (k < key[x])

				then return BinaryTreeQuery(left[x],k)

				else return BinaryTreeQuery(right[x],k)

To insert a new item x with key k into a binary search tree T, it is important to place it where it can be later be found. There is only one such location in any binary search tree, namely by replacing the nil pointer found in T after an unsuccessful query for k. Replacing this nil pointer with a pointer to x is a simple, constant-time operation after the search has been performed in O(h) time.  

Deletion is somewhat more tricky than insertion, because the node selected to die may not be a leaf. Leaf nodes may be deleted without mercy, by clearing the pointer to the given node. However, internal nodes have children that must remain accessible after the deletion. By restructuring or relabeling the tree, however, the item to delete can always be made into a leaf and then removed. Details appear in any data structures text.  

When implemented using binary search trees, all three dictionary operations take O(h) time, where h is the height of the tree. The smallest height we could hope for occurs when the tree is perfectly balanced, where . In fact, if we insert the keys in random order, with high probability the tree will have height. However, if we get unlucky with our order of insertion or deletion, we can end up with a linear-height tree in the worst case. The worst case is a serious potential problem. Indeed, it occurs whenever the keys are inserted in sorted order.

To avoid such worst-case performance, more sophisticated balanced binary search tree data structures have been developed that guarantee the height of the tree always to be . Therefore, all dictionary operations (insert, delete, query) take time each. Implementations of such balanced tree data structures as red-black trees are discussed in Section .  

From an algorithm design viewpoint, it is most important to know that these trees exist and that they can be used as black boxes to provide an efficient dictionary implementation. When figuring the costs of dictionary operations for algorithm analysis, assume the worst-case complexities of balanced binary trees to be a fair measure.