Treap

Operations

Basic operations

Treaps support the following basic operations:

• To search for a given key value, apply a standard binary search algorithm in a binary search tree, ignoring the priorities.
• To insert a new key x into the treap, generate a random priority y for x. Binary search for x in the tree, and create a new node at the leaf position where the binary search determines a node for x should exist. Then, as long as x is not the root of the tree and has a larger priority number than its parent z, perform a tree rotation that reverses the parent-child relation between x and z.
• To delete a node x from the treap, if x is a leaf of the tree, simply remove it. If x has a single child z, remove x from the tree and make z be the child of the parent of x (or make z the root of the tree if x had no parent). Finally, if x has two children, swap its position in the tree with the position of its immediate successor z in the sorted order, resulting in one of the previous cases. In this final case, the swap may violate the heap-ordering property for z, so additional rotations may need to be performed to restore this property.

Building a treap

• To build a treap we can simply insert n values in the treap where each takes ${\displaystyle O(\log n)}$ time. Therefore a treap can be built in ${\displaystyle O(n\log n)}$ time from a list values.

Bulk operations

In addition to the single-element insert, delete and lookup operations, several fast "bulk" operations have been defined on treaps: union, intersection and set difference. These rely on two helper operations, split and join.

• To split a treap into two smaller treaps, those smaller than key x, and those larger than key x, insert x into the treap with maximum priority—larger than the priority of any node in the treap. After this insertion, x will be the root node of the treap, all values less than x will be found in the left subtreap, and all values greater than x will be found in the right subtreap. This costs as much as a single insertion into the treap.
• Joining two treaps that are the product of a former split, one can safely assume that the greatest value in the first treap is less than the smallest value in the second treap. Create a new node with value x, such that x is larger than this max-value in the first treap and smaller than the min-value in the second treap, assign it the minimum priority, then set its left child to the first heap and its right child to the second heap. Rotate as necessary to fix the heap order. After that, it will be a leaf node, and can easily be deleted. The result is one treap merged from the two original treaps. This is effectively "undoing" a split, and costs the same. More generally, the join operation can work on two treaps and a key with arbitrary priority (i.e., not necessary to be the highest).

The join algorithm is as follows:

<b id="mwcg">function</b> join(L, k, R) <b id="mwcw">if</b> prior(k, k(L)) and prior(k, k(R)) <b id="mwdA">return</b> Node(L, k, R) <b id="mwdQ">if</b> prior(k(L), k(R)) <b id="mwdg">return</b> Node(left(L), k(L), join(right(L), k, R)) <b id="mwdw">return</b> Node(join(L, k, left(R)), k(R), right(R))

The split algorithm is as follows:

<b id="mwgQ">function</b> split(T, k) <b id="mwgg">if</b> (T = nil) <b id="mwgw">return</b> (nil, false, nil) (L, (m, c), R) = expose(T) <b id="mwhA">if</b> (k = m) <b id="mwhQ">return</b> (L, true, R) <b id="mwhg">if</b> (k < m) (L', b, R') = split(L, k) <b id="mwhw">return</b> (L', b, join(R', m, R)) <b id="mwiA">if</b> (k > m) (L', b, R') = split(R, k) <b id="mwiQ">return</b> (join(L, m, L'), b, R'))

The union of two treaps t₁ and t₂, representing sets A and B is a treap t that represents A ∪ B. The following recursive algorithm computes the union:

