THE FOLD / GRIND / WARM CACHE / THE SPLAY TREE
THE SPLAY TREE
a search tree that reshapes itself around what you use
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The splay tree is a self-adjusting binary search tree: every time you touch a node, you splay it — rotate it all the way to the root. There are no balance rules and no stored heights or colours; the tree simply reshapes itself so that recently and frequently accessed keys sit near the top, giving amortised O(log n) per operation.
It is a self-optimising cache in tree form, and the basis of link-cut trees.
LIT verified live: over 300 random operation sequences the in-order traversal stays sorted, the key set matches a reference, every key is found, and after each access that key is at the root (window.__splaytree). FIG no framing; exact.
It is a self-optimising cache in tree form, and the basis of link-cut trees.
LIT verified live: over 300 random operation sequences the in-order traversal stays sorted, the key set matches a reference, every key is found, and after each access that key is at the root (window.__splaytree). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at warm-cache — the thing you just used floats to the top, ready to hand, so the next access is cheap. The splay tree is a warm cache built of pointers. AVAN (AI) built the instrument: the top-down splay, the insert/find, the sorted-order + at-root checks.
Credit as content: Daniel Sleator & Robert Tarjan (1985). The weave: David names the warm cache; I splay each touched key to the root and confirm the tree stays a valid search tree while the workload reshapes it.
Credit as content: Daniel Sleator & Robert Tarjan (1985). The weave: David names the warm cache; I splay each touched key to the root and confirm the tree stays a valid search tree while the workload reshapes it.
3 ONE DIMENSION
A splay: the accessed node rotates upward step by step (zig, zig-zig, zig-zag) until it becomes the root — the path it travelled is roughly halved in depth along the way.
4 TWO DIMENSIONS · INTERACTIVE
Insert or access keys; the touched key splays to the root and the tree rebalances itself around your usage.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the accessed key, splayed to the root, the tree reshaped beneath it.
AVAN’s addition (the inverse-companion): the tree reshapes itself around what you use. Every access splays the touched node to the root, so recently and frequently used keys drift to the top and repeated access is amortised O(log n) — with no explicit balance rules, heights, or colours maintained. The inverse of ‘keep the tree balanced by rules’ is ‘let access itself reshape the tree.’ Magenta is the rigid AVL/red-black balance conditions you never maintain; green is the self-adjusting path splayed to the root. The structure adapts to the workload.
LIT Genuine splay tree (Sleator & Tarjan 1985). Verified live: over 300 random insert/access sequences the in-order traversal is sorted, the key multiset equals a reference set, every inserted key is found, and each accessed key ends at the root (window.__splaytree.sorted && .keysMatch && .accessedAtRoot).
FIG No framing: the top-down splay, insert/find, and the sorted-order + at-root checks run in-browser and hold exactly. The AVAN inverse is honest — every access splays the touched node to the root so the tree self-adjusts to the workload with no explicit balance rules; magenta is the AVL/red-black conditions never maintained, green the self-adjusting path splayed up. A warm cache built of pointers.
FIG No framing: the top-down splay, insert/find, and the sorted-order + at-root checks run in-browser and hold exactly. The AVAN inverse is honest — every access splays the touched node to the root so the tree self-adjusts to the workload with no explicit balance rules; magenta is the AVL/red-black conditions never maintained, green the self-adjusting path splayed up. A warm cache built of pointers.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of WARM CACHE · David Lee Wise (ROOT0), with AVAN