THE FOLD / BOSS / THE-FIREWALL / THE SCAPEGOAT TREE
THE SCAPEGOAT TREE
a tree that rebuilds its own worst branch
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The scapegoat tree keeps a binary search tree balanced without storing any balance information at all — no colours, no heights, no rotations. It just inserts normally, and whenever a new node ends up too deep (deeper than log1/α n), it walks back up to find the scapegoat: the first ancestor so lopsided that one of its subtrees holds more than an α-fraction of it. That entire subtree is then flattened and rebuilt perfectly balanced in one sweep. Because rebuilds are rare and cheap on average, insertions cost O(log n) amortized, and the tree’s height stays logarithmic — balance by occasional demolition, not constant maintenance.
LIT verified live: over 1000 random insertion sequences, the tree’s in-order traversal is always sorted, every key is findable, and the height never exceeds log1/α(n)+2 with α = 0.7 (window.__scapegoat_tree). FIG no framing; the depth-triggered scapegoat search and subtree rebuild run in-browser.
LIT verified live: over 1000 random insertion sequences, the tree’s in-order traversal is always sorted, every key is findable, and the height never exceeds log1/α(n)+2 with α = 0.7 (window.__scapegoat_tree). FIG no framing; the depth-triggered scapegoat search and subtree rebuild run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-firewall — when a branch grows dangerously deep, the tree finds the culprit and rebuilds it, holding the line at O(log n). AVAN (AI) built the instrument: the plain-BST insert, the depth trigger, the scapegoat search, the balanced rebuild, and the sorted / found / height checks.
Credit as content: Igal Galperin & Ronald Rivest (1993). The weave: David names the firewall; I confirm the tree stays sorted, searchable, and logarithmically tall — balance by rebuild alone.
Credit as content: Igal Galperin & Ronald Rivest (1993). The weave: David names the firewall; I confirm the tree stays sorted, searchable, and logarithmically tall — balance by rebuild alone.
3 ONE DIMENSION
Insert normally; when a node lands too deep, an over-heavy ancestor (the scapegoat) has its whole subtree rebuilt balanced.
4 TWO DIMENSIONS · INTERACTIVE
Insert keys; a too-deep insert triggers a rebuild, and the height stays within the logarithmic bound.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the tree, kept logarithmically shallow.
AVAN’s addition (the inverse-companion): don’t maintain balance every step — repair it when it breaks. The inverse of ‘an insert made a path too deep’ is ‘flatten the over-heavy scapegoat subtree and rebuild it perfectly balanced.’ Magenta is the too-deep path; green is the rebuilt balanced subtree. Balance by demolition.
LIT Genuine scapegoat tree (Igal Galperin & Ronald Rivest, 1993). Verified live: over 1000 random insertion sequences into an α=0.7 scapegoat tree, the in-order traversal equals the sorted keys, every key is findable, and the height never exceeds log_{1/α}(n)+2 (window.__scapegoat_tree.sorted, .allFound, .heightBounded).
FIG No framing: the depth-triggered scapegoat search and subtree rebuild run in-browser. The AVAN inverse is honest — instead of maintaining balance every step, it repairs balance when it breaks: an insert that made a path too deep triggers flattening the over-heavy scapegoat subtree and rebuilding it perfectly balanced. Magenta is the too-deep path; green is the rebuilt balanced subtree. Balance by demolition.
FIG No framing: the depth-triggered scapegoat search and subtree rebuild run in-browser. The AVAN inverse is honest — instead of maintaining balance every step, it repairs balance when it breaks: an insert that made a path too deep triggers flattening the over-heavy scapegoat subtree and rebuilding it perfectly balanced. Magenta is the too-deep path; green is the rebuilt balanced subtree. Balance by demolition.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-FIREWALL · David Lee Wise (ROOT0), with AVAN