Treap

Treap (a portmanteau of tree and heap) is a randomized self-balancing binary search tree within computation and algorithms that maintains dynamic ordered sets in O(log n) expected time per search, insertion, deletion, split, and join operation. Introduced by Raimund Seidel and Cecilia R. Aragon in 1989 (and structurally isomorphic to the Cartesian tree defined by Jean Vuillemin in 1980), a treap assigns each inserted node x both a user-supplied comparable search key k(x) and an independent, uniformly distributed random priority p(x).

By enforcing the binary search tree invariant on keys (every left descendant has a smaller key and every right descendant has a larger key) together with the heap invariant on priorities (every child has a priority no larger than its parent in a max-treap), a treap ensures that its tree topology is uniquely determined whenever all keys and priorities are distinct. Specifically, the root of any subtree must be the node with the maximum priority, which partitions the remaining elements by key into left and right subtrees—the exact recursive partition generated by inserting the keys into an unbalanced binary search tree in decreasing order of their random priorities. Because the priorities are chosen uniformly at random independent of the input key order, a treap transforms any adversarial sequence of insertions (such as pre-sorted keys) into a uniform random permutation, achieving O(log n) expected height with high probability without complex deterministic rebalancing cases.

Dual Tree-Heap Invariant and Cartesian Tree Isomorphism

Let S = {(k₁, p₁), (k₂, p₂), …, (k_n, p_n)} be a set of n pairs with distinct keys k_i and distinct priorities p_i. A binary tree T storing S is a max-treap if, for every node u ∈ T:

1. Binary Search Tree Property (Keys): For every node v in the left subtree of u, k(v) < k(u); for every node w in the right subtree of u, k(w) > k(u).
2. Max-Heap Property (Priorities): For every child c of u, p(c) < p(u).

By induction on n, there exists a unique treap T(S) for any set S with distinct keys and priorities: the root of T(S) must be the unique element r = arg max_x∈S p(x) by the heap property, the left subtree must store S_< = {x ∈ S : k(x) < k(r)} by the binary search tree property, and the right subtree must store S_> = {x ∈ S : k(x) > k(r)}. Consequently, the shape of a treap is history-independent: regardless of the sequence of insertions and deletions that produced the current set S, the treap's structure is identical to the binary search tree obtained by inserting the elements of S in decreasing order of priority.

Expected Depth and Rotation Count via Indicator Variables

Rank the n elements of S in increasing order of their keys as x₁, x₂, …, x_n with k(x₁) < k(x₂) < … < k(x_n), and define the indicator random variable A_i,j ∈ {0, 1} to equal 1 if and only if x_i is a proper ancestor of x_j in the treap. Under the random priority insertion equivalence (identical to the pivot selection analysis of Quicksort), x_i is an ancestor of x_j if and only if x_i is assigned the highest priority among all elements in the contiguous key interval {x_min(i,j), …, x_max(i,j)}. Because priorities are independent and identically distributed, each of the |i − j| + 1 elements in that interval is equally likely to have the maximum priority:

By linearity of expectation, the expected depth of the j-th ranked key x_j is the sum of ancestor probabilities over all i ≠ j:

where H_m = ∑_r=1..m 1/r ≈ ln m + γ is the m-th harmonic number. Furthermore, the expected number of tree rotations performed during any single insertion or deletion equals the expected sum of the right-spine length of the left subtree and the left-spine length of the right subtree of the affected node, which satisfies E[rotations] < 2.

Split and Join Primitives

In modern functional and competitive programming, treaps are most often implemented using two non-rotational structural primitives—Split and Merge (Join)—each running in O(log n) expected time:

• Split(T, k): Partitions a treap T into two treaps (L, R) such that L contains all nodes with keys ≤ k and R contains all nodes with keys > k. If k(root(T)) ≤ k, recursively split the right child of T into (L', R), attach L' as the new right child of root(T), and return (T, R); otherwise split the left child symmetrically.
• Merge(L, R): Given two treaps L and R where every key in L is strictly smaller than every key in R, combines them into a single treap. Compare p(root(L)) and p(root(R)): if p(root(L)) > p(root(R)), make root(L) the new root and recursively set its right child to Merge(L.right, R); otherwise make root(R) the new root and set its left child to Merge(L, R.left).

Using Split and Merge, inserting a new node x splits T at k(x) into (L, R) and returns Merge(Merge(L, x), R), while deleting k splits out the target key and merges the remaining left and right halves. Alternatively, rotation-based insertion inserts x as a leaf using standard binary search tree key comparisons and rotates x upward until p(x) ≤ p(parent(x)), while deletion rotates x downward toward the higher-priority child until it becomes a leaf and detaches it.

Implicit Treaps for Dynamic Sequence Manipulation

Replacing explicit keys with implicit array indices calculated dynamically from subtree sizes (size[u] = 1 + size[left(u)] + size[right(u)]) yields an implicit treap (or randomized rope). Because Split(T, pos) can cleave a sequence of n elements at any index pos in O(log n) expected time, an implicit treap supports inserting or deleting arbitrary substrings, cutting and pasting blocks, reversing any contiguous subarray [l, r] via lazy propagation flags, and querying range sums or range minimums in O(log n) expected time per operation.

Persistent and Parallel Set Algebra (Blelloch & Reid-Miller)

Because Split and Merge modify only the O(log n) nodes along a single root-to-leaf spine without parent pointers or bottom-up color flips, treaps are naturally suited for path-copying persistence in purely functional programming languages. Furthermore, Guy Blelloch and Margaret Reid-Miller (1998) demonstrated that two treaps of sizes m and n (with m ≤ n) can compute their set union, intersection, and difference in O(m log(n/m)) expected work and O(log n) parallel span by splitting the tree with the smaller root priority by the key of the larger root priority and recursing on the resulting left and right subtrees in parallel.

How does a treap differ from a binary heap or a standard binary search tree?

A binary heap enforces only the heap ordering on a single key and stores elements in a complete binary tree array, supporting O(1) find-max and O(log n) extract-max but requiring O(n) time to search for an arbitrary key. A standard binary search tree enforces left-to-right key ordering for fast searches but can degenerate into an O(n) linked list when keys are inserted in sorted order. A treap stores two values per node—a search key ordered as a binary search tree and a random priority ordered as a heap—combining logarithmic search by key with logarithmic tree height.

Can an attacker force a treap into O(n) worst-case height if they know the input keys?

If the treap generates priorities using a cryptographically or statistically independent pseudo-random number generator (PRNG) seeded at runtime and hidden from the external caller (oblivious adversary), no input key sequence—sorted, reverse-sorted, or alternating—can degrade the expected O(log n) depth, because the priorities are independent of the keys. Only if an attacker can inspect internal priority values or predict a deterministic hash function p(x) = hash(k(x)) can they selectively insert colliding high-priority keys.

Why is the expected number of rotations per treap insertion strictly less than 2?

During a rotation-based insertion, a newly inserted leaf x rotates upward once for each ancestor on its search path whose priority is smaller than p(x). After insertion completes, the exact number of upward rotations performed equals the sum of the number of nodes on the right spine of x's left subtree and the left spine of x's right subtree. Averaged over the uniform random priority of x_j, the expected spine lengths sum to 2 − 1/j − 1/(n − j + 1) < 2, matching the constant amortized structural modification cost of red–black trees and contrasting with the O(log n) rotations per access in a splay tree.

1. Seidel, R., & Aragon, C. R. (1996). "Randomized search trees." Algorithmica, 16(4–5), 464–497 (preliminary version in FOCS 1989, 540–545). https://doi.org/10.1007/BF01940876
2. Vuillemin, J. (1980). "A unifying look at data structures." Communications of the ACM, 23(4), 229–239. https://doi.org/10.1145/358841.358852
3. Blelloch, G. E., & Reid-Miller, M. (1998). "Fast set operations using treaps." In Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '98), 16–26. https://doi.org/10.1145/277651.277660
4. Motwani, R., & Raghavan, P. (1995). Randomized Algorithms (Section 8.2: Randomized Search Trees). Cambridge University Press. https://doi.org/10.1017/CBO9780511814075