Data Structures
Treap (Randomized BST)
Difficulty: Advanced
Implementing a Red-Black tree from memory under interview pressure is a known-hard task; the rotation cases alone are several hundred lines of careful pointer work. A Treap reaches the same expected O(log n) height in maybe sixty lines,...
Treap (Randomized BST)
Implementing a Red-Black tree from memory under interview pressure is a known-hard task; the rotation cases alone are several hundred lines of careful pointer work. A Treap reaches the same expected O(log n) height in maybe sixty lines, with no color bits and no balance factor, by giving each node a random priority and asking the tree to satisfy two simple invariants at once.
This lesson covers the dual structure (BST order on keys, heap order on randomly assigned priorities), the proof sketch that random priorities yield expected O(log n) height because the tree is shaped like a uniform random BST, and the two operations that make treaps unusually flexible: split(key) cuts the treap into 'less than' and 'greater or equal' pieces, and merge glues two treaps together when one contains only smaller keys. From those two primitives, insert, delete, k-th element, and even range reversal fall out naturally. You will also meet the implicit treap, where positions replace keys and the result behaves like a balanced array supporting O(log n) insert-at-index and slicing.
In Binary Search Tree (BST), you saw that an unlucky insertion order produced a chain; randomized priorities solve that by making any input look balanced in expectation, the same way randomized quicksort tames adversarial pivots.
With treaps in hand, the curriculum next explores structures that exploit very different properties (such as bounded integer universes) to push performance beyond what comparison-based trees can offer.
Prerequisites:
Binary Search Tree (BST)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain how a treap combines BST and heap properties, and why random priorities yield expected O(log n) height.
Implement the split and merge primitives that form the foundation of all treap operations.
Build insert and delete operations using split and merge.
Trace treap operations on paper given a set of keys and priorities.
Describe the implicit treap concept and how it extends treaps to act as balanced arrays.
Compare treaps with AVL, Red-Black, and splay trees in terms of complexity, ease of implementation, and use cases.
Why This Matters
01
Treaps achieve expected O(log n) height through randomization alone, providing the balance guarantees of AVL or Red-Black trees without the complex rebalancing logic. This makes them significantly easier to implement correctly.
02
The split and merge primitives are extraordinarily powerful: they enable insert, delete, k-th element, range reversal, and interval operations in O(log n) expected time. This versatility makes treaps the go-to structure in competitive programming.
03
Understanding treaps deepens your grasp of randomized algorithms and probabilistic analysis -- concepts that appear throughout algorithm design, from randomized quicksort to skip lists to hash tables.
04
Implicit treaps (keyed by position rather than value) can act as balanced arrays supporting O(log n) insert-at-index, delete-at-index, and range queries -- something no standard array or linked list can do.
Key Terms
7 terms you'll encounter in this lesson
Treap
A randomized binary search tree where each node has a key (BST-ordered) and a random priority (heap-ordered). The name is a portmanteau of 'tree' and 'heap'.
Split
A treap operation that divides a treap into two treaps: one containing all keys less than or equal to a given key, and one containing all keys greater than it. Runs in O(log n) expected time.
Merge
A treap operation that combines two treaps into one, given that all keys in the first treap are less than all keys in the second. Runs in O(log n) expected time.
Priority (in treap context)
A random number assigned to each node at insertion time. Priorities satisfy the max-heap property: every node's priority is greater than or equal to its children's priorities.
Implicit Treap
A treap variant where nodes do not store explicit keys. Instead, a node's position in the in-order traversal serves as its implicit index. This allows the treap to function as a balanced array with O(log n) insert/delete at any position.
Cartesian Tree
A binary tree derived from a sequence of numbers where the root is the minimum (or maximum) element and left/right subtrees are built recursively from the subsequences to its left and right. A treap is a Cartesian tree on the priorities with BST ordering on the keys.
Expected O(log n) Height
A probabilistic guarantee meaning that for a treap with n nodes, the height is O(log n) with high probability. This follows from the fact that random priorities produce the same tree structure as a randomly ordered BST insertion sequence.
Heads Up
Common misconceptions to watch out for
"Treaps guarantee O(log n) worst-case for every operation"
Treap operations are O(log n) in expectation, not worst-case. An adversary who knows the random priorities could construct a degenerate tree. However, since priorities are chosen randomly, the probability of a badly unbalanced tree is astronomically small -- roughly 1/n! for a fully degenerate tree.
"The heap property in a treap means it works like a priority queue"
The heap property is an internal mechanism to ensure balance, not a user-facing feature. You never extract-max by priority. The priorities are random numbers assigned at insertion time; they exist solely to keep the tree balanced. The user interacts with the treap through BST operations on the keys.
"Split and merge are just convenience wrappers around rotations"
Split and merge are fundamentally different from rotations. Rotations are local operations that change the relationship between a node and its child. Split divides an entire tree into two subtrees in a single O(log n) pass. Merge combines two trees in a single O(log n) pass. They are the primary building blocks -- insert and delete are built on top of split/merge, not the other way around.
"Implicit treaps and regular treaps are the same thing with different names"
They are structurally similar but semantically different. A regular treap stores explicit keys and maintains BST order on those keys. An implicit treap stores no keys -- each node's 'key' is its position in the in-order traversal, computed on the fly from subtree sizes. This lets an implicit treap model a dynamic array with O(log n) insert/delete at arbitrary positions.