<b id="mwkg">function</b> union(t<sub id="mwkw">1</sub>, t<sub id="mwlA">2</sub>): <b id="mwlQ">if</b> t<sub id="mwlg">1</sub> = nil: <b id="mwlw">return</b> t<sub id="mwmA">2</sub> <b id="mwmQ">if</b> t<sub id="mwmg">2</sub> = nil: <b id="mwmw">return</b> t<sub id="mwnA">1</sub> <b id="mwnQ">if</b> priority(t<sub id="mwng">1</sub>) < priority(t<sub id="mwnw">2</sub>): <b id="mwoA">swap</b> t<sub id="mwoQ">1</sub> and t<sub id="mwog">2</sub> t<sub id="mwow"><</sub>, t<sub id="mwpA">></sub> ← split t<sub id="mwpQ">2</sub> on key(t<sub id="mwpg">1</sub>) <b id="mwpw">return</b> join(union(left(t<sub id="mwqA">1</sub>), t<sub id="mwqQ"><</sub>), key(t<sub id="mwqg">1</sub>), union(right(t<sub id="mwqw">1</sub>), t<sub id="mwrA">></sub>))

Here, split is presumed to return two trees: one holding the keys less than its input key, one holding the greater keys. (The algorithm is non-destructive, but an in-place destructive version exists as well.)

The algorithm for intersection is similar, but requires the join helper routine. The complexity of each of union, intersection and difference is O(m log (⁠n/m⁠ + 1)) for treaps of sizes m and n, with m ≤ n. Moreover, since the recursive calls to union are independent of each other, they can be executed in parallel.

Randomized binary search tree

The randomized binary search tree, introduced by Martínez and Roura subsequently to the work of Aragon and Seidel on treaps, stores the same nodes with the same random distribution of tree shape, but maintains different information within the nodes of the tree in order to maintain its randomized structure.

Rather than storing random priorities on each node, the randomized binary search tree stores a small integer at each node, the number of its descendants (counting itself as one); these numbers may be maintained during tree rotation operations at only a constant additional amount of time per rotation. When a key x is to be inserted into a tree that already has n nodes, the insertion algorithm chooses with probability 1/(n + 1) to place x as the new root of the tree, and otherwise, it calls the insertion procedure recursively to insert x within the left or right subtree (depending on whether its key is less than or greater than the root). The numbers of descendants are used by the algorithm to calculate the necessary probabilities for the random choices at each step. Placing x at the root of a subtree may be performed either as in the treap by inserting it at a leaf and then rotating it upwards, or by an alternative algorithm described by Martínez and Roura that splits the subtree into two pieces to be used as the left and right children of the new node.

The deletion procedure for a randomized binary search tree uses the same information per node as the insertion procedure, but unlike the insertion procedure, it only needs on average O(1) random decisions to join the two subtrees descending from the left and right children of the deleted node into a single tree. That is because the subtrees to be joined are on average at depth Θ(log n); joining two trees of size n and m needs Θ(log(n+m)) random choices on average. If the left or right subtree of the node to be deleted is empty, the join operation is trivial; otherwise, the left or right child of the deleted node is selected as the new subtree root with probability proportional to its number of descendants, and the join proceeds recursively.

Comparison

The information stored per node in the randomized binary tree is simpler than in a treap (a small integer rather than a high-precision random number), but it makes a greater number of calls to the random number generator (O(log n) calls per insertion or deletion rather than one call per insertion) and the insertion procedure is slightly more complicated due to the need to update the numbers of descendants per node. A minor technical difference is that, in a treap, there is a small probability of a collision (two keys getting the same priority), and in both cases, there will be statistical differences between a true random number generator and the pseudo-random number generator typically used on digital computers. However, in any case, the differences between the theoretical model of perfect random choices used to design the algorithm and the capabilities of actual random number generators are vanishingly small.

Although the treap and the randomized binary search tree both have the same random distribution of tree shapes after each update, the history of modifications to the trees performed by these two data structures over a sequence of insertion and deletion operations may be different. For instance, in a treap, if the three numbers 1, 2, and 3 are inserted in the order 1, 3, 2, and then the number 2 is deleted, the remaining two nodes will have the same parent-child relationship that they did prior to the insertion of the middle number. In a randomized binary search tree, the tree after the deletion is equally likely to be either of the two possible trees on its two nodes, independently of what the tree looked like prior to the insertion of the middle number.