THE FOLD / LOOT / THE STASH / THE VAN EMDE BOAS
THE VAN EMDE BOAS
integer successor in O(log log u)
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The van Emde Boas tree stores integers from a universe {0, …, u−1} and answers successor, predecessor, and membership in O(log log u) time — faster than any comparison tree’s log u. It recursively splits the universe into √u clusters plus a summary structure over which clusters are non-empty, and stores each node’s min/max lazily so most queries short-circuit. It is the classic structure for very fast integer successor search.
LIT verified live: over 40 random trees on a 256-element universe, member(x) matches a reference set and successor(x) matches the sorted-set successor for every x (window.__veb). FIG no framing; exact.
LIT verified live: over 40 random trees on a 256-element universe, member(x) matches a reference set and successor(x) matches the sorted-set successor for every x (window.__veb). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-stash — the sorted hoard you must query “what’s the next item after x?” blazingly fast. The van Emde Boas tree is that successor oracle. AVAN (AI) built the instrument: the √u split, the summary structure, the lazy min/max, the recursive insert/member/successor, and the sorted-set cross-check.
Credit as content: Peter van Emde Boas (1975). The weave: David names the stash; I recurse over √u clusters with a summary of the non-empty ones and confirm membership and successor exactly match a sorted set.
Credit as content: Peter van Emde Boas (1975). The weave: David names the stash; I recurse over √u clusters with a summary of the non-empty ones and confirm membership and successor exactly match a sorted set.
3 ONE DIMENSION
The universe splits into √u clusters; a summary tracks which clusters are non-empty. To find the successor of x: look within x’s cluster; if none, jump via the summary to the next non-empty cluster and take its minimum.
4 TWO DIMENSIONS · INTERACTIVE
A vEB tree over a 256-universe; query successors and compare against the sorted set, all matching.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: successor search in log-log time.
AVAN’s addition (the inverse-companion): find an integer’s successor in O(log log u) by recursively splitting the universe into √u clusters with a summary of which are non-empty — so each step square-roots the search space. The inverse of ‘compare down a binary tree in log u’ is ‘square-root the universe each step — log log u.’ Magenta is the log-u comparisons a balanced tree needs; green is the √u recursion. Successor faster than comparison allows.
LIT Genuine van Emde Boas tree (van Emde Boas 1975). Verified live: over 40 random trees on a 256-element universe, member(x) matches a reference Set and successor(x) matches the sorted-set successor for every x in 0..255 (window.__veb.member && .successor).
FIG No framing: the sqrt(u) split, the summary structure, the lazy min/max, the recursive insert/member/successor, and the sorted-set cross-check run in-browser and agree exactly. The AVAN inverse is honest — recursively square-rooting the universe with a summary of non-empty clusters finds a successor in O(log log u); magenta is the log-u comparisons a balanced tree needs, green the sqrt(u) recursion. Successor faster than comparison allows.
FIG No framing: the sqrt(u) split, the summary structure, the lazy min/max, the recursive insert/member/successor, and the sorted-set cross-check run in-browser and agree exactly. The AVAN inverse is honest — recursively square-rooting the universe with a summary of non-empty clusters finds a successor in O(log log u); magenta is the log-u comparisons a balanced tree needs, green the sqrt(u) recursion. Successor faster than comparison allows.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE STASH · David Lee Wise (ROOT0), with AVAN