7.2 Treap: A Randomized Binary Search Tree

The problem with random binary search trees is, of course, that they are not dynamic. They don't support the $\mathtt{add(x)}$ or $\mathtt{remove(x)}$ operations needed to implement the SSet interface. In this section we describe a data structure called a Treap that uses Lemma 7.1 to implement the SSet interface.

A node in a Treap is like a node in a BinarySearchTree in that it has a data value, $\mathtt{x}$, but it also contains a unique numerical priority, $\mathtt{p}$, that is assigned at random:

    class Node<T> extends BinarySearchTree.BSTNode<Node<T>,T> {
        int p;
    }

In addition to being a binary search tree, the nodes in a Treap also obey the heap property: At every node $\mathtt{u}$, except the root, $\ensuremath{\mathtt{u.parent.p}} < \ensuremath{\mathtt{u.p}}$. That is, each node has a priority smaller than that of its two children. An example is shown in Figure 7.5.

Figure 7.5: An example of a Treap containing the integers $0,\ldots,9$. Each node, $\mathtt{u}$, is illustrated with $\ensuremath{\mathtt{u.x}},\ensuremath{\mathtt{u.p}}$.

The heap and binary search tree conditions together ensure that, once the key ( $\mathtt{x}$) and priority ( $\mathtt{p}$) for each node are defined, the shape of the Treap is completely determined. The heap property tells us that the node with minimum priority has to be the root, $\mathtt{r}$, of the Treap. The binary search tree property tells us that all nodes with keys smaller than $\mathtt{r.x}$ are stored in the subtree rooted at $\mathtt{r.left}$ and all nodes with keys larger than $\mathtt{r.x}$ are stored in the subtree rooted at $\mathtt{r.right}$.

The important point about the priority values in a Treap is that they are unique and assigned at random. Because of this, there are two equivalent ways we can think about a Treap. As defined above, a Treap obeys the heap and binary search tree properties. Alternatively, we can think of a Treap as a BinarySearchTree whose nodes were added in increasing order of priority. For example, the Treap in Figure 7.5 can be obtained by adding the sequence of $(\ensuremath{\mathtt{x}},\ensuremath{\mathtt{p}})$ values

$$\langle (3,1), (1,6), (0,9), (5,11), (4,14), (9,17), (7,22), (6,42), (8,49), (2,99) \rangle$$

into a BinarySearchTree.

Since the priorities are chosen randomly, this is equivalent to taking a random permutation of the keys -- in this case the permutation is

$$\langle 3, 1, 0, 5, 9, 4, 7, 6, 8, 2 \rangle$$

-- and adding these to a BinarySearchTree. But this means that the shape of a treap is identical to that of a random binary search tree. In particular, if we replace each key $\mathtt{x}$ by its rank,² then Lemma 7.1 applies. Restating Lemma 7.1 in terms of Treaps, we have:

Lemma 7..2   In a Treap that stores a set $S$ of $\mathtt{n}$ keys, the following statements hold:

1. For any $\ensuremath{\mathtt{x}}\in S$, the expected length of the search path for $\mathtt{x}$ is $H_{r(\ensuremath{\mathtt{x}})+1} + H_{\ensuremath{\mathtt{n}}-r(\ensuremath{\mathtt{x}})} - O(1)$.
2. For any $\ensuremath{\mathtt{x}}\not\in S$, the expected length of the search path for $\mathtt{x}$ is $H_{r(\ensuremath{\mathtt{x}})} + H_{\ensuremath{\mathtt{n}}-r(\ensuremath{\mathtt{x}})}$.

Here, $r(\ensuremath{\mathtt{x}})$ denotes the rank of $\mathtt{x}$ in the set $S\cup\{\ensuremath{\mathtt{x}}\}$.

Lemma 7.2 tells us that Treaps can implement the $\mathtt{find(x)}$ operation efficiently. However, the real benefit of a Treap is that it can support the $\mathtt{add(x)}$ and $\mathtt{delete(x)}$ operations. To do this, it needs to perform rotations in order to maintain the heap property. Refer to Figure 7.6. A rotation in a binary search tree is a local modification that takes a parent $\mathtt{u}$ of a node $\mathtt{w}$ and makes $\mathtt{w}$ the parent of $\mathtt{u}$, while preserving the binary search tree property. Rotations come in two flavours: left or right depending on whether $\mathtt{w}$ is a right or left child of $\mathtt{u}$, respectively.

