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

xif (

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.

Mon Jun 2 23:33:50 EDT 1997