Treap

Why treap matters

• Split/merge ergonomics. A treap supports Split(T, k) → (L, R) and Merge(L, R) → T in O(log n) expected, with a few dozen lines of code. Red-black and AVL split is doable but requires hundreds of lines to keep all invariants — most production code skips it. Splay trees support split/merge but lose the persistent-friendly property.
• Competitive programming. The standard choice for ordered-set problems with rank, kth-element, range-sum, and reverse-range tasks. ICPC and Codeforces solutions show implicit treaps in roughly 80 to 150 lines of C++.
• Implicit sequence ops. Implicit treaps store a sequence indexed by subtree size. Insert at position i, delete range [i, j], reverse range (using lazy propagation), and concatenate two sequences all run in O(log n) expected. The engine behind rope-style text editors and several functional list libraries.
• Persistent data structures. Path copying in a treap touches only the O(log n) nodes on the access path, giving a persistent variant in O(log n) per op with O(log n) extra space. The functional ML and Haskell communities ship persistent treaps as their default ordered map.
• Randomization replaces balancing. No color bits, no balance factors, no rotations on every update — only when a freshly inserted priority violates the heap property. Average rotations per insert is roughly 1.4.
• Hashed variant. Replace random priorities with a hash of the key; gives a unique deterministic tree shape per key set (a "hash treap"), useful for caching and proof-of-storage.

Treap invariants

• BST property on keys. For every node u, all keys in u's left subtree are less than u.key, all keys in u's right subtree are greater. Inorder traversal yields keys in sorted order.
• Min-heap property on priorities. For every node u, u.priority <= every priority in u's subtree. The root is the node with the smallest priority.
• Uniqueness theorem. Given a fixed set of (key, priority) pairs with all priorities distinct, the treap shape is unique. The root is fully determined: it is the node with the smallest priority. Left and right subtrees recurse on keys less than and greater than the root key — and within each subtree the same uniqueness applies.
• Equivalence to random BST. If priorities are drawn iid from a continuous distribution, the resulting treap has the exact distribution of a random BST built by inserting keys in priority order. Hence all results on random BST depth and rotation counts apply.
• Expected depth. The expected depth of any node is at most 2 H(n) - 2, where H(n) is the n-th harmonic number, bounded by 2 ln n + O(1). Concretely, a treap of n = 1 million nodes has expected depth ≤ 27.7.

Core operations

• Search(T, k): O(log n) expected. Standard BST search; ignore priorities.
• Insert(T, k): O(log n) expected. Draw a fresh random priority p. Insert (k, p) as a leaf via standard BST insert. If p < parent.priority, rotate up (left or right rotation depending on which child it is) until heap order is restored or it becomes the root. Expected rotations per insert is O(1).
• Delete(T, k): O(log n) expected. Locate node u with key k. While u has two children, rotate the smaller-priority child up (left rotation if right child is smaller, right rotation if left child is smaller). Eventually u has at most one child; splice it out.
• Split(T, k): O(log n) expected. Returns (L, R) where L holds all keys < k and R holds all keys >= k. Recurse: at root, if root.key < k, the root and its left subtree go to L, recurse on root.right; otherwise root and its right subtree go to R, recurse on root.left.
• Merge(L, R): O(log n) expected. Precondition: every key in L < every key in R. Compare root priorities. Smaller-priority root becomes the merge root; recurse on the appropriate side. Implementations typically use a 30-line recursive function.
• Range operations. Range-sum, range-min, range-update via lazy propagation: split at l and r, operate on the middle treap, merge back. All in O(log n) expected per range op.

Implicit treap

• Replace key with subtree size. Each node stores size = 1 + left.size + right.size. The "key" of a node becomes its inorder rank, computed implicitly from sizes.
• Position i lookup. Walk from root: if left.size == i, current node is at position i; if i < left.size, recurse left; else recurse right with i - left.size - 1. O(log n) expected.
• Insert at position i. Split at i to get (L, R), create a new single-node treap N with random priority, return Merge(Merge(L, N), R). O(log n) expected.
• Delete range [l, r]. Split at l → (A, B), split B at r - l + 1 → (C, D). Discard C, return Merge(A, D). O(log n) expected.
• Reverse range. Split out the [l, r] range, set a lazy reverse flag on the middle root, merge back. When traversing a reversed subtree, swap children and propagate the flag down. O(log n) expected per reverse, O(log n) per access amortized.
• Concatenation. Merge(A, B) concatenates two sequences in O(log(|A| + |B|)) expected. Faster than the O(n) cost of array concatenation.

Analysis cheat sheet

• Expected depth of node u. E[depth(u)] = sum over v of Pr[v is an ancestor of u] = sum over v of 1 / (|rank(u) - rank(v)| + 1). The harmonic-like sum gives 2 H_n - 2 = O(log n).
• Expected rotations per insert. O(1). The number of rotations equals the depth of the inserted node in the final tree minus its depth in the BST search path — bounded above by the new node's expected position in the heap-ordered priority list.
• Tail bound on height. Pr[height > c log n] <= 1 / n^(c-2) for sufficiently large c. With c = 4, height exceeds 4 log n with probability at most 1/n^2.
• Worst case. O(n) per op, but only on adversarial priorities. Random priorities make this event have probability O(1 / n!) over insertions of distinct keys.
• Treap of m operations. Total expected work is O(m log m). Confidence intervals: 99% of operations on a million-node treap finish within 50 comparisons.

Common misconceptions

• "Always O(log n)." Only expected. Worst-case height can be n; it just rarely happens with random priorities. If your priorities can be controlled by an adversary (e.g., they leak through timing), worst-case is achievable.
• "Needs randomness — useless without it." True for the standard analysis. Hashed treaps substitute a hash of the key for the random priority and behave like random treaps under random oracle assumptions but become deterministic.
• "Same as a random BST." Equivalent in distribution but different in operation: a treap supports decrease/increase priority and explicit deletion, where a random BST built by random insertion is fixed once built.
• "Rotations break the BST invariant." Rotations preserve inorder. They permute the heap structure but never the sorted-key sequence. Easy to verify by inspection.
• "Priorities must be integers." Any totally ordered type with low collision probability works — 64-bit floats, 128-bit hashes, or pairs (random64, insert-id).
• "Split is destructive." The standard imperative split mutates the input treap. Persistent split returns two new treaps and leaves the original intact, with O(log n) extra space (path copying).
• "Pay attention to balance factor." No balance metadata to maintain. Code is shorter than red-black or AVL by a factor of 2 to 5.

Implementation tips

• Priority generator. Use a 64-bit Mersenne Twister or PCG. Avoid time(NULL) % range — too small and predictable.
• Tie breaking. Distinct priorities are required for the uniqueness theorem. With 64-bit priorities, the probability of collision is ~n^2 / 2^64; for n = 10^9, that is ~5e-2, so use 64-bit minimum.
• Lazy propagation. For range updates and reverses, store a lazy flag per node and a push() helper that propagates and clears before each descent.
• Iterative vs recursive. Recursive code is shorter. With n = 10^6, recursion depth peaks around 50 — safe on default stack.
• Memory layout. Allocate node pools to avoid malloc churn; nodes are typically 32 to 48 bytes.