Home▸Algorithms & AI▸Treap — Randomized Balanced BST

🎲 Treap — Randomized Balanced BST

Each key in a treap gets a random priority; the tree stays a max-heap on priorities while remaining a BST on keys, giving expected O(log n) operations without explicit balancing rules.

Algorithms & AI2DAdvanced60 FPS

About Treap — Randomized Balanced BST

A treap is a randomized binary search tree that combines a BST with a heap — hence the name — introduced by Cecilia Aragon and Raimund Seidel in 1989. Each node stores a key and an independently chosen random priority. Keys satisfy the binary search tree invariant, while priorities simultaneously satisfy the max-heap invariant: every node's priority is at least as large as its children's. Because priorities are random, the resulting shape is equivalent in distribution to a BST built by inserting keys in random order, guaranteeing expected O(log n) height without deterministic balancing rules. Insertion performs an ordinary BST insert by key, assigns a random priority, then rotates the new node upward while it violates the heap property with its parent. Deletion rotates the target node downward toward whichever child holds the higher priority until it can be removed. Unlike AVL or red-black trees, which enforce balance through explicit invariants, a treap achieves balance probabilistically, and it also supports O(log n) split and merge for ordered sets.

Frequently Asked Questions

Why do random priorities give a treap expected O(log n) height?

Because each node's priority is chosen independently and uniformly at random, the tree that results from ordering nodes by priority is distributionally identical to a BST built by inserting keys in a random permutation. Random BSTs are a classical result with expected height O(log n), so treaps inherit this guarantee without needing explicit rebalancing.

How does the insertion rotation work?

A new key is first placed with an ordinary recursive BST insert, landing as a leaf with a fresh random priority. If that priority exceeds its parent's priority, the node is rotated upward — a right rotation if it is a left child, a left rotation if it is a right child. Rotations continue until the parent's priority is greater or the node becomes the root.

How does deletion "rotate down" a node?

To delete a node with two children, the algorithm rotates up whichever child has the higher priority, which pushes the target node down into the opposite subtree while keeping the max-heap property intact. This repeats until the node has at most one child, at which point it is spliced out of the tree directly.

Why do treaps avoid needing explicit balance invariants like AVL or red-black trees?

AVL and red-black trees track height or color bits per node and apply deterministic case-by-case rebalancing rules after every update. A treap instead relies on randomized priorities: because the shape only depends on random numbers, the expected height stays logarithmic automatically, with no bookkeeping and no rebalancing cases to prove correct.

⚙ Under the hood

Each key in a treap gets a random priority; the tree stays a max-heap on priorities while remaining a BST on keys, giving expected O(log n) operations without explicit balancing rules.

binary search treerandomized algorithmbalanced treedata structure

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install