Treap: A Balanced BST Built From a Coin Flip

The problem with a plain BST

A binary search tree is only fast if it is roughly balanced. Insert keys in sorted order and a plain BST degenerates into a linked list — height n, every operation O(n). AVL trees and red-black trees fix this with rotation rules triggered by an explicit balance invariant, which works, but the case analysis for insertion and deletion is notoriously fiddly to get right. A treap (tree + heap) reaches the same expected O(log n) height with a much simpler idea: give every key a random number, and let that number do the balancing.

Two orderings, held at once

Every node stores a key and a priority drawn uniformly at random when it is inserted. The tree maintains both properties simultaneously:

BST order:   in-order traversal visits keys in sorted order
Heap order:  every node's priority >= both children's priorities

For any set of (key, priority) pairs with distinct values, exactly one tree shape satisfies both constraints — so the structure is fully determined the moment the priorities are chosen, regardless of what order the keys arrive in.

Insertion via rotations

Insert like an ordinary BST — walk down comparing keys until you find the empty spot — then restore heap order by rotating the new node upward past any parent with a smaller priority, exactly like sift-up in a binary heap but using tree rotations instead of array swaps:

function rotateRight(y) {          // y becomes right child of x
  const x = y.left;
  y.left = x.right;
  x.right = y;
  return x;                        // x is the new subtree root
}
// insert(node), then while node.priority > node.parent.priority:
//   rotate right or left depending on which child node is

Why random priorities guarantee expected O(log n) height

This is the result Raimund Seidel and Cecilia Aragon proved in 1996: a treap built from any sequence of key insertions, as long as the priorities are drawn independently at random, has the exact same probability distribution over shapes as a plain BST built by inserting those same keys in a uniformly random order. It does not matter whether the actual insertion order was sorted, reverse-sorted or adversarially chosen — the priorities alone decide the shape, and a randomly-ordered BST is well known to have expected height O(log n). The treap gets the average-case guarantee of random insertion order for free, on any input.

Split and merge: the operations that make treaps special

split(t, key) divides a treap into two treaps — everything less than key, everything greater — in O(log n), by walking down the tree once and reattaching subtrees along the way. merge(t1, t2) does the reverse: given two treaps where every key in t1 is less than every key in t2, it combines them into one, again in O(log n), by always attaching whichever root has the higher priority and recursing into the other side:

function merge(t1, t2) {
  if (!t1) return t2;
  if (!t2) return t1;
  if (t1.priority > t2.priority) {
    t1.right = merge(t1.right, t2);
    return t1;
  } else {
    t2.left = merge(t1, t2.left);
    return t2;
  }
}

Because split and merge are so mechanical, an implicit treap — one where the "key" is just an element's position in a sequence rather than a stored value — supports operations that are painful in most other balanced trees: cut a contiguous range out, reverse it, splice it back in somewhere else, all in O(log n). That is why treaps show up as the backbone of rope-like text editors and array structures needing range reversal or range shift.

Treap vs AVL vs red-black

AVL and red-black trees guarantee O(log n) height in the worst case, with no randomness involved — an adversary who sees every operation can never force bad performance. A treap only guarantees O(log n) in expectation; a run of terrible luck in the random priorities is possible, just vanishingly unlikely, and invisible to an adversary who does not know the random seed. In exchange, treap code is dramatically simpler — no color bits, no balance factors, no multi-case rotation logic for deletion — and it composes: split and merge let you build range operations, persistence and order statistics with a few extra lines rather than a redesign of the rebalancing logic.

Frequently asked questions

Try it live

Everything above runs in your browser — open Treap and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.