Figure 7.6: Left and right rotations in a binary search tree.

The code that implements this has to handle these two possibilities and be careful of a boundary case (when $\mathtt{u}$ is the root) so the actual code is a little longer than Figure 7.6 would lead a reader to believe:

    void rotateLeft(Node u) {
        Node w = u.right;
        w.parent = u.parent;
        if (w.parent != nil) {
            if (w.parent.left == u) {
                w.parent.left = w;
            } else {
                w.parent.right = w;
            }
        }
        u.right = w.left;
        if (u.right != nil) {
            u.right.parent = u;
        }
        u.parent = w;
        w.left = u;
        if (u == r) { r = w; r.parent = nil; }
    }    
    void rotateRight(Node u) {
        Node w = u.left;
        w.parent = u.parent;
        if (w.parent != nil) {
            if (w.parent.left == u) {
                w.parent.left = w;
            } else {
                w.parent.right = w;
            }
        }
        u.left = w.right;
        if (u.left != nil) {
            u.left.parent = u;
        }
        u.parent = w;
        w.right = u;
        if (u == r) { r = w; r.parent = nil; }
    }

In terms of the Treap data structure, the most important property of a rotation is that the depth of $\mathtt{w}$ decreases by one while the depth of $\mathtt{u}$ increases by one.

Using rotations, we can implement the $\mathtt{add(x)}$ operation as follows: We create a new node, $\mathtt{u}$, and assign $\mathtt{u.x=x}$ and pick a random value for $\mathtt{u.p}$. Next we add $\mathtt{u}$ using the usual $\mathtt{add(x)}$ algorithm for a BinarySearchTree, so that $\mathtt{u}$ is now a leaf of the Treap. At this point, our Treap satisfies the binary search tree property, but not necessarily the heap property. In particular, it may be the case that $\mathtt{u.parent.p > u.p}$. If this is the case, then we perform a rotation at node $\mathtt{w}$= $\mathtt{u.parent}$ so that $\mathtt{u}$ becomes the parent of $\mathtt{w}$. If $\mathtt{u}$ continues to violate the heap property, we will have to repeat this, decreasing $\mathtt{u}$'s depth by one every time, until $\mathtt{u}$ either becomes the root or $\ensuremath{\mathtt{u.parent.p}} < \ensuremath{\mathtt{u.p}}$.

    boolean add(T x) {
        Node<T> u = newNode();
        u.x = x;
        u.p = rand.nextInt();
        if (super.add(u)) {
            bubbleUp(u);
            return true;
        }
        return false;
    }
    void bubbleUp(Node<T> u) {
        while (u.parent != nil && u.parent.p > u.p) {
            if (u.parent.right == u) {
                rotateLeft(u.parent);
            } else {
                rotateRight(u.parent);
            }
        }
        if (u.parent == nil) {
            r = u;
        }
    }

An example of an $\mathtt{add(x)}$ operation is shown in Figure 7.7.

Figure 7.7: Adding the value 1.5 into the Treap from Figure 7.5.

The running time of the $\mathtt{add(x)}$ operation is given by the time it takes to follow the search path for $\mathtt{x}$ plus the number of rotations performed to move the newly-added node, $\mathtt{u}$, up to its correct location in the Treap. By Lemma 7.2, the expected length of the search path is at most $2\ln \ensuremath{\mathtt{n}}+O(1)$. Furthermore, each rotation decreases the depth of $\mathtt{u}$. This stops if $\mathtt{u}$ becomes the root, so the expected number of rotations cannot exceed the expected length of the search path. Therefore, the expected running time of the $\mathtt{add(x)}$ operation in a Treap is $O(\log \ensuremath{\mathtt{n}})$. (Exercise 7.3 asks you to show that the expected number of rotations performed during an insertion is actually only $O(1)$.)

The $\mathtt{remove(x)}$ operation in a Treap is the opposite of the $\mathtt{add(x)}$ operation. We search for the node, $\mathtt{u}$, containing $\mathtt{x}$ and then perform rotations to move $\mathtt{u}$ downwards until it becomes a leaf and then we splice $\mathtt{u}$ from the Treap. Notice that, to move $\mathtt{u}$ downwards, we can perform either a left or right rotation at $\mathtt{u}$, which will replace $\mathtt{u}$ with $\mathtt{u.right}$ or $\mathtt{u.left}$, respectively. The choice is made by the first of the following that apply:

