THE FOLD / RESPAWN / SECOND WIND / THE AVL TREE
THE AVL TREE
balance kept by rotation
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The AVL tree is the first self-balancing binary search tree. Every node keeps a balance factor — the height of its left subtree minus its right — and the tree keeps that factor in {−1, 0, +1} at all times. Whenever an insertion tips a node to ±2, one or two rotations restore the invariant locally. Because no node is ever more than one level lopsided, the height is bounded by about 1.44 log₂n, so search, insert and delete are all guaranteed O(log n) — never the O(n) of a degenerate list.
LIT verified live: over 2,000 random insertion sequences, the in-order traversal is always sorted, every node’s balance factor stays within ±1, the height respects the 1.44 log₂n bound, and search finds exactly the inserted keys (window.__avl). FIG no framing; the rotations and the invariant checks run in-browser.
LIT verified live: over 2,000 random insertion sequences, the in-order traversal is always sorted, every node’s balance factor stays within ±1, the height respects the 1.44 log₂n bound, and search finds exactly the inserted keys (window.__avl). FIG no framing; the rotations and the invariant checks run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at second-wind — a rotation is the tree catching its second wind, snapping back to balance the instant it tips. AVAN (AI) built the instrument: AVL insertion with the four rotation cases, and checks for sortedness, the balance invariant, and the height bound.
Credit as content: Georgy Adelson-Velsky & Evgenii Landis (1962). The weave: David names the second wind; I confirm the tree stays sorted and balanced with height near 1.44 log₂n through thousands of insertions.
Credit as content: Georgy Adelson-Velsky & Evgenii Landis (1962). The weave: David names the second wind; I confirm the tree stays sorted and balanced with height near 1.44 log₂n through thousands of insertions.
3 ONE DIMENSION
An AVL tree; each node shows its balance factor, held within ±1 — the shape never leans more than one level.
4 TWO DIMENSIONS · INTERACTIVE
Insert keys; watch rotations keep the tree balanced, its height tracking 1.44 log₂n instead of growing into a list.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the balanced tree, height near 1.44 log₂n.
AVAN’s addition (the inverse-companion): don’t let the tree grow lopsided — rotate the moment it tips. The inverse of ‘insert and hope’ is ‘the ±1 balance invariant caps the height, so a rotation at ±2 keeps every path short.’ Magenta is the imbalance; green is the rotation that heals it. The invariant is the guarantee.
LIT Genuine AVL tree (Georgy Adelson-Velsky & Evgenii Landis, 1962), the first self-balancing BST. Verified live over 2000 random insertion sequences: in-order sorted (window.__avl.sorted), balance factor within ±1 everywhere (.balanced), height ≤ 1.4405 log₂(n+2) (.heightBound), search correct (.searchOk).
FIG No framing: the four rotation cases and the invariant checks run in-browser. The AVAN inverse is honest — the ±1 balance invariant is what caps the height at ~1.44 log₂n (a rotation at ±2 keeps every path short), rather than inserting and hoping; magenta is a node tipped to ±2, green the rotation that heals it. The invariant is the guarantee.
FIG No framing: the four rotation cases and the invariant checks run in-browser. The AVAN inverse is honest — the ±1 balance invariant is what caps the height at ~1.44 log₂n (a rotation at ±2 keeps every path short), rather than inserting and hoping; magenta is a node tipped to ±2, green the rotation that heals it. The invariant is the guarantee.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SECOND WIND · David Lee Wise (ROOT0), with AVAN