↩ back to Probabilistic

Treap

A treap is a binary search tree fused with a heap: every node holds a search key, ordered left-to-right exactly like any BST, and a priority, ordered top-to-bottom like a max-heap — the root always holds the highest priority in the tree. AVL and red-black trees bound height by enforcing an explicit shape rule after every write; a splay tree gives up any shape rule and instead deliberately restructures on every access, even a read. A treap does neither: give each newly-inserted key a priority drawn uniformly at random, and the heap property alone — no rule about subtree heights, no color bits, nothing that looks at more than one node's priority at a time — turns out to keep the tree balanced in expectation, because a uniformly random priority assignment produces exactly the same distribution of shapes as if the keys had been inserted into a plain BST in random order, regardless of what order the caller actually inserts them in. That's the same randomization-does-the-work idea Skip List (this page's sibling in Probabilistic) uses via coin-flipped levels instead of tree rotations — a treap keeps the tree shape, just decides it randomly rather than deterministically.

Try it

The tree below was loaded by inserting 1 through 7 in ascending order — the exact same sequence splay-tree.html's own loaded demo uses to produce a full height-7 chain (a plain unbalanced BST given the same ascending input always does the same thing, since insertion order and BST-descent order are identical). Here, with real random priorities attached (shown in small type under each value), the same seven values land at height 4 instead — checked against the shipped algorithm below, not hand-picked. Try deleting 4, the current root: delete trickles a node down by rotating toward whichever child has the higher priority, and 5's priority (0.968) beats 1's (0.627), so 5 rotates up to become the new root. Try searching for 6 afterward and watch nothing move at all — search is a plain, unrestructured BST walk, the one place a treap and a splay tree do something completely different for the identical operation. Insert something new and watch it bubble up only as far as its own freshly-drawn priority carries it — priorities are real, live Math.random() draws from here on, not the seeded sequence that built the loaded tree (the same live-honesty rule Skip List's own page follows for its coin flips).

Insert, search, delete

Search is a plain BST descent by key comparison, nothing more — no priority is ever consulted, and nothing rotates, on a hit or a miss.

Insert walks down like an ordinary BST insert and attaches a new leaf where the walk falls off the tree, then draws that leaf a fresh random priority and bubbles it up: while the new node's priority exceeds its parent's, rotate at the parent (right if the new node is a left child, left if it's a right child) and check again. This is exactly one zig step at a time — never a two-level zig-zig/zig-zag lookahead like a splay tree's splay, because a treap only ever needs to fix the single heap-order violation the new leaf itself created, not deliberately walk all the way to the root. If the key already exists, nothing is attached or rotated; the existing node is left exactly where it is, since (unlike a splay tree) a treap's shape doesn't depend on which keys were recently searched for.

Delete finds the target by plain BST descent, then trickles it down: while it still has two children, rotate at the target itself toward whichever child holds the higher priority (that child's rotation brings it up and pushes the target down one level, on the other side), and repeat. Once the target has at most one child, splice it out directly — attach its remaining child (or nothing) in its place. Trickling toward the higher-priority side at each step is what keeps the heap property intact everywhere else in the tree; trickling toward the lower-priority side instead would still remove the right key, but would leave a real heap-order violation behind (see Pitfalls).

Reference implementation

class Treap {
  constructor(rng = Math.random) {
    this.root = null;
    this.rng = rng;                                    // () => number in [0, 1)
  }

  #rotateRight(x) {
    const y = x.left;
    x.left = y.right;
    if (y.right !== null) y.right.parent = x;
    y.parent = x.parent;
    if (x.parent === null) this.root = y;
    else if (x === x.parent.left) x.parent.left = y;
    else x.parent.right = y;
    y.right = x;
    x.parent = y;
  }

  #rotateLeft(x) {
    const y = x.right;
    x.right = y.left;
    if (y.left !== null) y.left.parent = x;
    y.parent = x.parent;
    if (x.parent === null) this.root = y;
    else if (x === x.parent.left) x.parent.left = y;
    else x.parent.right = y;
    y.left = x;
    x.parent = y;
  }

  insert(value) {
    if (this.root === null) {
      this.root = { value, priority: this.rng(), left: null, right: null, parent: null };
      return;
    }
    let cur = this.root, last = null;
    while (cur !== null) {
      last = cur;
      if (value === cur.value) return;                 // duplicates ignored
      cur = value < cur.value ? cur.left : cur.right;
    }
    const z = { value, priority: this.rng(), left: null, right: null, parent: last };
    if (value < last.value) last.left = z; else last.right = z;
    let x = z;
    while (x.parent !== null && x.priority > x.parent.priority) {
      if (x === x.parent.left) this.#rotateRight(x.parent);
      else this.#rotateLeft(x.parent);
    }
  }

  search(value) {
    let cur = this.root;
    while (cur !== null) {
      if (value === cur.value) return true;
      cur = value < cur.value ? cur.left : cur.right;
    }
    return false;
  }

  delete(value) {
    let cur = this.root;
    while (cur !== null && cur.value !== value) cur = value < cur.value ? cur.left : cur.right;
    if (cur === null) return false;
    while (cur.left !== null && cur.right !== null) {
      if (cur.left.priority > cur.right.priority) this.#rotateRight(cur);
      else this.#rotateLeft(cur);
    }
    const child = cur.left !== null ? cur.left : cur.right;
    if (child !== null) child.parent = cur.parent;
    if (cur.parent === null) this.root = child;
    else if (cur.parent.left === cur) cur.parent.left = child;
    else cur.parent.right = child;
    return true;
  }
}

