Treaps

Like a red-black tree, a treap is a type of binary search tree (BST), but a treap follows a unique set of rules beyond the behavior of a traditional BST. The name “treap” is a combination of the words “tree” and “heap,” and you’ll see shortly what heaps have to do with treaps, other than the fact that they rhyme.

Treaps themselves come in various flavors, not all of which are self-balancing. Our focus in this chapter is on the randomized treap since this is the kind of treap that serves as a self-balancing tree. To save ink, though, I’ll refer to randomized treaps simply as treaps since that’s the only type of treap we’ll be dealing with here.

Treaps vs. Red-Black Trees

Treaps and red-black trees share certain things in common:

1. They are both variants of BSTs. As a reminder, to be considered a BST, (1) a tree must have nodes with 0, 1, or 2 children; and (2) a node’s left descendants must all have lower values than it, and a node’s right descendants must all have greater values than it. For ease of reference, I’ll call this the “BST Rule” throughout this chapter.

2. Red-black trees and treaps are both self-balancing trees. This means that even if we insert values in ascending order, the tree will not become a linked list, but instead will have a height along the lines of log N.

3. Treaps maintain balance using the same types of rotations red-black trees use. In , I discussed the details of how clockwise and counterclockwise rotations work; treaps use these very same rotations.

However, this is where the similarities between treaps and red-black trees end. While red-black trees maintain balance using the Red-Black Rules outlined in , these rules do not exist in the world of treaps. In fact, treap nodes have no concept of color at all. Instead, treaps follow a simpler set of rules. And thank goodness for that.

Treap Nodes

Treap nodes are different than classic BST nodes in that, in addition to containing a value, each treap node also contains an extra piece of data. This extra data is called the priority, and comes in the form of a number. We’ll see shortly what the purpose of the priority is.

A node’s priority is not at all correlated to the node’s value. In fact, in a randomized treap, a node’s priority is generated randomly.

Throughout this chapter, all of the treap diagrams will have nodes that contain a value that is a letter from the alphabet, and a priority that is a number between 1 and 100. (It’s common to choose a priority that is a float that lies between 0 and 1, but I’m using the range of 1 to 100 to keep the diagrams simple.) Here’s an example treap node:

Although in past chapters I used numerical values in tree examples, to easily distinguish between the value and the priority, I’m making values alphabetical characters in this chapter. Really, though, treap node values can be numbers (or any data type) as with any tree.

An example of a treap is .

Note that because a treap is a type of BST, it must follow the BST Rule, which is that the left descendants’ values must be smaller than their ancestor, and the right descendants’ values must be greater than their ancestor. Because we’re using alphabet letters as values, whether a letter is smaller or greater than another letter depends on its placement within the alphabet. For example, the letter Q is considered “greater” than the letter H because Q appears later in the alphabet. The letter A is the “smallest” value in the entire alphabet, and the letter Z is the “greatest” value.

The Heap Rule

So far, we’ve seen that a special attribute of a treap is that its nodes contain priorities in addition to values. However, treaps have one other important attribute: a treap must adhere to what I call the “Heap Rule.” Fortunately, the Heap Rule is pretty straightforward:

• The Heap Rule: Each node’s priority must be greater than (or equal to) its parent’s priority.

Take a look at the of our example treap. Note that the treap follows the Heap Rule, as the root node contains the smallest priority, and as we descend downward through the tree, the nodes’ priorities become increasingly greater. There isn’t a single node that has a smaller priority than its parent.

The Heap Rule is derived from the concept of the heap data structure, which I covered in Volume 1, Chapter 16. There, I explained that in a min-heap, the value of each node must be greater than its parent’s value. However, with a heap, it was the value that needed to follow the Heap Rule. With treaps, on the other hand, it’s not the value, but the priority that must follow the Heap Rule.

Recall from Volume 1 that a heap can either be a min-heap or a max-heap. The two types of heaps are virtually the same, except that a min-heap makes the arbitrary decision that each node’s value must be greater than its parent, and a max-heap makes the decision that each node’s value must be smaller than its parent.

A similar arbitrary decision can be made with treaps. That is, a treap can also be either a “min-treap” or a “max-treap.” In this chapter, we’ll arbitrarily go with the “min-treap” flavor, simply because much of the treap documentation out there does as well.

The Heap Rule and BST Rule

I noted at the beginning of this chapter that the name “treap” comes from combining the terms “tree” and “heap.” This, indeed, is because treaps follow the Heap Rule, much in the way that heaps do. However, I must point out a critical distinction between treaps and heaps.

Heaps only follow the Heap Rule, and cannot be a BST. Take a min-heap, for example. The heap is only valid if each node has a smaller value than either of its children. However, in a BST, a node is required to have a greater value than its left child.

Treaps, though, follow both the Heap Rule and the BST Rule. While that might sound impossible at first, here’s how this works: treaps follow the BST Rule with regard to the nodes’ values, but follow the Heap Rule with regard to the nodes’ priorities.

In other words, treaps must ensure that the values of each node act like a BST—namely, that a node’s left descendants have smaller values, and a node’s right descendants must have greater values. At the same time, treaps have to be careful that each node’s priority is greater than the priority of its parent.

Let’s take one more look at our example treap. If you look carefully, you’ll see that both the BST Rule and Heap Rule are adhered to by all the nodes in the treap: