Treap — Randomized Balanced BST

🎲 Treap

Randomized balanced BST

Insert

Insert key

Delete

Delete key

Stats

Node count

Tree height

Last rotation count

Rotations total

Info & Theory

A treap is a randomized binary search tree named for combining a tree with a heap, introduced by Cecilia Aragon and Raimund Seidel in 1989. Every node stores a key and an independently chosen random priority.

Dual invariant

The tree is simultaneously a BST on keys — left subtree keys are smaller, right subtree keys are larger — and a max-heap on priorities — every node's priority is at least as large as its children's priorities.

Why expected O(log n)

Because priorities are drawn uniformly at random, the shape that results from arranging nodes by priority is distributionally identical to a BST built by inserting keys in a uniformly random order. Random BSTs are a classical result with expected height O(log n), so treaps inherit that guarantee automatically — with no explicit balancing rules at all.

Insertion

Insert the key with an ordinary recursive BST insert, landing it as a leaf, and assign it a fresh random priority. Then rotate the node up — right rotation if it is a left child, left rotation if it is a right child — as long as its priority exceeds its parent's, restoring the max-heap property.

Deletion

Locate the node by key. While it has two children, rotate down: promote whichever child holds the higher priority (treating the deleted node's own priority as −∞), pushing the target node toward a leaf. Once it has at most one child, splice it out directly.

No explicit balance bookkeeping

Unlike AVL or red-black trees, which track heights or color bits and apply deterministic case-by-case rebalancing after every update, a treap needs none of that — randomness alone keeps the expected height logarithmic.

Bonus: split & merge

Treaps also support elegant O(log n) split and merge operations, which make them a popular building block for ordered sets, ropes, and persistent data structures.

About Treap — Randomized Balanced BST

Last updated: 11 July 2026

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.