Treap
A randomized BST built from split and merge, with order statistics and clean structural recursion.
Treap
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
The treap is the balanced binary search tree I find easiest to turn into contest code. It combines two invariants: the keys satisfy the binary-search-tree order, while random priorities satisfy the heap order.
That combination gives a tree that behaves like a random BST. In practice, it means I get split and merge almost for free, which is why treaps show up in ordered sets, implicit sequences, and many ``cut this interval, move that interval'' problems.
When to Use It
Use it when:
you need an ordered set with insert and erase,
split and merge are the cleanest primitive operations,
an implicit sequence representation would be useful later,
you want randomized balancing instead of amortized balancing.
If the task only needs an ordinary ordered set, the STL may already be enough. Treaps become attractive when you need direct control of the tree structure itself.
Core Idea
Each node stores:
a key for BST order,
a random priority for heap order.
So the inorder traversal is sorted by key, while priorities decrease from parent to child.
The useful consequence is that once priorities are fixed, the treap shape is determined. Random priorities make that shape behave like a randomly built BST, which keeps the expected height logarithmic.
Key Insight
The treap is easiest to reason about through split and merge, not through raw rotations.
split(root, key) returns two treaps: keys \(< key\) and keys \(\ge key\),
merge(left, right) assumes all keys in the left treap are smaller and rebuilds one valid treap.
Once those two routines are correct, insert and erase are usually only a few lines of logic around them.
Operations / Main Technique
The standard ordered-set version supports:
split,
merge,
insert,
erase,
kth or order-statistic queries if subtree sizes are stored.
Worked example.
To insert \(x\), split by \(x\), create one node with key \(x\), then merge left + node + right. To erase \(x\), find the node, remove it, and merge its left and right children back together.
That is why treaps feel modular: the balancing is hidden inside merge rather than spread throughout many case splits.
Correctness Intuition
BST order is preserved because split partitions keys correctly and merge is only called when every key in the left treap is smaller than every key in the right treap.
Heap order is preserved because merge always picks the root with higher priority, then recursively merges the remaining subtree on the correct side. Since both subtrees were already valid treaps, the combined result is a valid treap too.
Complexity Analysis
With random priorities:
split, merge, insert, erase, kth: \(O(\log n)\) expected,
memory: \(O(n)\).
The worst case still exists, but randomized priorities make it unlikely enough for normal contest use.
Implementation
The reference code keeps:
explicit node pointers,
random priorities,
subtree sizes,
split / merge,
insert / erase / kth.
That is the version I like as a base because it scales naturally to implicit treaps, where indices replace keys and interval operations become split/merge chains.
Common Pitfalls
Forgetting to pull subtree size after recursive changes.
Merging trees whose key ranges overlap.
Using a weak random source and then trusting the shape too much.
Mixing ``duplicates allowed'' and ``unique keys'' rules halfway through the implementation.
Writing implicit-treap code before the plain ordered-set version feels stable.
Variants / Extensions
implicit treap for sequence manipulation,
lazy tags for range reverse, range add, or range assign,
treap with duplicate counts,
persistent treap variants,
union of two treaps in \(O(m \log(n/m))\) expected time.
Compared with splay trees, treaps are randomized rather than amortized. I usually reach for treap first when I want something predictable to code quickly, and for splay when I specifically want access-based restructuring or link-cut trees later.
Practice Problems
Ordered set with insert, erase, predecessor, successor, and k-th queries.
Cut-and-paste sequence problems with an implicit treap.
Interval reverse or rotate operations after adding lazy tags.
References
Code
Contest-ready reference implementation for the idea explained above.
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
struct Treap {
struct Node {
int key, prior, sz;
Node *left, *right;
explicit Node(int key_)
: key(key_), prior((int)rng()), sz(1), left(nullptr), right(nullptr) {}
};
using Ptr = Node*;
Ptr root = nullptr;
static int size(Ptr node) { return node ? node->sz : 0; }
static void pull(Ptr node) {
if (!node) return;
node->sz = 1 + size(node->left) + size(node->right);
}
static void split(Ptr node, int key, Ptr& left, Ptr& right) {
if (!node) {
left = right = nullptr;
} else if (node->key < key) {
split(node->right, key, node->right, right);
left = node;
pull(left);
} else {
split(node->left, key, left, node->left);
right = node;
pull(right);
}
}
static Ptr merge(Ptr left, Ptr right) {
if (!left || !right) return left ? left : right;
if (left->prior > right->prior) {
left->right = merge(left->right, right);
pull(left);
return left;
}
right->left = merge(left, right->left);
pull(right);
return right;
}
bool contains(int key) const {
Ptr cur = root;
while (cur) {
if (cur->key == key) return true;
cur = key < cur->key ? cur->left : cur->right;
}
return false;
}
void insert(int key) {
if (contains(key)) return;
Ptr left, right;
split(root, key, left, right);
root = merge(merge(left, new Node(key)), right);
}
static Ptr erase(Ptr node, int key) {
if (!node) return nullptr;
if (node->key == key) {
Ptr merged = merge(node->left, node->right);
delete node;
return merged;
}
if (key < node->key) node->left = erase(node->left, key);
else node->right = erase(node->right, key);
pull(node);
return node;
}
void erase(int key) {
root = erase(root, key);
}
static int kth(Ptr node, int k) {
int left_size = size(node->left);
if (k == left_size + 1) return node->key;
if (k <= left_size) return kth(node->left, k);
return kth(node->right, k - left_size - 1);
}
int kth(int k) const {
return kth(root, k);
}
static int order_of_key(Ptr node, int key) {
if (!node) return 0;
if (key <= node->key) return order_of_key(node->left, key);
return size(node->left) + 1 + order_of_key(node->right, key);
}
int order_of_key(int key) const {
return order_of_key(root, key);
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.