1. If $\mathtt{u.left}$ and $\mathtt{u.right}$ are both $\mathtt{null}$, then $\mathtt{u}$ is a leaf and no rotation is performed.
2. If $\mathtt{u.left}$ (or $\mathtt{u.right}$) is $\mathtt{null}$, then perform a right (or left, respectively) rotation at $\mathtt{u}$.
3. If $\ensuremath{\mathtt{u.left.p}} < \ensuremath{\mathtt{u.right.p}}$ (or $\ensuremath{\mathtt{u.left.p}} > \ensuremath{\mathtt{u.right.p}})$, then perform a right rotation (or left rotation, respectively) at $\mathtt{u}$.

These three rules ensure that the Treap doesn't become disconnected and that the heap property is maintained once $\mathtt{u}$ is removed.

    boolean remove(T x) {
        Node<T> u = findLast(x);
        if (u != nil && compare(u.x, x) == 0) {
            trickleDown(u);
            splice(u);
            return true;
        }
        return false;
    }
    void trickleDown(Node<T> u) {
        while (u.left != nil || u.right != nil) {
            if (u.left == nil) {
                rotateLeft(u);
            } else if (u.right == nil) {
                rotateRight(u);
            } else if (u.left.p < u.right.p) {
                rotateRight(u);
            } else {
                rotateLeft(u);
            }
            if (r == u) {
                r = u.parent;
            }
        }
    }

An example of the $\mathtt{remove(x)}$ operation is shown in Figure 7.8.

Figure 7.8: Removing the value 9 from the Treap in Figure 7.5.

The trick to analyze the running time of the $\mathtt{remove(x)}$ operation is to notice that this operation is the reverse of the $\mathtt{add(x)}$ operation. In particular, if we were to reinsert $\mathtt{x}$, using the same priority $\mathtt{u.p}$, then the $\mathtt{add(x)}$ operation would do exactly the same number of rotations and would restore the Treap to exactly the same state it was in before the $\mathtt{remove(x)}$ operation took place. (Reading from bottom-to-top, Figure 7.8 illustrates the insertion of the value 9 into a Treap.) This means that the expected running time of the $\mathtt{remove(x)}$ on a Treap of size $\mathtt{n}$ is proportional to the expected running time of the $\mathtt{add(x)}$ operation on a Treap of size $\ensuremath{\mathtt{n}}-1$. We conclude that the expected running time of $\mathtt{remove(x)}$ is $O(\log \ensuremath{\mathtt{n}})$.

7.2.1 Summary

The following theorem summarizes the performance of the Treap data structure:

Theorem 7..2   A Treap implements the SSet interface. A Treap supports the operations $\mathtt{add(x)}$, $\mathtt{remove(x)}$, and $\mathtt{find(x)}$ in $O(\log \ensuremath{\mathtt{n}})$ expected time per operation.

It is worth comparing the Treap data structure to the SkiplistSSet data structure. Both implement the SSet operations in $O(\log \ensuremath{\mathtt{n}})$ expected time per operation. In both data structures, $\mathtt{add(x)}$ and $\mathtt{remove(x)}$ involve a search and then a constant number of pointer changes (see Exercise 7.3 below). Thus, for both these structures, the expected length of the search path is the critical value in assessing their performance. In a SkiplistSSet, the expected length of a search path is

$$2\log \ensuremath{\mathtt{n}} + O(1) \enspace ,$$

In a Treap, the expected length of a search path is

$$2\ln \ensuremath{\mathtt{n}} +O(1) \approx 1.386\log \ensuremath{\mathtt{n}} + O(1) \enspace .$$

Thus, the search paths in a Treap are considerably shorter and this translates into noticeably faster operations on Treaps than Skiplists. Exercise 4.2 in Chapter 4 shows how the expected length of the search path in a Skiplist can be reduced to

$$e\ln \ensuremath{\mathtt{n}} + O(1) \approx 1.884\log \ensuremath{\mathtt{n}} + O(1)$$

by using biased coin tosses. Even with this optimization, the expected length of search paths in a SkiplistSSet is noticeably longer than in a Treap.

Footnotes

... rank,²

The rank of an element $\mathtt{x}$ in a set $S$ of elements is the number of elements in $S$ that are less than $\mathtt{x}$.