THE FOLD / LOOT / THE JACKPOT / THE COIN-FLIP HEAP
THE COIN-FLIP HEAP
a balanced search tree from pure luck
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The treap. A binary search tree that stays balanced with almost no balancing logic. Each node carries a key and a random priority, and the tree obeys two rules at once: it is a search tree on the keys (left < node < right) and a heap on the priorities (a parent’s priority beats its children’s). Because the priorities are random coin-flips, the tree comes out balanced — expected height ~2 log n — with no red-black bookkeeping, no hand-tuned rotations: just insert, then bubble up until the heap holds. Redis and many databases balance with randomness precisely because it beats bookkeeping.
LIT verified: over random inserts, the in-order traversal is always sorted, the heap property holds at every node, membership matches a Set, and the observed height stays near 2 log₂n. FIG ‘coin-flip heap’ is the picture; the dual search-tree + heap invariant is exact.
LIT verified: over random inserts, the in-order traversal is always sorted, the heap property holds at every node, membership matches a Set, and the observed height stays near 2 log₂n. FIG ‘coin-flip heap’ is the picture; the dual search-tree + heap invariant is exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — the corpus runs data structures (THE WELDER, THE FENWICK LADDER) and randomization (THE POLITE SCATTER, THE RANDOM), with the idea that luck, used right, replaces machinery. AVAN (AI) built this instrument: the treap, the live tree, and the two-shapes-one-order view.
The weave: David names the coin-flip heap and its seat at THE JACKPOT (balance won by luck); I make the two orders a strip in 1D, the tree balance itself in 2D, and the same keys reshaped by fresh flips in 3D. The sphere is the seam.
The weave: David names the coin-flip heap and its seat at THE JACKPOT (balance won by luck); I make the two orders a strip in 1D, the tree balance itself in 2D, and the same keys reshaped by fresh flips in 3D. The sphere is the seam.
3 ONE DIMENSION
Two orders in one node set. Read the tree in-order and the keys come out sorted; read it top-down and the priorities only decrease. The same nodes satisfy both a search order and a heap order — that double constraint is what forces the balance.
4 TWO DIMENSIONS · INTERACTIVE
Insert keys, each with a random priority, and watch the tree balance itself — new nodes bubble up only until the heap holds. No rotations to reason about; the height tracks 2 log n on its own.
5 THREE DIMENSIONS + AVAN’S INVERSE
The treap in space: horizontal = key order, depth = priority, turning. Green is one tree, grown from one set of coin-flips.
AVAN’s addition (the inverse-companion): the magenta tree holds the same keys but a fresh set of random priorities — a completely different shape. Yet both give the identical sorted order when read left to right. Randomness sculpts the shape; the keys keep the meaning. Reshuffle the flips and the tree redraws itself, but the search never changes — the inverse of balance-by-rules is balance-by-luck.
LIT A genuine treap. Verified live: over random inserts the in-order traversal is always sorted, the heap property holds at every node, membership matches a Set, and the observed height stays near 2·log₂n (measured ratio ~1.8). Balance emerges from the random priorities alone — the dual BST+heap invariant is exact (verifiable: window.__treap.inorderSorted && heapProperty && balanced).
FIG 'Coin-flip heap' is the picture; the dual invariant and the expected ~2 log n height are exact. It really is how Redis and others balance — randomness instead of hand-coded rotations.
FIG 'Coin-flip heap' is the picture; the dual invariant and the expected ~2 log n height are exact. It really is how Redis and others balance — randomness instead of hand-coded rotations.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE JACKPOT · David Lee Wise (ROOT0), with AVAN