The Treap

A treap stores a search key and a priority in every node. The keys satisfy the binary-search-tree invariant: every key in the left subtree is smaller, and every key in the right subtree is larger.

The priority is the treap’s balancing metadata. A regular binary search tree has no such field, so its shape depends on insertion order; inserting already-sorted keys can produce a chain. A treap assigns priorities independently at random and rotates higher-priority nodes above lower-priority nodes. This makes the shape depend on the random priorities instead of the insertion order, giving expected logarithmic height.

Priorities therefore control the tree’s shape, not search order or application-level importance. In a max-heap treap, every parent has a greater priority than either child.

Among a set of nodes with distinct priorities, the node with the greatest priority must be the root. Its key partitions the remaining nodes into a smaller-key left subtree and a larger-key right subtree. The same rule applies recursively within each partition.

The two invariants therefore determine a unique tree for a fixed set of key-priority pairs. An in-order traversal^* still returns the keys in sorted order, while the priorities determine the shape.

^* An in-order traversal visits the left subtree, then the current node, then the right subtree. In a binary search tree, this visits the keys from smallest to largest.

Search ignores priorities. Compare the target with the current key, continue left for a smaller target, and continue right for a larger target until the key is found or a missing child proves that it is absent.

The operation visits one root-to-leaf path, so its cost is O(h) for tree height h. Random priorities keep h logarithmic in expectation.

Insertion first places the new key as a leaf using the ordinary binary-search-tree rule. If the new node has a greater priority than its parent, a rotation moves it upward. Rotations continue until its parent has a greater priority or the new node becomes the root.

Insert (65, 88) below (60, 45). First, 88 > 45, so a left rotation at 60 makes 65 the parent of 60. The new parent is then (75, 70). Because 88 > 70, a second rotation—right at 75—makes 65 the parent of 75. The process stops below (50, 95) because 95 > 88.

A rotation promotes one child and demotes its parent. The subtree between those two nodes changes sides, but no key crosses another key in the in-order sequence. Treap insertion therefore uses rotations to repair priority order without breaking search order.

Seidel and Aragon showed that an update uses fewer than two rotations on average, even though the search path to the update position has expected logarithmic length. The structural changes remain local to that path.

To delete a node with two children, rotate the child with the greater priority upward. This moves the target one level lower while preserving heap order among the nodes that remain. Repeat until the target has at most one child, then remove it with the standard binary-search-tree splice.

Deletion touches a single downward path. Its expected running time is O(log n), including both the search and the rotations.

If priorities are chosen independently at random and ties are broken consistently, their relative order is a uniformly random permutation. The resulting treap has the same shape distribution as a binary search tree built by inserting the keys in random order.

The expected height is Θ(log n), so search, insertion, and deletion take expected O(log n) time. This is a probabilistic performance guarantee. A priority assignment that produces a chain is possible, giving worst-case Θ(n) height.

Split partitions a treap around a key k. One result contains keys smaller than k; the other contains keys greater than or equal to k. The algorithm follows a search path and reconnects the subtrees passed on the way down.

Only nodes on that path change, so split takes expected O(log n) time. Both results continue to satisfy the search-tree and heap invariants.

Merge combines treaps A and B when every key in A is smaller than every key in B. The root with the greater priority becomes the result root. The algorithm then recursively merges one of its subtrees with the other treap.

Merge follows the boundary between the two key ranges and takes expected O(log(|A| + |B|)) time. Insertion can also be expressed as two splits followed by two merges; deletion can be expressed as splits that isolate the target, followed by one merge.

Split and merge extend from single-key updates to union, intersection, and difference on ordered sets. Select a root from one input, split the other input around that root key, and recurse independently on the two key ranges.

For input sizes m and n, where m ≤ n, treap set operations can use expected O(m log(n/m + 1)) work. The two recursive sides can also execute in parallel.

A priority can be derived from a hash of the search key instead of stored as a sampled value. For a fixed hash seed and collision rule, the same set of keys then produces the same treap shape regardless of insertion order.

The hash must spread priorities well enough to preserve the randomized analysis. If callers can choose keys, use a keyed hash with a secret, per-instance seed; a public, predictable hash lets an adversary search for keys that force a poor shape. Priority collisions still require a deterministic tie-breaker.

Treaps provide expected logarithmic search and updates with one priority field and a small rotation routine. Split and merge are direct consequences of the two invariants, which makes the structure useful when those operations are part of the interface. A van Emde Boas tree can answer ordered-set queries faster for bounded integers, but its direct representation depends on the size of the key universe rather than only the stored set.

Unlike AVL and red-black trees, a treap does not guarantee logarithmic height for every priority assignment. Its pointer-based layout also has weaker cache locality than flat structures such as the array-backed binary heap. A skip list offers similar randomized expected bounds with a different pointer layout.

Git’s vcs-svn import code used a pool-backed treap for large, growing sets of objects. The embedded Go key-value store gkvlite makes an immutable, copy-on-write treap its fundamental ordered index, so snapshots can share every unchanged subtree.

The SpK plasma-physics code stores a dynamically refined spectrum in a treap. It inserts extra frequency points around spectral lines as they become relevant instead of allocating a high-resolution grid everywhere. The same split-and-merge interface is useful in implicit treaps for editor-like sequence operations such as inserting a span or reversing a range.

A treap is a binary search tree over keys and a heap over independently assigned priorities. Search follows key order; insertion and deletion use rotations to restore priority order.

Random priorities give expected O(log n) search and update time, but a poor priority assignment can still create linear height. The same invariants support expected-logarithmic split and merge operations and work-efficient ordered-set operations.