The interactive demo above uses equivalent insertTreap/searchTreap/ deleteTreap functions with extra bookkeeping to record the descent path and which rotations fired, purely to drive the highlighting and log text — the algorithm is identical, including the parent pointers this needs for the same reason a splay tree does: delete's rotate-toward-the- higher-priority-child loop, like a splay's zig-zig lookahead, only makes sense relative to a node's own children, and splicing out the low end needs to reach back up to a parent afterward.

Verified against a plain JavaScript Set as a reference model across 300 randomized trials of 40 mixed insert/search/delete operations each on a deliberately small value range (to force heavy collisions between inserts, no-op duplicate inserts, and deletes of both present and absent values), checking after every single operation, 12,000 checks total with zero mismatches: the BST ordering property, the heap-order property between every parent and child, that every node's parent pointer matches its actual position in the tree, that size() matches the Set's size, and that every value the Set holds is actually reachable by search. The checker was self-tested against a deliberately broken rotation first — dropping the child's reattached parent pointer from #rotateLeft — and caught it on the very first rotation that fired, before trusting a clean run on the real code. Re-verified by extracting the exact shipped insertTreap/searchTreap/deleteTreap functions out of the HTML and re-running an equivalent pass directly against them, plus a real click-driven fake-DOM harness confirming the two worked examples named above (the 1-through-7 ascending load lands at height 4, not 7; deleting 4 promotes 5 to root). See /tmp/treap/ref.js, /tmp/treap/stress.js, and /tmp/treap/height_table.js, scratch, not committed.

Pitfalls

A valid heap order doesn't mean a balanced tree — only a genuinely random priority draw earns that. The whole balance guarantee rests on priorities being independent and uniform, not merely internally consistent. Checked, not just asserted: assign priorities equal to insertion order instead of drawing them randomly (node i gets priority i, so each new insert automatically outranks everything already in the tree) and insert 1 through 7 ascending, the identical sequence the loaded demo above uses. The heap property holds at every parent-child pair — the checker above would call this tree valid — and yet the result is a full height-7 chain, the exact same shape a plain BST or an un-splayed splay tree produces from the same ascending input. A treap with a monotonic, insertion-order-correlated priority source is really just a BST wearing a heap-shaped costume: internally consistent, structurally unbalanced.

