Introduction to Random Binary Search Trees

Here, we present a binary search tree structure that uses randomization to achieve $O(\log n)$ expected time for all operations.

Consider the two binary search trees shown below in figure, each of which has $n = 15$ nodes.

The one on the left is a list and the other is a perfectly balanced binary search tree. The one on the left has a height of $n − 1 = 14$ and the one on the right has a height of three.

Imagine how these two trees could have been constructed. The one on the left occurs if we start with an empty BinarySearchTree and add the sequence

$$\left< 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14 \right>$$

No other sequence of additions will create this tree (as you can prove by induction on n). On the other hand, the tree on the right can be created by the sequence

$$\left< 7,3,11,1,5,9,13,0,2,4,6,8,10,12,14 \right>$$

Other sequences work as well, including

$$\left< 7,3,1,5,0,2,4,6,11,9,13,8,10,12,14 \right>$$

and

$$\left< 7,3,1,11,5,0,2,4,6,9,13,8,10,12,14 \right>$$

In fact, there are $21,964,800$ addition sequences that generate the tree on the right and only one that generates the tree on the left.

The above example gives some anecdotal evidence that, if we choose a random permutation of $0,...,14$, and add it into a binary search tree, then we are more likely to get a very balanced tree (the right side of the above illustration, than we are to get a very unbalanced tree (the left side of the above illustration).

We can formalize this notion by studying random binary search trees. A random binary search tree of size n is obtained in the following way: Take a random permutation, $x_{0},...,x_{n−1}$, of the integers $0,...,n − 1$ and add its elements, one by one, into a BinarySearchTree. By random permutation we mean that each of the possible $n!$ permutations (orderings) of $0,...,n−1$ is equally likely, so that the probability of obtaining any particular permutation is $1/n!$.

Note that the values $0,...,n−1$ could be replaced by any ordered set of n elements without changing any of the properties of the random binary search tree. The element $x \in \{{0,...,n − 1}\}$ is simply standing in for the element of rank x in an ordered set of size n.

Before we can present our main result about random binary search trees, we must take some time for a short digression to discuss a type of number that comes up frequently when studying randomized structures. For a non-negative integer, $k$ ...