Treap Deletion

Deleting a node from a treap is also much simpler than it is with a red-black tree. The trick is that we can use rotations to move the node we’re deleting downward through the treap until it becomes a leaf node (that is, it has no children). Once this node becomes a leaf, we simply detach it from the treap.

Here’s the specific algorithm:

1. First, we search the tree for the node with the value that we intend to delete. We’ll call this node the node_to_delete.

2. If we find this node, we run a loop that lasts as long as the node_to_delete has children.

3. Within this loop, we rotate the node_to_delete with its child. If the node_to_delete happens to have two children, we rotate it with the child that has the smaller priority. (I’ll explain the reason for this shortly.) We continue to rotate the node_to_delete downward until it has no children, after which our loop ends.

4. We remove the node_to_delete from the treap. That is, if the node_to_delete is a left child, we declare that its parent’s left child is henceforth None, and if the node_to_delete is a right child, its parent’s right child will now be None. By doing this, we can no longer access the node_to_delete from the treap.

Treap Deletion in Action

Let’s get a visual of treap deletion so that the algorithm is abundantly clear. Say we want to delete the D node from the following treap:

Note that in this diagram, the priority of the D node is obscured. This was done because the D’s priority is completely irrelevant in the deletion algorithm. That is, you don’t ever need to look at the D’s priority to perform deletion.

To delete the node from the treap, first, we conduct a search to find the node. The search algorithm is the same algorithm for searching for a node within a classic BST. In this example, we find the D immediately since it happens to be the root node.

We then begin a loop that rotates the D downward through the treap. The D currently has two children. The B has a priority of 41, while the F has a priority of 50. As stated earlier, we choose to rotate the node_to_delete with the child with the smaller priority. This would be the B since 41 is less than 50. So, we rotate the D and the B in a clockwise fashion:

Let me pause here to explain why we chose to rotate the node_to_delete with the child with the smaller priority.

If we do the alternative, and rotate the node_to_delete with the child with the greater priority, we’d end up moving the F upward, like so:

This would put us in a position where the F is an ancestor of B. However, because F has a greater priority than B, this violates the Heap Rule!

When we rotate a node downward, we end up turning one of its children into the ancestor of the other child. By rotating the node with the child with the smaller priority, we ensure that the child with the smaller priority becomes the ancestor of the child with the greater priority.

Let’s go back to where we were when we did things correctly. Currently, the D has two children, C and F. Between the two children, F has the smaller priority, so we rotate the D with the F in good ol’ counterclockwise fashion:

The D’s two children are now C and E. The C’s priority is smaller than the E’s, so we rotate D and C clockwise, as shown in the .

The D now only has one child, E, so we rotate D and E:

The D is now a leaf node, so we can now safely remove it from the treap:

Poof! It’s gone.

Treap Deletion vs. BST Deletion

In Volume 1, Chapter 15, I covered how BST deletion works. I won’t rehash all the details here, but the algorithm is arguably more complex than the algorithm for treap deletion. In particular, the BST deletion algorithm performs different actions in different scenarios, such as when the node_to_delete has no children, one child, or two children. It also deals with moving around a “successor node” and managing the successor node’s child if it has one.

Treap deletion, on the other hand, can pretty much be summed up in one sentence: Continuously rotate the node_to_delete downward with the child with the lesser priority until the node_to_delete becomes a leaf node, and then remove it from the treap.

Now, here’s the interesting thing. The treap deletion algorithm would work as well on a classic BST, too. Although BSTs don’t have priorities, we could simply rotate the node_to_delete downward through the tree, choosing any child at random, until the node_to_delete becomes a leaf node, after which we can remove it from the tree. Again, rotations never cause a violation of the BST Rule, so there’s no reason we can’t perform this deletion algorithm on a BST.

It seems that the only reason this algorithm is not typically used on classic BSTs is that it involves rotations, which are not themselves the simplest of all algorithms. Essentially, then, it’s a complexity trade-off. The BST deletion algorithm has complexity in dealing with multiple scenarios but avoids having to implement rotations.

Treaps, on the other hand, already have to implement rotations to power insertions. Once the ability to perform rotations is in place, we may as well use them to implement a simple deletion algorithm.

On a similar note, we could also technically use the classic BST deletion algorithm on treaps, but this would, in many cases, trigger a Heap Rule violation since we often plug a “successor node” into a higher spot within the tree. We’d then have to fix the treap by rotating the successor node down through the treap. But this is all considerably more complicated than simply rotating the node_to_delete down through the treap in the first place, so why go through all that trouble?

Code Implementation: Treap Deletion

Here, we implement a delete method, which in turn depends on a search method:

The search method is identical to classic BST search, so let’s focus on the delete method.

We begin by searching for a node with the value we’re trying to delete. If we find that node, it’s assigned to the variable node_to_delete. If it’s not found, we terminate the method early by returning False:

Next, we handle the unique case where the node_to_delete is the only node inside the treap, in which case we simply remove it from the treap by resetting the root to None:

Next, we begin our loop that runs as long as the node_to_delete has at least one child:

We then perform a clockwise rotation with the node_to_delete and its left child if either there’s no right child or if the left child has a smaller priority than the right child:

On the other hand, if only a right child exists or if the right child’s priority is smaller than the left child, we rotate the node_to_delete with its right child:

Finally, we cut off the node_to_delete from the treap:

We finally conclude the method by returning the node_to_delete to confirm that the deletion was successful.

And that’s it!