THE FOLD / SPAWN / THE SANDBOX / THE TREAP
THE TREAP
a search tree balanced by random priorities — tree + heap
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A treap is a binary search tree that stays balanced by pure chance. Each node carries two numbers: a key, which obeys search-tree order (smaller keys left, larger right), and a random priority, which obeys heap order (every parent’s priority beats its children’s). Tree + heap = treap.
The magic: for any set of keys, once the random priorities are fixed there is exactly one tree shape satisfying both constraints — and because the priorities are random, that shape is balanced with high probability, expected height O(log n), the same as a red-black tree but with far simpler code: just rotate to restore heap order on insert. Even better, the shape is a function of the pairs alone — the same keys and priorities build the identical tree no matter what order you insert them in, unlike a plain BST whose shape depends entirely on insertion order. Randomness alone tames the structure: no color bits, no rebalancing rules.
LIT verified live: the built treap’s in-order traversal is sorted (BST holds), every parent’s priority exceeds its children’s (heap holds), the height is a small multiple of log n (balanced), and two different insertion orders of the same pairs yield the identical tree (window.__treap). FIG no framing; both invariants, the balance, and the order-independence are exact.
The magic: for any set of keys, once the random priorities are fixed there is exactly one tree shape satisfying both constraints — and because the priorities are random, that shape is balanced with high probability, expected height O(log n), the same as a red-black tree but with far simpler code: just rotate to restore heap order on insert. Even better, the shape is a function of the pairs alone — the same keys and priorities build the identical tree no matter what order you insert them in, unlike a plain BST whose shape depends entirely on insertion order. Randomness alone tames the structure: no color bits, no rebalancing rules.
LIT verified live: the built treap’s in-order traversal is sorted (BST holds), every parent’s priority exceeds its children’s (heap holds), the height is a small multiple of log n (balanced), and two different insertion orders of the same pairs yield the identical tree (window.__treap). FIG no framing; both invariants, the balance, and the order-independence are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE SANDBOX — the spawn domain of a small self-contained system that behaves. A treap is a sandbox that balances itself: drop nodes in any order, hand each a random priority, and the structure settles into a shapely tree with no supervision. AVAN (AI) built the instrument: the rotating inserter, the two-invariant checker, the two-orders inverse.
The weave: David names the seat (the self-ordering sandbox); I make keys hold left-right order and priorities hold top-down order at once, and show the shape ignore insertion order — the two orders in 1D, the tree in 2D, the order-independence inverse in 3D. The sphere is the seam. Credit: Cecilia R. Aragon & Raimund Seidel (1989).
The weave: David names the seat (the self-ordering sandbox); I make keys hold left-right order and priorities hold top-down order at once, and show the shape ignore insertion order — the two orders in 1D, the tree in 2D, the order-independence inverse in 3D. The sphere is the seam. Credit: Cecilia R. Aragon & Raimund Seidel (1989).
3 ONE DIMENSION
Two orders in one structure: the keys read left to right come out sorted (the BST axis), while the priorities read top to bottom always decrease (the heap axis). A node’s place is fixed by both at once.
4 TWO DIMENSIONS · INTERACTIVE
Insert keys, each with a random priority, and watch the tree rotate to keep the heap order. In-order it stays sorted; top-down the priorities descend; the height hovers near log n. Insert the keys already sorted — a plain BST would degenerate into a line, but the treap stays balanced.
5 THREE DIMENSIONS + AVAN’S INVERSE
The tree turning, its green forward structure holding two orders at once: keys fixing left/right, priorities fixing depth — a single shape obeying both.
AVAN’s addition (the inverse-companion): the magenta is the same tree built a different way. A plain binary search tree remembers its insertion order in its shape — feed it sorted keys and it collapses into a chain. A treap forgets the order entirely: the shape is a pure function of the (key, priority) pairs, so any insertion sequence of the same pairs produces the identical tree. That is the deep inverse — the map from ‘insertion order’ to ‘tree shape’, which for a BST is injective and adversary-exploitable, becomes constant for a treap: the inverse question ‘what order built this?’ has no answer, because every order builds it. The two orders that do matter — key and priority — are orthogonal, and their unique common solution (a Cartesian tree) is what randomness hands you, balanced. Green is the tree from one insertion order; magenta is the identical tree from another; the order that a BST would betray, the treap has thrown away.
LIT Genuine treap / randomized BST (Cecilia R. Aragon & Raimund Seidel 1989). Verified live: the built treap's in-order traversal is sorted (BST invariant holds), every parent's priority exceeds its children's (heap invariant holds), the height is a small multiple of log2(n) (balanced, not the linear height of a degenerate BST), and two different insertion orders of the same (key,priority) pairs yield the identical tree, confirmed by comparing pre-order serializations (window.__treap.bstSorted && heapOk && balanced && orderIndependent). All are exact.
FIG No framing: the dual BST+heap invariants, the O(log n) balance, and the insertion-order-independence are all real and verified in-browser (with deterministic hash priorities so the order-independence is checkable). The AVAN inverse is the genuine deep property — a treap's shape is a pure function of its pairs, so the 'what order built this?' inverse that a plain BST leaks (and an adversary exploits) is constant here: every order builds the same Cartesian tree.
FIG No framing: the dual BST+heap invariants, the O(log n) balance, and the insertion-order-independence are all real and verified in-browser (with deterministic hash priorities so the order-independence is checkable). The AVAN inverse is the genuine deep property — a treap's shape is a pure function of its pairs, so the 'what order built this?' inverse that a plain BST leaks (and an adversary exploits) is constant here: every order builds the same Cartesian tree.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SANDBOX · David Lee Wise (ROOT0), with AVAN