Treap: A Randomised Binary Search Tree

In this section we study a binary search tree structure that uses randomisation to achieve O(logn) expected time for all operations.

If we scrutinize the two binary search trees in figure 1, each of which has n=15 nodes. The left-hand tree is in fact a list with a height of n-1=14 and the right-hand tree is a perfectly balanced binary search tree with a height of 3.

If we consider how these two trees could have been constructed, the one on the left can only occur if we start with an empty BinarySearchTree and add the sequence {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}. No other sequence of additions will create this tree (which we can prove by induction on n). However, the right-hand tree can be created by multiple sequences such as;

• {7,3,11,1,5,9,13,0,2,4,6,8,10,12,14}
• {7,3,1,5,0,2,4,6,11,9,13,8,10,12,14}
• {7,3,1,11,5,0,2,4,6,9,13,8,10,12,14}

In actuality there are 21,964,800 addition sequences that will generate the right-hand tree and only one that generates the left-hand tree.

The above example is anecdotal evidence that given a random permutation of 0,...,14, added into a binary search tree, then we are more likely to get a balanced tree than we are to get an unbalanced tree.

We can formalise this by studying random binary search trees. We can obtain a random binary search tree of size n in this way: Take a random permutation, x₀,...,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 likelym so that the probability of any specific permutation is 1/n!.

It should be noted that the values 0,...,n-1 could be any ordered set of n elements without changing the properties of the random binary search tree. The element x∈{0,...,n-1} is just a stand in for the element of rank x in an ordered set of size n.

When studying randomised structures a type of number appears frequently and should be addressed. For a non-negative integer, k, the k-th harmonic number, H_k, is defined as H_k=1+1/2+1/3+...+1/k. The harmonic number H_k has no simple closed form, but it is very closely related to the natural logarithm of k. In particular ln(k)k≤ln(k)+1.

If you have studied calculus you may notice that this is due to the the integral . Bearing in mind that an integral can be interpreted as the area between a curve and the x-axis, the value of H_k can be lower-bounded by the integrel and upper-bounded by (see Fig.2).