Trickling toward the wrong child on delete still removes the key, but silently corrupts the heap property elsewhere. Skip the priority comparison in delete's loop and always rotate toward, say, the left child regardless of which side actually has the higher priority: the target still ends up spliced out correctly, and every value that was findable before is still findable after, so a checker that only re-runs search against every remaining key would report success. What it misses is that the rotation just performed can leave a child with a higher priority than its new parent — a real heap-order violation, undetectable by BST-order or search-agreement checks alone, exactly the class of bug the verification above catches only because it walks every parent-child pair and checks priorities directly, not just values.

"Expected O(log n)" is a real, computed number, not an assumption — and it only approaches the ideal as n grows, it doesn't start there. Built random treaps (random insertion order, one fresh random priority per key) at four sizes and measured average height against log₂(n) directly:

The ratio to log₂(n) climbs slowly toward a known constant (a random BST's expected height is Θ(log n) with a leading constant near 4.311 in natural-log terms) rather than sitting flat — a treap's balance is a genuine limiting behavior, not something that's already tight at small n. And "expected" is exactly that: nothing stops an unlucky draw of priorities from producing a bad tree, the same honest "randomization removes the need for an adversary, only bad luck" point quicksort's random-pivot Pitfalls section and Skip List's own Pitfalls both make about their own worst cases — a treap's is just as real, and just as vanishingly unlikely for a genuinely uniform priority source.

Where treaps show up

• Implicit treaps for array operations, in competitive programming. Drop the search key entirely and instead let a node's position in the in-order walk be its index — the priority alone still decides shape. Splitting a treap into "everything before index k" / "everything from k on" and merging two treaps back together are both O(log n), which turns an ordinary array into a structure supporting insert-in-the-middle, delete-a-range, and even reverse-a-range, all in O(log n), none of which a plain array offers.
• Cartesian trees, and the range-minimum-query trick built on them. Build a treap-shaped tree over an array where priority is the array value itself (min-heap ordered) and the in-order walk is the array's original index order — that's exactly a Cartesian Tree, and the lowest common ancestor of two indices in that tree is always the range minimum between them. Notably, a Cartesian tree's priorities come from the data, not a random source — it's a deliberate demonstration that the heap-plus-BST shape is useful even when nothing about it is balanced, tying directly back to the first Pitfall above (and inheriting that same sorted-input worst case, with no random priorities left to dodge it).
• A simpler alternative to AVL or red-black trees when simplicity matters more than a worst-case guarantee. The name and structure come from Seidel and Aragon's 1996 "Randomized Search Trees" paper, motivated by exactly this: a treap's insert and delete are each one straightforward rotation loop with a single comparison to make, with no rotation-case taxonomy to get right the way red-black insert/delete fixups need.
• Order Statistics Tree, the opposite move from Cartesian Tree above. Keep the random priorities exactly as built here, and add one more field instead of removing one: a subtree-size count at every node, kept correct through the identical rotation logic. That single field turns this same structure into one that answers select(k) (the k-th smallest stored value) and rank(x) (how many stored values are smaller than x) in O(log n), neither of which a plain treap can do without an O(n) walk.

Complexity

Time: search, insert, and delete are all O(log n) expected, over the randomness of the priorities — not amortized like a splay tree's guarantee (which holds over any sequence of operations on a fixed structure) and not worst-case guaranteed like AVL or red-black's. O(n) remains possible in the worst case, however unlikely for genuinely random priorities — the measured, growing gap to log₂(n) above is the honest version of that same trade. Space: O(n) for n nodes — two child pointers, one parent pointer, and one priority value each, the same pointer shape as a red-black tree but with a full priority (a float, in this page's implementation) standing in for its single color bit, and with no separate cached height field the way AVL needs one.

This site's guide, Choosing a Probabilistic Structure, compares this entry against Skip List — the other randomized alternative to a rotation-based balanced tree — side by side.