Treaps: Priorities, Expected Depth, and Rotation-Only Updates

A treap is a binary tree whose nodes carry two values: a key, ordered as in a search tree, and a priority, ordered as in a max-heap. The two orders are independent, and that independence is the whole design. A node’s priority is drawn at random when the node is created, and the tree is the unique shape that satisfies both orders simultaneously. Because the priorities are random, the shape is distributed exactly as if the keys had been inserted in random order — which is to say, with expected depth logarithmic in the number of keys.

The structure is worth studying for three reasons. It needs no balance metadata at all: no height, no colour, no subtree size. It has a direct, non-recursive deletion: rotate the node down until it is a leaf, then unlink it. And its height bound is probabilistic rather than worst-case, which changes what “guaranteed” means for an implementation that has to reason about tail latency.

The shape is determined by the priorities

Given a set of key-priority pairs with distinct keys and distinct priorities, exactly one binary tree satisfies both the search order on keys and the heap order on priorities. The root must be the node with the highest priority, since heap order forces it above everything else; the keys smaller than it form its left subtree and the keys larger form its right, recursively. That construction is deterministic given the priorities, and it produces a tree whose shape is the Cartesian tree of the priority sequence when the keys are taken in sorted order.

The distribution claim follows. If the priorities are independent uniform random values, the highest priority among n keys is equally likely to be any of them, so the root is a uniformly random key. The left and right subtrees then have the same distribution on their own key sets, recursively. That is exactly the distribution of a binary search tree built by inserting keys in a uniformly random permutation: the first inserted key becomes the root, and it is uniform. So a treap on random priorities has the same shape distribution as a random-insertion BST, including the expected depth of about 2 ln n and the expected height of about 4.311 ln n.

The distinction from the earlier discussion of random insertion, in height bounds and degenerate search trees, is where the randomness lives. In a random-insertion BST the randomness is a property of the input, and an adversary who controls insertion order controls the shape. In a treap the randomness is a property of the structure, chosen independently of the keys, so no input order can force a bad shape. An adversary who knows the priority generator can still try to choose keys that interact badly with a known priority sequence, which is why implementations use a seeded generator with an unpredictable seed rather than a fixed one.

Insertion is a descent plus rotations

Insertion allocates a node with a fresh priority, attaches it as a leaf where the search order requires, then rotates it upward while its priority exceeds its parent’s. Each rotation moves it one level closer to the root and preserves the in-order sequence. The process stops when the parent has a higher priority or the node reaches the root.

The expected number of rotations is the expected number of ancestors with lower priority, which is at most the expected depth, so O(log n). The descent is O(log n) as well. No other node’s metadata is touched, because there is none.

struct Node<K, P> {
    key: K,
    prio: P,
    left: Option<Box<Node<K, P>>>,
    right: Option<Box<Node<K, P>>>,
}

// Rotate the left child up; returns the new subtree root.
fn rotate_right<K, P>(mut t: Box<Node<K, P>>) -> Box<Node<K, P>> {
    let mut l = t.left.take().expect("left child must exist");
    t.left = l.right.take();
    l.right = Some(t);
    l
}

The rotation is the same three-pointer rewrite used everywhere in this cluster, described at the pointer level in rotations and in-order invariance. The difference is the trigger: an AVL tree rotates when a height difference reaches two, a red-black tree rotates when recolouring fails, and a treap rotates whenever the heap order is violated. The trigger is a comparison of two priorities, which is a single integer comparison if priorities are 64-bit values.

Deletion is the inverse and is unusual among balanced trees in being expressed entirely with rotations. To delete a node, rotate it downward — choosing at each step to rotate the child with the higher priority upward — until it has no children, then unlink the leaf. Rotating the higher-priority child up maintains the heap order for the rest of the tree, and the node being deleted sinks monotonically. The number of rotations equals the length of the path from the node to a leaf in the resulting tree, which is at most the height.

The union operation and why it is cheap

Two treaps whose key ranges are disjoint can be merged without any per-node search. If one is empty, return the other. Otherwise compare the two roots’ priorities: the higher-priority root becomes the root of the result, and the other treap is split at that root’s key into the part below and the part above, which are then merged recursively with the corresponding subtrees. The split is a descent, so the total cost is O(m log(n/m)) for merging trees of sizes m ≤ n, a bound that is better than the O(m log n) of inserting the smaller tree’s keys one at a time.

Set union and intersection follow the same pattern: split one tree at the other’s root key, recurse on the pieces, and rejoin with the root if the key is present in both. The recursion visits only the parts of the trees that overlap, so the cost is proportional to the size of the smaller tree times a logarithmic factor. This is the same shape of algorithm as the split-and-join approach taken by weight-balanced trees, and the two structures are the main alternatives when bulk set operations matter.

The reason a treap can do this without rebalancing logic is that the priorities already encode the shape the merged tree must have. Merging two treaps whose priority sets are independent is again a treap on the union of the key sets, because the priorities were drawn independently and the heap order picks the root deterministically. No invariant needs to be restored; the recursion constructs the unique valid shape directly.

What “expected” costs in practice

The height bound is O(log n) in expectation, and the tail is what matters for a system with a latency budget. The probability that the height exceeds c log₂ n is small but not negligible for small c; the standard analysis gives a bound that decays exponentially in c, so choosing c large enough makes the probability negligible, at the cost of a height constant that is worse than a red-black tree’s deterministic 2 log₂(n + 1).

For most workloads the distinction never surfaces, because the expected height is close to the deterministic bound and the tail is thin. It surfaces in three situations. The first is when an adversary can observe or predict the priority generator; a deterministic seed makes the shape a function of the keys, and a crafted key set can produce a degenerate tree. The second is when the tree is rebuilt incrementally across processes and the priorities must be reproduced exactly, which forces a deterministic generator and reintroduces the adversarial concern. The third is when the workload is latency-critical and a single deep path is unacceptable regardless of its probability, which is the case where a deterministic bound is worth paying for.

The memory argument is the strongest reason to choose a treap. A node needs a key, two child pointers, and a priority. If the priority is 64 bits, the node is larger than a red-black node by 8 bytes, but no colour bit is needed and no subtree count is needed unless order statistics are required. Compared with a weight-balanced tree, which stores a full word for size, the treap is the same size or smaller. Compared with an AVL tree, which stores a height or a factor, it is larger by a few bytes but simpler to maintain.

Determinism and reproducibility

A treap’s shape is a function of its priorities, so two processes that build the same key set with the same priority sequence produce identical trees. That property is useful for comparing implementations and for producing reproducible serialized forms, and it is a liability when the priority sequence is predictable.

The standard mitigation is to derive the priority from a hash of the key with a per-process random seed, rather than from a counter or a global random stream. Deriving from the key makes the shape stable for a given seed regardless of insertion order, which is often what is wanted; the random seed makes it unpredictable to an adversary. Implementations that need both reproducibility and unpredictability store the seed alongside the tree.

A subtler issue is that priorities must be distinct. Collisions produce nodes of equal priority, and the heap order no longer determines a unique shape, so the analysis no longer applies directly. With 64-bit priorities and a few million nodes, a collision is unlikely but not impossible, and implementations either break ties by key comparison — which makes the shape deterministic but no longer uniform — or use a 128-bit priority. The tie-breaking choice is invisible in normal operation and shows up as a slight height increase when collisions occur, which is exactly the kind of defect that a validation pass over the heap order will catch and a random workload will not.