Pattern Reference
Treap (Randomized BST)
"Randomized BST with heap property. Split/merge operations. Range reverse, lazy propagation, order statistics, implicit treap."
Loading...
Deep Dive Tutorial
A treap node has a key (BST property: left < node < right) and a random priority (heap property: node.priority > children.priority). The random priorities make the tree balanced with high probability (O(log n) height). Split by key: recursively split left or right subtree depending on key comparison. Merge two treaps: always take the one with higher priority root, recurse on its subtree.
Treap with split/merge operations
class TreapNode {
constructor(key) {
this.key = key;
this.priority = Math.random();
this.left = this.right = null;
this.size = 1;
}
}
function size(node) { return node ? node.size : 0; }
function upd(node) { if (node) node.size = 1 + size(node.left) + size(node.right); }
// Split: returns [left, right] where left has keys < key, right has keys >= key
function split(node, key) {
if (!node) return [null, null];
if (node.key < key) {
const [l, r] = split(node.right, key);
node.right = l; upd(node);
return [node, r];
} else {
const [l, r] = split(node.left, key);
node.left = r; upd(node);
return [l, node];
}
}
// Merge: all keys in left must be < all keys in right
function merge(left, right) {
if (!left) return right;
if (!right) return left;
if (left.priority > right.priority) {
left.right = merge(left.right, right); upd(left); return left;
} else {
right.left = merge(left, right.left); upd(right); return right;
}
}
// Insert key: split, create node, merge back
function insert(root, key) {
const [l, r] = split(root, key);
return merge(merge(l, new TreapNode(key)), r);
}
// Kth element (1-indexed)
function kth(node, k) {
const ls = size(node.left);
if (k === ls + 1) return node.key;
if (k <= ls) return kth(node.left, k);
return kth(node.right, k - ls - 1);
}Worked Problems
target
Treap vs other ordered sets:
- Treap: randomized, expected O(log n), easy split/merge
- AVL tree: deterministic O(log n), complex rotations
- Skip list: randomized, simpler implementation than treap
- Sorted array: O(n) insert, O(log n) search — good for small n or rare inserts
Treap key operations:
- insert(key): split at key, make node, merge back — O(log n)
- delete(key): split at [key, key+1], discard middle, merge — O(log n)
- kth(k): navigate using subtree sizes — O(log n)
- rank(key): split at key, size of left part — O(log n)
In interviews: Use sorted array + binary search (splice) for simplicity. Treap is overkill unless the problem specifically requires O(log n) insert + order statistics.
- Treap: randomized, expected O(log n), easy split/merge
- AVL tree: deterministic O(log n), complex rotations
- Skip list: randomized, simpler implementation than treap
- Sorted array: O(n) insert, O(log n) search — good for small n or rare inserts
Treap key operations:
- insert(key): split at key, make node, merge back — O(log n)
- delete(key): split at [key, key+1], discard middle, merge — O(log n)
- kth(k): navigate using subtree sizes — O(log n)
- rank(key): split at key, size of left part — O(log n)
In interviews: Use sorted array + binary search (splice) for simplicity. Treap is overkill unless the problem specifically requires O(log n) insert + order statistics.