Treap: A Randomized Binary Search Tree
Explore how Treaps combine binary search tree and heap properties to implement the SSet interface. Understand the role of random priorities, rotations for maintaining heap order, and how add and remove operations work efficiently. This lesson helps you comprehend the expected performance and practical advantages of Treaps in managing dynamic sets.
The problem with random binary search trees is, of course, that they
are not dynamic. They don’t support the add(x) or remove(x) operations
needed to implement the SSet interface. In this section we describe a
data structure called a Treap that uses Lemma 1 to implement the SSet
interface.
Note: The names Treap comes from the fact that this data structure is simultaneously a binary search tree and a heap.
Treap overview
A node in a Treap is like a node in a BinarySearchTree in that it has
a data value, x, but it also contains a unique numerical priority, p, that is
assigned at random:
In addition to being a binary search tree, the nodes in a Treap also
obey the heap property:
- Heap Property: At every node
u, except the root,u.parent.p < u.p.
In other words, each node has a priority smaller than that of its two children. An example is shown in the figure below.
The heap and binary search tree conditions together ensure that, once
the key(x) and priority(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, r, of the Treap. The binary
search tree property tells us that all nodes with keys smaller than r.x are
stored in the subtree rooted at r.left and all nodes with keys larger than
r.x are stored in the subtree rooted at 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 the above figure can be obtained by
adding the sequence of (x, p) values
...