Pattern Guide
Treap & Ordered Set
"BST + heap priorities. Split and merge in O(log n). Dynamic order statistics."
A treap is a randomized binary search tree that maintains heap property on random priorities. It supports split (divide by key) and merge (combine two treaps) in O(log n) expected time. This enables: insert/delete in O(log n), k-th element, rank queries, range operations. In JavaScript, use a sorted array + binary search for interview problems; treap for competitive programming.
Problems you can solve with this pattern
4 problems · click any to start solving
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);
}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.
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);
}- 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.