Sections

Visualize
Tree operations

Algorithm
Visualization

Homepage

## Binary Search Trees

### Summary

Consider the problem to maintain a set of objects, each one identified by a key, during a sequence of query and update operations.

To be more specific, we want to design a data structure for a set which supports test of membership, insertion and removal. Sometimes such a dynamic set is called a dictionary.

In the following, we assume a total order on the set of key-values.

Search trees are data structures that support many dynamic-set operations including the following operations. (We use the parameter names S for sets, x for elements and k for key-values.)
 search(S,k) returns an element x in S such that key[x]=k, if such an element exists. Otherwise returns NULL. insert(S,x) augments S with x. delete(S,x) removes x from S (if it's contained in S). minimum(S) returns an element x of minimum key-value in S. maximum(S) returns an element x of maximum key-value in S. predecessor(S,x) returns an element which key-value is next larger than key[x] in the set of keys of S. successor(S,x) returns an element which key-value is next smaller than key[y] in the set of keys of S.
Basic operations on a binary search tree take time proportional to the height of a tree. For a complete binary tree with n nodes, such operations run in theta (ln(n)) worst-case time. If the tree is a linear chain of n nodes, however, the same operations take theta (n) time.

### Tree Data Structure

A binary search tree is organized, as the name suggests, in a binary tree, as shown below. Such a tree can be represented by a recursive data structure, in which each node is an object.

In addition to a key field, each node contains fields left and right, corresponding to the left and right subtrees at this node.

In a more formal description, a tree is either the empty tree NULL, or it's a node containing a key and the two subtrees:

datatype Tree = NULL | node of KeyType * Tree * Tree
Given a tree x = node(key,y,x) we call x the root of the tree and we call y and z its children.

The elements in a binary search tree are always organized in a way to satisfy the important 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 key[y] <= key[x]. If y is a node in the right subtree of x, then key[x] >= key[y].

### Tree Algorithms

In the following, we're only considering operations on a specific tree. Therefore, we omit the tree parameter for the operations. Also, we identify keys and elements assuming a one-to-one correspondence.

#### Search(k)

The search operations searches recursively for a key k. If the key x at the root is equal to k we can return the root node, otherwise the search continues in the appropriate subtree (k < x left subtree, x > k right subtree). In case the corresponding subtree doesn't exist (i.e. is a NULL tree), we abort the search unsuccessfully.

#### Insert(x)

The insert operation searches recursively for x. Thereby, the search path for x is identified. In case x is not found, we add x as a child of y the last node on that path.

#### Delete(x)

The delete operation searches recursively for x. Depending on the number of children of x we consider three cases:

In case x is a leaf node, i.e. it doesn't have any children, we can simply remove x.
In case only one child y is present at x we remove x by replacing it with y.

#### Example

The remaining case deals with the situation that both subtrees are present at x: At first, we locate the predecessor y, which is the largest element of the left subtree. Observe, that y has at most one child. Next, we swap the nodes x and y. Now, x has at most one child and we can remove it according to the first two cases.

### References

[1] Introduction To Algorithms, Cormen, Leiserson, Rivest, MIT Press, 1989

Henning Biermann, biermann@cs.nyu.edu
Revised: February 25, 1998