Self-Balancing Treaps in Action

Because a node’s priority is randomly generated, the number of rotations that occur upon treap insertion is determined by randomization. For instance, if our V node from the previous example happened to have been randomly assigned the priority of 100, we wouldn’t have performed any rotations at all. This is because a node with a priority of 100 indeed belongs at the bottom of the treap. And if the V received the priority of 1, we would have rotated the V until it became the root of the treap.

The crazy thing is that this randomization allows treaps to achieve a level of balance that is similar to red-black trees. While red-black trees have a rotation scheme that is complex and follows a precise set of rules, a treap’s random rotations achieve a similar result!

Let’s look at an example of a treap performing this balancing act. Let’s say that we’re going to insert values into a treap in order. We know that for a regular BST, inserting values in order is a death knell, as the tree becomes a super-long linked list. But let’s see what happens with a treap when we insert the values A through G in perfectly ascending order.

We’ll begin by inserting an A. Let’s say that this node’s randomly generated priority is 75:

Next, we’ll insert B. The computer spins its internal die and decides that the B’s priority should be 41.

In a regular BST, the B would become the A’s right child. However, in a treap, this violates the Heap Rule since the child’s priority 41 is less than the parent’s priority of 75. And so, we rotate the A and B:

Next up, we have a C, and its randomized priority happens to be 52. As such, we get to make C the B’s right child, and no rotations are necessary:

We then insert a D, and the computer decides to assign it a priority of 16. This is the minimum priority of the entire treap so far, so we rotate the D upward until it becomes the treap’s root:

Our next node has the value of E and a priority of 80. No rotations are necessary:

The letter F is up next, and its priority is 50. A single rotation is in order:

Lastly, we insert the G. The computer grants it a priority of 89, so we can simply insert it like this:

Amazingly, although we inserted values in perfect order, the treap rotations arranged them so that our treap is fully balanced.

Of course, this example was completely contrived since I had the liberty to choose the computer’s “random” priorities. However, it does turn out that treaps in general have a high probability of being well-balanced.

Let’s dig a little further to see why.