Treap Insertion

We’re now ready to see how treap insertions work. Like a red-black tree, treap insertion goes through two phases (as discussed in ). In the first phase, the new node is inserted in the same way a node is inserted into a regular BST, and in the second phase, the tree is “fixed” so that it doesn’t violate any of the rules.

Let’s insert the letter V into the treap shown at the end of the previous section. I mentioned earlier that with randomized treaps, a node’s priority is randomly generated. So, let’s say that the randomly generated priority is 22.

The First Phase

To begin the first phase of insertion, we first compare the V against the root’s value of M:

Because the value V is “greater” than the value M, it means that the V will be inserted somewhere among the V’s right descendants. So we focus on the M’s right child:

We compare the V to the Q. V is greater than Q, so we focus on the Q’s right child:

We compare the V to the Z. Because V is less than Z, we focus on the Z’s left child. However, the Z doesn’t have a left child, so we insert the V into the tree as the Z’s left child:

This concludes the first phase of insertion, and you’ll notice that it’s identical to regular BST insertion. However, you can also see that the Heap Rule has now been violated since the V’s priority of 22 is less than its parent’s priority of 80. We now need to fix this violation, so the second phase—which I call the “fixing phase”—begins.

The Fixing Phase

At the moment, the V’s priority is in conflict with the Z’s priority. To fix this, we rotate the V and the Z.

Treap rotations are completely identical to red-black tree rotations, and as you saw in the previous chapter, there are two types of rotations: clockwise and counterclockwise. When rotating two nodes (a child and parent), we perform a clockwise rotation when the child node is the left child of its parent, and a counterclockwise rotation when the child node is the right child of its parent. In this case, the V is the left child of the Z, so we perform a clockwise rotation:

By performing this rotation, we “fixed” the Heap Rule violation between the V and the Z since the V (whose priority is less than the Z) is now above the Z.

At the same time, we can be assured that our fix will not create a violation of the BST Rule since rotations never do. (We covered this in the last chapter, in ).

It turns out that rotations are a great tool for fixing Heap Rule violations since we can easily “bubble up” a node to its proper place in terms of priority, and not worry that we’ll accidentally violate the BST Rule.

Now, while we’ve fixed the Heap Rule violation between the V and Z, the V still violates the Heap Rule with regard to the Q. That is, the V’s priority of 22 is less than its parent’s priority of 54. As such, we now need to perform a rotation between the V and the Q. Because the V is the Q’s right child, we perform a counterclockwise rotation:

The V’s priority of 22 is greater than its parent’s priority of 16, so the Heap Rule has been restored. Our treap is now fixed, and our insertion is complete!