The Power of Random Priorities

As I noted earlier, when we insert values in random order into a BST, the BST will likely be well-balanced. I’ll call this data structure a randomized BST.

I’ll now demonstrate intuitively why randomized treaps should be as well-balanced as randomized BSTs. The key is that the two data structures share an attribute, which is that all the values have equal odds of landing at any particular spot within the tree. Here’s what I mean.

Say that we’re inserting the values 1 through 100 into a regular BST. When we insert the values in perfectly ascending order, we are dictating that the 1 becomes the root of the tree. This already causes a severe imbalance since the root can now only have right descendants because it’s impossible for the 1, the smallest of our values, to have a left child.

But with a randomized BST, each and every value has an equal chance of becoming the tree’s root. That is, each value has an equal chance of being picked first, and whichever value is picked first becomes the root.

This alone already helps achieve balance because even though having a 1 as the root is a terrible outcome, there’s only a 1 in 100 chance that this will happen. There are greater odds that a more reasonable number will be chosen as the root.

The same goes for randomization at every level of the tree. Regarding the tree’s second level, for example, there are some bad numbers that could be chosen, but odds are that this won’t happen.

So, the balance of a randomized BST is based on the fact that each and every value has an equal chance of landing at any particular level within the tree.

The same goes for randomized treaps: the level where any node lands is completely based on its priority. And because the priorities are random, any value can land at any level.

For example, whichever node has the smallest priority will become the treap’s root since otherwise we’d be violating the Heap Rule. And with a randomized treap, each value has an equal shot at being assigned the smallest priority. It might be a bad thing if our smallest value (such as the letter A) also happens to get assigned the smallest priority, but the odds are that this won’t happen.

It emerges that both a BST and a randomized treap share the characteristic that all values have the same odds of landing at any particular level within the tree. Because of this, the two data structures have the same level of balance.

The Expected Height of a Treap

Speaking of treap balance, how well-balanced can we expect a treap to be? You discovered in the previous chapter that if a red-black tree has N values, it will have a height of O(log N) if we express the height using Big O notation. Furthermore, it’s guaranteed that a red-black tree’s height will not exceed 2 log N. The Red-Black Rules ensure that a greater height is simply not possible.

Believe it or not, a randomized treap also has an expected height of O(log N), making a treap a great competitor to a red-black tree.

However, a treap does not have the same O(log N) guarantee that a red-black tree does. It is possible, albeit highly unlikely, for a treap to have a much greater height. Imagine that we inserted values in perfect order, and the computer happened to randomly choose priorities that were also in perfect order. We’d end up with the dreaded linked list! The good news, though, is that this scenario is extremely rare.

I’ve run many tests building treaps of various sizes (from 50 up to 5,000,000 nodes), and have found that the height of each treap has always come out to be between 2 log N and 3 log N. Again, it’s theoretically possible to have a taller treap, but such a likelihood is very small.

It turns out that by using a simple randomized algorithm, treaps perform virtually as well as red-black trees. And not only that, treaps achieve this performance with so much less complexity than the byzantine set of algorithms that power red-black trees.

Yes, red-black trees are never taller than 2 log N, and treaps’ heights are usually around 2.5 log N. However, it may be a worthwhile trade-off to have slightly higher trees and thereby gain a considerable amount of code simplicity. More simplicity generally means fewer bugs. And the difference between 2.5 log N and 2 log N may be considered negligible for many applications.

However, if you need a guarantee that your tree doesn’t exceed a height of 2 log N, then you may opt for the red-black tree rather than the treap. Again, it’s all about trade-offs.

In any case, treaps are a great example of how randomization can achieve simplicity. It’s also a perfect example of a data structure that is powered by randomization, or what some call a randomized data structure.

Code Implementation: Treap Insertion

Let’s look at the Python code for treaps. To start, here’s the code for a treap node:

Like other tree nodes we’ve worked with, this Node has value, left_child, right_child, and parent attributes. However, what makes treap nodes unique is that they also have a priority attribute.

In a randomized treap, this priority will simply be a random number. In our implementation, we use the random() method to generate this number, which will be a random float between 0 and 1. That is, it’ll be something like 0.2677900713452904 or 0.9337348703962393.

Mainly for testing purposes, I built in the ability for the creator of a node to assign a priority to that node. A random priority will only be generated if no other priority has been explicitly assigned. This also allows our treap to be used in its classical variant, where the priorities are not random. And so, our code can be used to serve either as a randomized treap or a classic treap.

Now that we have our treap Node in place, here is the first section of code for our actual Treap class:

This is a lot of code, but much of it is code we’ve encountered before. Let’s walk through all of the code in order.

The Treap’s constructor creates the self.root variable, which is used to keep track of the treap’s root at all times.

The bulk of the remaining code consists of several methods that I copied from our red-black tree implementation in the previous chapter in . These include rotate_counterclockwise, rotate_clockwise, insert, and smaller helper methods is_a_left_child and is_a_right_child.

The main difference compared to our red-black tree code is the implementation of the insert_fix method. The insert_fix algorithm here is:

We run a loop as long as the inserted node’s priority is less than its parent’s priority. In the loop, we continue to rotate the inserted node with its parent. The rotation will be clockwise if the inserted node is a left child and counterclockwise if the inserted node is a right child. Once the inserted node is situated so that its priority is greater than (or equal to) its parent’s priority, we’re done.

It’s worth taking a peek back at the red-black tree’s insert_fix code in to appreciate how much simpler the treap algorithm is. It’s pretty incredible what randomization can do.