Treaps

A binary search tree keeps things sorted: every left child has a smaller key, every right child has a larger one. But a plain BST is only as good as the order items arrive. Insert them in sorted order and you get a linked list, not a tree — every lookup now costs $O(n)$ instead of $O(\log n)$.

To fix that, you need the tree to stay balanced. AVL trees and red-black trees do it with elaborate rotation rules and extra color or height bits on every node. Those algorithms work, but they are notoriously subtle to implement correctly.

A treap takes a completely different route. Give each node a second field called its priority — a uniformly random number drawn when the node is created. Now enforce two invariants simultaneously:

• BST property on keys: left subtree keys < node key < right subtree keys.
• Max-heap property on priorities: every parent has a higher priority than its children.

Aragon and Seidel proved in 1989 that these two rules together force the tree's shape to be the unique binary search tree consistent with both orderings — and because priorities are random, the expected height is $O(\log n)$.

No rotation counters, no color bits, no rebalancing passes. Randomness does the work.

The two fundamental treap operations are split and merge. Split divides the treap into two treaps (keys ≤ threshold and keys > threshold). Merge fuses them back, restoring both invariants.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{label_key}} <input id="key-in" type="number" min="1" max="99" value="50" style="width:52px"></label>
  <button id="btn-insert">{{btn_insert}}</button>
  <span class="sep">|</span>
  <label>{{label_split}} <input id="split-in" type="number" min="1" max="99" value="40" style="width:52px"></label>
  <button id="btn-split">{{btn_split}}</button>
  <button id="btn-merge" disabled>{{btn_merge}}</button>
  <button id="btn-reset" class="ghost">{{btn_reset}}</button>
</div>
<div id="msg" class="msg"></div>
<div id="canvas-wrap"><canvas id="cv" width="680" height="280"></canvas></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .45rem; flex-wrap: wrap; margin-bottom: .5rem; }
label { font-size: .9rem; }
input[type=number] { font: inherit; padding: .2rem .3rem; border: 1px solid #adb1b8; border-radius: 6px; }
button { font: 600 13px system-ui; padding: .38rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.sep { color: #aaa; }
.msg { font-size: .93rem; font-weight: 600; min-height: 1.3em; margin-bottom: .3rem; }
.msg.ok  { color: #0a7d33; }
.msg.bad { color: #c92f3c; }
#canvas-wrap { overflow-x: auto; }
canvas { display: block; background: #f7f9fb; border-radius: 10px; border: 1px solid #dde3ea; max-width: 100%; }

// Code not found

Notice how the tree reorganizes after every operation yet always satisfies both invariants. Checking that a tree is a valid treap takes $O(n)$ — just walk every node and verify the BST and heap conditions. Building an optimal balanced BST from scratch without randomness is harder (see binary search trees and dynamic shortest paths for related ideas about optimal structure).

How fast are treap operations?

• Search, insert, delete: all run in $O(\log n)$ expected time. The expected height of a random treap on $n$ keys is at most $4.3 \ln n$, a consequence of the priorities forming a random permutation.
• Split and merge: also $O(\log n)$ expected time. Split follows a root-to-leaf path determined entirely by the threshold key and the heap invariant. Merge races two paths simultaneously and picks the higher-priority root at each step.
• Worst-case: $O(n)$ — a pathological priority draw can produce a skewed tree, just as quicksort can degenerate. But the probability of the tree exceeding height $c \log n$ drops exponentially in $c$.
• Proven result (Aragon & Seidel, 1989): the expected number of rotations to insert or delete a node is exactly 2. This is the source of treaps' practical speed.

Compared to deterministic alternatives:

The treap trades a deterministic worst-case guarantee for a probabilistic one — and wins on simplicity, which matters enormously in practice.

The split/merge primitive makes treaps unusually versatile:

• Order-statistics tree: augment each node with its subtree size. Then finding the $k$-th smallest element or the rank of any key costs $O(\log n)$, exactly as in a balanced BST — but with a simpler codebase.
• Persistent treaps: because split and merge create new nodes rather than modifying existing ones, making them persistent (keeping all past versions alive) costs only one extra pointer per node. This is the backbone of functional ordered sets in languages like Haskell.
• Rope data structure: represent a long string as a treap on character indices. Substring insertion, deletion, and concatenation all become treap merges and splits — each $O(\log n)$ instead of $O(n)$ for a flat array.
• Competitive programming: treaps are a contest staple because they replace segment trees, interval trees, and sorted sets with a single data structure and roughly 50 lines of code. See also binary search for the sorted-order guarantees they rely on.
• Implicit treap: use the subtree size as the implicit key (no explicit key stored). This turns the treap into a sequence data structure that supports $O(\log n)$ split, merge, and arbitrary indexed access — more powerful than a doubly linked list and faster than a balanced BST for positional queries.

The unifying theme: once you have $O(\log n)$ split and merge, almost any sequence or set operation reduces to a small composition of those two primitives.

The treap's insight is almost embarrassingly simple: let randomness do the balancing. Add one random number to each node, obey the heap invariant, and the resulting tree is expected to be as flat as any hand-balanced structure — with far less code.

Split and merge make this structure genuinely powerful. Nearly every ordered-set or sequence operation reduces to a composition of those two primitives, which means a treap can replace half a dozen specialized data structures without sacrificing asymptotic performance.

The next time you reach for an AVL tree or a red-black tree and dread the implementation, remember: a coin flip per node might be all you need. That is the lesson the treap has quietly been teaching since 1989.