The Treap

Fractional CTO · Founder of Injuria.ai
The treap is a randomized binary search tree[1] data structure that maintains a dynamic set of ordered keys.[30] Its name is a portmanteau of "tree" and "heap", reflecting its dual nature: it enforces the binary search tree property on its keys and the binary heap[2] property on a set of randomly generated priorities. By combining these two structural rules, the treap achieves a balanced shape in expectation[3], ensuring that standard operations such as search, insertion, and deletion run efficiently without the complex deterministic rebalancing rules required by other self-balancing trees.
Unlike structures that track height differentials or node colors to enforce strict balance, the treap relies entirely on probability. When a node is inserted, it is assigned a random priority. The tree is then modified so that the highest priority nodes rise toward the root. Because the priorities are independent and uniformly distributed, the resulting tree shape is mathematically equivalent to a binary search tree constructed from a completely random sequence of insertions. This probabilistic approach guarantees that the tree depth remains logarithmic on average, regardless of the order in which the user inserts or deletes the keys.
The treap occupies a distinct position in computer science as a bridge between theoretical simplicity and practical utility. It supports advanced operations, such as splitting a tree into two or merging two trees into one, with minimal code complexity. These capabilities have led to its adoption in various domains, from standard library memory allocators[4] to parallel set operations and competitive programming[5]. While it does not offer the strict worst-case latency guarantees of deterministic balanced trees, its expected performance, ease of implementation, and versatility make it a fundamental data structure in algorithm design.
Core Definition and the Balancing Problem
To understand the specific problem the treap solves, one must first examine the limitations of the standard binary search tree. A binary search tree organizes comparable keys such that for any given node, all keys in its left subtree are smaller, and all keys in its right subtree are larger. This organization allows for rapid binary searches. When a tree is reasonably balanced, traversing from the root to any leaf takes time proportional to the logarithm of the number of nodes.
However, the standard binary search tree is highly sensitive to the order of insertions. If keys are inserted in already sorted or reverse-sorted order, the tree degenerates into a linear linked list. In this worst-case scenario, the depth of the tree equals the number of nodes, and basic operations degrade to linear time complexity[6]. To prevent this degradation, computer scientists developed self-balancing binary search trees, such as the AVL tree[7] and the Red-Black tree[8]. These structures maintain balance by storing additional metadata in each node, such as a height integer or a color bit, and applying deterministic rules. When an insertion or deletion violates the balance conditions, the tree performs a series of pointer rotations and metadata updates. Implementing these rules requires handling numerous edge cases, making the code difficult to write, verify, and maintain.
The treap[9] solves the balancing problem by discarding deterministic metadata in favor of randomization. Every node in a treap contains a key, a value, and a randomly generated numerical priority. The data structure enforces two invariants simultaneously. First, the keys must satisfy the binary search tree property. Second, the priorities must satisfy the heap property, meaning that the priority of any node must be greater than or equal to the priorities of its children (in a max-heap configuration).
A well-known theorem in computer science states that if a set of distinct keys and distinct priorities is given, there is exactly one valid tree structure that satisfies both the binary search tree property on the keys and the heap property on the priorities. Because the priorities are generated randomly, the shape of the treap is completely independent of the order in which the keys are inserted. The structure is identically distributed to a standard binary search tree built by inserting keys in decreasing order of their random priorities.
To prove that the expected depth of any node is logarithmic, one can analyze the probability of ancestor-descendant relationships. Let the inserted keys be sorted in ascending order, denoted as a sequence from the first key to the $n$-th key. The depth of a specific node is determined by the number of its ancestors. A node $A$ is an ancestor of a node $B$ if and only if $A$ possesses the highest priority among all nodes located between $A$ and $B$ inclusive in the sorted sequence.
The number of nodes in this contiguous range is exactly the absolute difference between their sorted indices plus one. Because the priorities are assigned randomly and independently from a uniform distribution, every node in this range has an equal probability of holding the maximum priority. Therefore, the probability that node $A$ is an ancestor of node $B$ is exactly one divided by the size of that range.
To find the expected depth of a node at index $j$, one must sum these probabilities for all possible ancestors. This summation is split into two parts: the nodes smaller than $j$ and the nodes larger than $j$. The sum of probabilities for the smaller nodes evaluates to the $j$-th harmonic number[10] minus one. The sum for the larger nodes evaluates to the $(n - j + 1)$-th harmonic number minus one. Since the harmonic number $H_k$ grows as the natural logarithm of $k$, the expected depth of any node is strictly bounded by $2 \ln n + O(1)$.[31] This mathematical guarantee ensures that the treap bypasses the need for complex rebalancing logic, achieving balance through the natural properties of random variables.
Mechanism and Algorithmic Complexity
The mechanics of a treap revolve around maintaining its two structural invariants during modifications. The fundamental building block for these modifications is the tree rotation, a constant-time operation that changes the hierarchical arrangement of nodes without violating the binary search tree property. A right rotation elevates a left child to the position of its parent, while a left rotation elevates a right child.
When a new key is inserted into a treap, the algorithm first generates a random priority for the new node using a pseudorandom number generator[11]. The node is then inserted as a leaf using the standard binary search tree insertion algorithm, traversing left or right down the tree based on key comparisons. Once the node is attached as a leaf, its priority is compared to its parent's priority. If the new node has a higher priority than its parent, the heap property is violated. To restore the invariant, the algorithm performs rotations to move the new node upward. If the new node is a left child, a right rotation is applied; if it is a right child, a left rotation is applied. This process continues until the node's priority is less than or equal to its parent's priority, or until the node becomes the root of the tree.
Deletion follows a similar but reversed logic. To delete a node, the algorithm locates it using a standard binary search. If the node is a leaf, it is simply removed. If it has one child, it is replaced by that child. If the node has two children, the algorithm compares the priorities of the two children. The child with the higher priority is rotated upward, pushing the target node down a level. This process is repeated until the target node becomes a leaf or has only one child, at which point it is removed from the tree.
The true flexibility of the treap lies in its split and merge operations, which operate top-down and eliminate the need for bottom-up rotations entirely. The split operation takes a treap and a threshold key, dividing the treap into two separate treaps. One resulting treap contains all keys less than or equal to the threshold, and the other contains all keys strictly greater. The merge operation takes two treaps, where the maximum key in the first is less than the minimum key in the second, and combines them into a single valid treap.
// Pseudocode for top-down split and merge operations
Node* merge(Node* left, Node* right) {
if (left == NULL) return right;
if (right == NULL) return left;
if (left->priority > right->priority) {
left->right = merge(left->right, right);
return left;
} else {
right->left = merge(left, right->left);
return right;
}
}
void split(Node* root, int threshold, Node** out_left, Node** out_right) {
if (root == NULL) {
*out_left = NULL;
*out_right = NULL;
return;
}
if (root->key <= threshold) {
*out_left = root;
split(root->right, threshold, &root->right, out_right);
} else {
*out_right = root;
split(root->left, threshold, out_left, &root->left);
}
}
Using split and merge, insertion and deletion can be implemented without explicit rotations. To insert a node, the tree is split at the new node's key, and the three components (the left tree, the new node, and the right tree) are merged back together. To delete a node, the tree is split to isolate the target node, and the remaining left and right subtrees are merged.
In terms of algorithmic complexity, the expected time for search, insertion, deletion, split, and merge operations is $O(\log n)$, where $n$ is the number of nodes.[30] The worst-case time complexity is $O(n)$, which occurs if the random priorities happen to be ordered such that the keys, when sorted by priority, are in strictly increasing or decreasing order, causing the tree to degenerate into a linked list. However, the probability of this worst-case scenario is astronomically small for large values of $n$. The space complexity of the treap is $O(n)$, as each node requires storage for its key, value, priority, and two child pointers.
Discovery and Historical Context
The treap was formalized and introduced to the computer science community by Raimund Seidel and Cecilia R. Aragon. They first presented the data structure in 1989 at the 30th Annual IEEE Symposium on Foundations of Computer Science in a paper titled "Randomized Search Trees"[12]. They later expanded on their findings in a comprehensive journal article published in Algorithmica[13] in 1996. Seidel and Aragon were affiliated with the University of California, Berkeley, during the initial development of the algorithm. Their motivation was to find a simpler alternative to deterministic balanced trees that could provide optimal expected behavior without the overhead of maintaining complex balance invariants.
The structural foundation of the treap relies heavily on prior art, specifically the Cartesian tree[14], which was introduced by Jean Vuillemin in 1980[15]. Vuillemin defined a Cartesian tree as a binary tree derived from a sequence of points consisting of X and Y coordinates. The tree is constructed such that it satisfies the binary search tree property on the X coordinates and the heap property on the Y coordinates. Seidel and Aragon's breakthrough was the realization that by artificially generating random values for the Y coordinates, they could force a Cartesian tree to behave as a highly efficient, self-balancing search tree.
Following its introduction, the treap became a subject of extensive study, leading to several refinements. In 1998, Guy E. Blelloch and Margaret Reid-Miller published "Fast Set Operations Using Treaps"[16] at the ACM Symposium on Parallel Algorithms and Architectures. They demonstrated that the treap's split and merge operations could be utilized to perform parallel set operations, such as union, intersection, and difference. Blelloch and Reid-Miller's algorithm for computing the union of two treaps works by taking the root of the first treap and using its key to split the second treap into two subtrees. The algorithm then recursively computes the union of the left subtrees and the right subtrees. Because these two recursive calls operate on strictly disjoint subsets of the key space, they can be executed simultaneously on separate processors. Blelloch and Reid-Miller proved that these parallel algorithms achieved optimal work bounds, running in expected $O(m \log(n/m))$ work and $O(\log n)$ depth for sets of size $n$ and $m$.
Important Variants
The fundamental mechanics of the treap have been adapted to create several specialized variants, each solving distinct computational problems.
The most widely used variant is the implicit treap[17], sometimes referred to as a treap with implicit keys. In a standard treap, the binary search tree property is maintained using explicit keys provided by the user. In an implicit treap, the explicit keys are removed entirely. Instead, the logical key of a node is defined implicitly by its index in a sequence. This index is calculated dynamically by maintaining a size field in each node that records the total number of nodes in its subtree. When traversing the tree, the algorithm determines a node's index by looking at the size of its left subtree.
This modification transforms the treap into a powerful dynamic array. It supports inserting an element at any arbitrary index, deleting an element from any index, and querying or modifying ranges of elements, all in expected $O(\log n)$ time. For example, an implicit treap can reverse a sub-array of elements in logarithmic time by maintaining a boolean reverse flag on nodes and lazily propagating it downward. This lazy propagation technique is frequently used in competitive programming[18] to solve complex string and sequence manipulation problems that would otherwise require linear time per operation.
Another significant variant is the persistent treap. Persistent data structures[19] preserve previous versions of themselves when modified, allowing access to historical states. Because the top-down split and merge operations of a treap only modify nodes along the search path, it is straightforward to implement a persistent version using a technique called path copying. Instead of mutating the child pointers of existing nodes, the split and merge functions allocate new nodes that copy the state of the original nodes, sharing the unmodified subtrees with previous versions. The randomized nature of the treap ensures that the expected number of newly allocated nodes per operation remains $O(\log n)$, making it an efficient choice for functional programming languages and versioned databases.
In 2009, Daniel Golovin introduced the B-Treap at the International Colloquium on Automata, Languages, and Programming, later refining it into the B-Skip-List[20]. The B-Treap extends the treap concept to B-trees[21], optimizing it for external memory and disk-based storage where block transfers dictate performance. The primary contribution of the B-Treap is its strong history independence. A data structure is strongly history-independent if its memory layout is entirely determined by its current logical contents, revealing no information about the chronological sequence of operations that produced it.[31]
If an attacker inspects the memory layout of a standard deterministic tree, they might deduce the order in which records were inserted. Because a treap's shape is uniquely determined by its keys and priorities, it naturally resists this forensic analysis. To achieve strict history independence, Golovin's B-Treap replaces the random number generator with a pseudorandom function keyed by the inserted item.[32] This guarantees that a specific set of items will always produce the exact same priorities and tree shape, satisfying stringent security and privacy requirements for filesystems and databases.
Real-World Applications and Implementations
While deterministic trees like the Red-Black tree dominate standard libraries in languages such as C++ and Java, the treap has found adoption in systems that benefit from its specific probabilistic and structural properties.
The Zig programming language[22] utilizes a treap in its standard library (std.Treap). Specifically, the treap is currently employed within Zig's GeneralPurposeAllocator (it was originally added for std.Thread.Futex) to manage memory buckets and is actively used to manage wait queues in std.Thread.Futex. When an allocator processes memory addresses, the inputs are often highly ordered, corresponding to sequential operating system pages. Deterministic trees can suffer from excessive rotation overhead when fed sequential data. By assigning random priorities to the memory blocks, the Zig allocator ensures that the tree remains balanced without predictable degradation, reducing the time complexity of searching for available buckets from linear to logarithmic time.
In the C++ ecosystem, the Boost C++ Libraries provide treap implementations within the Boost.Intrusive module. The library offers treap_set and treap_multiset[23], which allow developers to store objects in a balanced structure without allocating separate node containers. Intrusive containers require the user to embed the tree node pointers directly into their own data structures. Boost allows the user to provide the priority comparison function, meaning priorities can be computed on the fly via hashing rather than stored explicitly, reducing the memory overhead of the structure.
Treaps are also deployed in specialized database architectures and caching layers. In 2026, researchers Seobum Jeong and Simon S. Woo presented the Treap-Augmented Skip List (TASL) at the ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Skip lists[24] are widely used in production databases like Redis[25] and RocksDB[26], but they incur unnecessary traversal overhead for frequently accessed keys under skewed Zipfian workloads[27]. TASL places an external treap as a hot-tier cache above an unmodified skip list. By utilizing the treap to manage the most frequently accessed elements, the system optimizes point lookup performance for skewed workloads while delegating range queries to the underlying skip list.
Recent advancements in machine learning have utilized the treap architecture to create learning-augmented search trees. Research published at the International Conference on Machine Learning in 2022 by Honghao Lin, Tian Luo, and David P. Woodruff demonstrated how to optimize access time by replacing the treap's random priorities with priorities derived from machine learning predictions (Learning Augmented Binary Search Trees[28]). In 2025, Jingbang Chen, Xinyuan Cao, Alicia Stepin, and Li Chen expanded this approach to arbitrary input distributions (On the Power of Learning-Augmented Search Trees[29]). They assigned each item a composite priority calculated as the negative floor of the double logarithm of the inverse of its predicted weight plus a uniform random variable. By predicting the access frequency of items and assigning higher priorities to frequently accessed keys, the treap naturally shifts hot items closer to the root. This approach achieves static optimality, meaning the tree performs as efficiently as the best possible custom-tailored search tree for a given access distribution.
Significance and Tradeoffs
The treap holds significant educational and practical value because it decouples the problem of maintaining binary search tree order from the problem of maintaining tree height. By delegating the balancing act to a random number generator and a standard heap property, the treap eliminates the need to track balance factors, calculate height differentials, or memorize complex rotation cases. The entire data structure can be implemented in a few dozen lines of code using the symmetric split and merge functions. This simplicity drastically reduces the surface area for software bugs, making the treap highly favored in environments where developers must implement structures from scratch.
However, the reliance on randomness introduces specific tradeoffs. The $O(\log n)$ time complexity for operations is an expected bound, not a strict worst-case guarantee. In hard real-time systems, such as aviation control software or high-frequency trading platforms, worst-case execution time must be strictly bounded. A treap cannot guarantee that an operation will not occasionally take $O(n)$ time if the random number generator produces a highly skewed sequence of priorities. In these strict environments, deterministic structures like the AVL tree are mandatory.
Additionally, the treap incurs a constant-factor overhead in both memory and computation. Each node must store an extra integer or floating-point number for the priority, which increases the memory footprint compared to a Red-Black tree that only requires a single color bit per node. In programming languages with memory alignment padding, this extra field can increase the node size by up to eight bytes. Computationally, generating a high-quality random number during every insertion consumes CPU cycles. If the underlying pseudorandom number generator is slow, the cost of generating priorities can outweigh the performance benefits of simplified balancing.
Finally, like all standard binary search trees, the treap suffers from poor cache locality compared to array-based structures like B-trees. Traversing a treap requires following pointers that may be scattered arbitrarily across the heap, leading to frequent CPU cache misses. Engineers must weigh the simplicity and flexibility of the treap against the strict guarantees, memory efficiency, and cache performance of deterministic alternatives when designing production systems.
Sources (32)
- Wikipedia: binary search tree
- Wikipedia: binary heap
- Wikipedia: expectation
- Wikipedia: memory allocators
- Wikipedia: competitive programming
- Wikipedia: time complexity
- Wikipedia: AVL tree
- Wikipedia: Red-Black tree
- Wikipedia: treap
- Wikipedia: harmonic number
- Wikipedia: pseudorandom number generator
- "Randomized Search Trees"
- *Algorithmica*
- Wikipedia: Cartesian tree
- 1980
- "Fast Set Operations Using Treaps"
- implicit treap
- competitive programming
- Wikipedia: Persistent data structures
- B-Skip-List
- Wikipedia: B-trees
- Zig programming language
- `treap_set` and `treap_multiset`
- Wikipedia: Skip lists
- Redis
- RocksDB
- Wikipedia: Zipfian workloads
- Learning Augmented Binary Search Trees
- On the Power of Learning-Augmented Search Trees
- Michael Backes, Peng Ning, Computer Security -- ESORICS 2009 (Springer Science & Business Media, 2009)
- Pat Morin, Subhash Suri, Algorithms and Data Structures (Springer Nature, 2023)
- Günther Pernul, Peter Y A Ryan, Edgar Weippl, Computer Security -- ESORICS 2015 (Springer, 2015)