Treap (Randomized Binary Search Tree)
A Treap combines a BST key with a random heap priority so split and merge run in O(log n) expected time—unlocking implicit-key range reversals, splits, and order statistics in ~30 lines of code.
Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code
Treap (Randomized Binary Search Tree)
A Treap (Tree + Heap) assigns every node a BST key and a random heap priority (prio). Because a BST ordered by key and heap-ordered by random priorities is structurally identical to inserting keys in random order, its expected height is $O(\log n)$—and every operation (insert, erase, split, join, and implicit-key subarray reversal!) reduces to just two tiny recursive primitives: split and merge!
At a Glance
| Operation | Expected Time |
| :--- | :---: |
| split(root, key) / merge(L, R) | $O(\log n)$ |
| insert / erase / kth | $O(\log n)$ |
| Implicit-Key Subarray Cut/Paste/Reverse | $O(\log n)$ |
| Auxiliary Space | $O(n)$ |
---
Practice Problems
Hard
1. Treap split, merge, insert, erase, and $k$-th Smallest
Implement a randomized Treap supporting insert, erase, and kth(k) in $O(\log n)$ expected time.
Approach: split(t, key, l, r) partitions t into keys <= key and > key; merge(l, r) joins two treaps respecting heap priorities. Maintain sz in pull(t) for $O(\log n)$ kth!
<details>
<summary>Show C++ Solution</summary>
#include <cstdint>
#include <iostream>
#include <random>
struct TNode {
int key, sz = 1;
uint32_t prio;
TNode *l = nullptr, *r = nullptr;
TNode(int k, uint32_t p) : key(k), prio(p) {}
};
int sz(TNode* t) { return t ? t->sz : 0; }
void pull(TNode* t) { if (t) t->sz = 1 + sz(t->l) + sz(t->r); }
void split(TNode* t, int key, TNode*& l, TNode*& r) {
if (!t) { l = r = nullptr; return; }
if (t->key <= key) { split(t->r, key, t->r, r); l = t; }
else { split(t->l, key, l, t->l); r = t; }
pull(t);
}
TNode* merge(TNode* l, TNode* r) {
if (!l || !r) return l ? l : r;
if (l->prio > r->prio) { l->r = merge(l->r, r); pull(l); return l; }
r->l = merge(l, r->l); pull(r); return r;
}
int kth(TNode* t, int k) {
int ls = sz(t->l);
if (k == ls + 1) return t->key;
if (k <= ls) return kth(t->l, k);
return kth(t->r, k - ls - 1);
}
void freeTreap(TNode* t) { if (!t) return; freeTreap(t->l); freeTreap(t->r); delete t; }
int main() {
std::mt19937 rng(42);
TNode* root = nullptr;
for (int x : {30, 10, 50, 20, 40}) {
TNode *l = nullptr, *r = nullptr;
split(root, x, l, r);
root = merge(merge(l, new TNode(x, rng())), r);
}
std::cout << kth(root, 1) << " " << kth(root, 3) << " " << kth(root, 5) << "\n"; // 10 30 50
freeTreap(root);
return 0;
}
</details>
---
Related Structures & Algorithms
- AVL Tree & Red-Black Tree — deterministic balanced BSTs.
- Skip List — randomized list alternative to Treap.