A BinarySearchTree is a particular binary tree wherein each node, u, also stores a data value, u.x, from some total order. The data values in a binary search tree obey the property: For a node, u, every data value stored in the subtree rooted at u.left is less than u.x and every data value stored in the subtree rooted at u.right is greater than u.x (see Fig.1).

The binary search tree property is useful because we can use it to quickly locate a value, x, in a binary search tree. We start the search for x at the root, r. When we examine a node, u, there are three cases:

1. If x < u.x, then we move to u.left.
2. If x > u.x, then we move to u.right.
3. If x = u.x, then we have found the node, u, containing x.

We terminate the search when case 3 occurs or when u is a null value. So, we have either found x or we can conclude that x does not exist in the binary search tree (see Fig.2).

Two examples of searches in a binary search tree are illustrated in figure 5. As the second example shows, even when we don't find x in the tree, we can still gain valuable information. If we look at the last node, u, at which Case 1 occured, we see that u.x is the smallest value in the tree that is greater than x. Similarly, the last node at which Case 2 occured contains the largest value that is smaller than x. So, by tracking the last node, z, at which Case 1 occurs, a BinarySearchTree can implement the find(x) operation that returns the smallest value stored in the tree that is greater than or equal to x (see Fig.4).

To add a new value, x, to a BinarySearchTree, we first need to search for x. If x is found, then there is no need to insert it. Otherwise, we store x at a leaf child of the last node, p, encountered during the search for x. Whether the new node is the left or right child of p is dependent on the result of comparing x and p.x (see Fig.6). The most time-consuming of this process is the initial search for x which takes an amount of time proportional to the height of the newly added node, u. In the worst case, this is equal to the height of the tree.

Deleting a value stored in a node, u, of a BinarySearchTree is a little more difficult. If u is a leaf, then we simply detach u from its parent. If u only has one child, then we can splice u from the tree and have u.parent adopt u's child(see fig.7).

When u has two children things become more complicated. Generally the most simple solution is to find a node, w, that has less than two children and such that w.x can replace u.x. In order to maintain the binary search tree property, the value w.x should be close to the value of u.x. As an example, selecting w is straightforward; it is the smallest value in the subtree rooted at u.right and can be removed as it has no left child (see Fig.8).

The find(x), add(x), and remove(x) operations in a BinarySearchTree each involve following a path from the root of the tree to some node in the tree. Without knowing the shape of the tree it is difficult to predict the length of the path, other than that it is less than n, the number of nodes in the tree. The following theorem summarizes the performance of BinarySearchTree data structure:

BinarySearchTree implements the SSet interface and supports the operations add(x), find(x), and remove(x) in O(n) time per operation.

This theorem compares badly with Theorem SkipSSet.1, which shows that the SkiplistSSet structure can implement the SSet interface with O(logn) expected time per operation. The main issue with the BinarySearchTree structure is that it can become unbalanced. Instead of looking like the tree in figure 1, it can easily resemble a long chain of n nodes, with all but the last having one child.

There are several ways of dealing with ubalanced binary search trees, which lead to data structures with O(logn) time operations. In the next section we see how O(logn) expected time operations can be achieved with randomisation. In the section Scapegoat Trees we see how O(logn) amortized time operations can be achieved with partial rebuilding operations. In the section Red-Black Trees we see how O(logn) worst-case time operations can be achieved by simulating a non-binary tree where nodes can have up to four children.