AVL trees store a height number per node. Red-black trees store a color bit per node. Splay trees store nothing extra, but pay for that by restructuring the tree on every single operation, including a plain search. A scapegoat tree takes a third path: it stores nothing extra either — no height, no color, no priority, not even a size counter inside each node — and it does no work at all on a search, not a single rotation. The catch it accepts instead: an insert can occasionally trigger an expensive repair, and that repair isn't a rotation but a full flatten-and-rebuild of one whole subtree. The name comes from that repair step — when an insert makes the tree too deep, the algorithm walks back up from the new leaf and blames one specific ancestor for the imbalance, then throws out its entire subtree and rebuilds it from scratch, perfectly balanced. Only two numbers are tracked globally, not per node: how many keys the tree holds now, and the largest it's held since the last time the whole thing was rebuilt.
The tree below was loaded by inserting 1 through 8 in ascending order, the same adversarial sequence the AVL, red-black, and splay pages all used — and, like the splay tree's unsplayed chain, it lands as a full height-8 chain here too, checked against the shipped algorithm below. That's not a failure to notice the imbalance; a chain of 8 nodes is still shallow enough to satisfy this tree's own height rule (more on that rule below), so nothing has fired yet. Now insert 9: the new leaf lands at depth 8, which finally crosses the line, and watch the lower part of the chain — nodes 5 through 9 — light up and flatten into a balanced shape while nodes 1 through 4 stay exactly where they were (node 4 keeps its own position; only its right child changes, from a straight line down to the new balanced piece). That's the whole mechanism in one move: only the piece that's actually unbalanced gets touched, not the whole tree. Once that's done, try deleting 9, then 8, then 7 in that order — the third delete drops the tree to 6 nodes, which is small enough relative to its high-water mark of 9 to trigger the other kind of rebuild this structure does: a full rebuild of the entire tree, not just one subtree, since delete has no cheap way to identify a single scapegoat the way insert does.
After every insert, this tree enforces one invariant: no node may sit deeper than
log1/α(n), where n is the current key count and
α (alpha) is a tuning constant between 0.5 and 1, conventionally 0.75
(the value this page's demo and reference implementation both use). A smaller alpha means a
stricter, shallower bound; a larger alpha tolerates deeper trees before acting — see Pitfalls for
what that trade costs in practice. When a freshly-inserted leaf's depth exceeds that bound, the
tree is "weight-unbalanced" and needs a repair. Finding where to repair walks back up
from the new leaf toward the root, checking one condition at each ancestor p along the
way: is the size of the subtree just climbed out of more than α times the size of
p's whole subtree? The first ancestor where that's true is the scapegoat — the
specific node blamed for letting things get this deep, even though every individual insert along
the way was, on its own, a perfectly ordinary BST insert. Flattening its subtree via an in-order
walk and rebuilding it as a perfectly balanced tree (repeatedly picking the middle element of the
remaining sorted range as the new root) restores the height rule for that whole region in one
move — and because the flattened region is, by construction, exactly the piece that was too deep,
fixing it is guaranteed to bring the new leaf back within bound.
Insert can always point to a single guilty subtree, because the newly-inserted leaf's own
ancestor chain is exactly where the imbalance is. Delete has no equivalent signal — removing a key
can only ever shrink the tree, and a single delete alone can't tell you which surviving
subtree, if any, is now disproportionately large relative to the rest. Rather than track enough
extra bookkeeping to answer that question cheaply, a scapegoat tree sidesteps it with a much
blunter rule: after every delete, if the key count n has fallen below
α times maxN (the largest the tree has been since its last full rebuild),
rebuild the entire tree from scratch and reset maxN back down to the current
n. This is deliberately wasteful-looking per event — throwing away a perfectly good
tree just because it's "gotten small" — but it's cheap on average for the same reason insert's
partial rebuilds are: it only fires once enough deletes have accumulated to justify the cost, and
the reset maxN means the next full rebuild is just as far away again.
const ALPHA = 0.75;
class ScapegoatTree {
#root = null;
#n = 0;
#maxN = 0;
#size(node) {
if (node === null) return 0;
return 1 + this.#size(node.left) + this.#size(node.right);
}
#flatten(node, out) {
if (node === null) return;
this.#flatten(node.left, out);
out.push(node.value);
this.#flatten(node.right, out);
}
#buildBalanced(arr, lo, hi) {
if (lo > hi) return null;
const mid = (lo + hi) >> 1;
return {
value: arr[mid],
left: this.#buildBalanced(arr, lo, mid - 1),
right: this.#buildBalanced(arr, mid + 1, hi),
};
}
#rebuildAt(parent, isLeftChild, subtreeRoot) {
const arr = [];
this.#flatten(subtreeRoot, arr);
const rebuilt = this.#buildBalanced(arr, 0, arr.length - 1);
if (parent === null) this.#root = rebuilt;
else if (isLeftChild) parent.left = rebuilt;
else parent.right = rebuilt;
}
insert(value) {
if (this.#root === null) {
this.#root = { value, left: null, right: null };
this.#n = 1; this.#maxN = 1;
return;
}
const path = []; // ancestors from root down to (not including) the new leaf
let cur = this.#root;
while (true) {
if (value === cur.value) return; // no duplicates
path.push(cur);
if (value < cur.value) {
if (cur.left === null) { cur.left = { value, left: null, right: null }; break; }
cur = cur.left;
} else {
if (cur.right === null) { cur.right = { value, left: null, right: null }; break; }
cur = cur.right;
}
}
this.#n++;
this.#maxN = Math.max(this.#maxN, this.#n);
const depth = path.length;
const heightLimit = Math.log(this.#n) / Math.log(1 / ALPHA);
if (depth <= heightLimit) return; // still within the height rule, nothing to do
// Walk back up looking for the scapegoat: the first ancestor whose child
// toward the new leaf holds more than ALPHA of that ancestor's own subtree.
let childSize = 1;
for (let i = path.length - 1; i >= 0; i--) {
const p = path[i];
const descendedLeft = i === path.length - 1 ? value < p.value : path[i + 1] === p.left;
const sibling = descendedLeft ? p.right : p.left;
const pSize = childSize + this.#size(sibling) + 1;
if (childSize > ALPHA * pSize) {
const gp = i > 0 ? path[i - 1] : null;
this.#rebuildAt(gp, gp !== null ? gp.left === p : null, p);
return;
}
childSize = pSize;
}
}
search(value) {
let cur = this.#root;
while (cur !== null) {
if (value === cur.value) return true;
cur = value < cur.value ? cur.left : cur.right;
}
return false;
}
delete(value) {
let cur = this.#root, parent = null, isLeftChild = null;
while (cur !== null && cur.value !== value) {
parent = cur;
isLeftChild = value < cur.value;
cur = isLeftChild ? cur.left : cur.right;
}
if (cur === null) return false;
if (cur.left !== null && cur.right !== null) {
let succParent = cur, succ = cur.right;
while (succ.left !== null) { succParent = succ; succ = succ.left; }
cur.value = succ.value;
if (succParent.left === succ) succParent.left = succ.right;
else succParent.right = succ.right;
} else {
const child = cur.left !== null ? cur.left : cur.right;
if (parent === null) this.#root = child;
else if (isLeftChild) parent.left = child;
else parent.right = child;
}
this.#n--;
if (this.#n > 0 && this.#n < ALPHA * this.#maxN) {
this.#rebuildAt(null, null, this.#root);
this.#maxN = this.#n;
} else if (this.#n === 0) {
this.#maxN = 0;
}
return true;
}
}The interactive demo above uses equivalent insertScapegoat/searchScapegoat/
deleteScapegoat functions with extra bookkeeping to record the descent path, which
ancestor (if any) turned out to be the scapegoat, and which values belonged to whichever subtree
just got flattened and rebuilt — purely to drive the highlighting and log text. The tree-shape
logic is identical, including the choice not to store parent pointers or subtree sizes on the node
objects themselves: every size this algorithm needs is recomputed on demand by walking the actual
subtree, which costs no more than the rebuild that's about to happen anyway.
Verified against a plain JavaScript Set as a reference model across 300 randomized
trials of 50 mixed insert/delete operations each (15,000 operations total) on a deliberately small
value range, checking after every single operation: the BST ordering property, that the
in-order traversal exactly matches the Set's sorted contents, that contains
agrees with the Set for every value in range, and that tree height never exceeds
log1/α(n) plus a small rounding allowance — followed by a full
drain confirming the tree always ends empty. Zero mismatches. The height bound was then stressed
harder in two more targeted runs: inserting 1 through 2000 in ascending order (the classic
worst-case sequence for a plain BST) produced a final height of 25, against a
theoretical bound of 26.4 and a plain BST's or unsplayed splay tree's degenerate 2000; and 30 trials
of 3,000 random inserts each, followed by deleting every one of those keys back out in random
order and re-checking the height bound after every single delete (not just the inserts) —
zero violations across roughly 90,000 delete operations, the closest observed height ever reaching
95% of the theoretical bound and never crossing it. That last run mattered specifically because
delete's rebuild trigger is a global count check, not a per-operation height check the way insert's
is — worth confirming empirically that the bound still holds throughout a long delete-heavy run,
not just assuming it does because insert alone enforces it. The checker was self-tested against
four deliberately broken variants before trusting a clean run on the real code: skipping the
rebalance check entirely (chain height stayed at 1000 instead of dropping to 25, caught
immediately by the height-bound check), inverting the scapegoat comparison
(childSize < ALPHA * pSize instead of >, also caught by the height
check — height grew unbounded instead of staying near the theoretical line), dropping the +
1 for the ancestor itself when computing a subtree's size (same failure), and forgetting to
unlink the in-order successor from its old parent during a two-children delete (caught immediately
by the content-match check, over 5,000 mismatches in 100 trials — a real bug, not just a
theoretical one, since it leaves a duplicate node reachable from two places in the tree). One more
variant — always assuming the new leaf descended left when computing which ancestor child is the
"other" side — turned out not to be reliably caught by either check, an inconclusive
result rather than a confirmed-safe one, noted honestly rather than presented as a fifth successful
catch. Re-verifying by extracting the exact shipped insertScapegoat/
searchScapegoat/deleteScapegoat functions out of the HTML — rather than
trusting that a page's demo script matches the standalone reference model just because the two were
written to do the same thing — caught a real, separate bug the reference-model stress test above
never could: the shipped demo tracked the insert descent path as a plain array of values
(to drive the highlight/log UI) and then tried to reconstruct node references from those values by
re-walking the tree and comparing each value against itself, which is a tautology and wanders off
into the wrong branch on any tree that isn't a straight chain — invisible on the loaded 1-through-8
chain example specifically, because a pure right-chain's every ancestor's own value happens to equal
the comparison outcome by coincidence, but wrong the moment a real (non-chain) subtree gets
rebuilt and a second insert needs to walk back up through it. Fixed by keeping the actual node
references from the initial descent instead of re-deriving them from values, then re-ran the full
Set-comparison stress test directly against the corrected shipped functions with a
wider value range (0–500 instead of the original small range) specifically to force real branching
subtrees rather than chains, the exact shape that had exposed the bug: 200 trials of 60 operations
each starting from the loaded 8-node tree, 12,000 operations total, zero mismatches. A real
click-driven fake-DOM harness then confirmed the two worked examples named above (the 1-through-8
chain plus
inserting 9 finds scapegoat node 5 and flattens exactly nodes 5 through 9, dropping height from 8
to 7; then deleting 9, 8, 7 in order triggers a full rebuild on the third delete, dropping height
to 3). See /tmp/scapegoat/ref.js,
/tmp/scapegoat/stress.js, /tmp/scapegoat/delete_heavy.js,
/tmp/scapegoat/broken1.js–broken5.js, and
/tmp/scapegoat/fake_dom.js//tmp/scapegoat/click_harness.js, scratch, not
committed.
Alpha trades tree depth against total rebuild work, and the trade is steep in both
directions — measured, not just asserted. Building a tree by inserting 1 through 2000 in
ascending order at three different alpha values: α = 0.55 (close to the strictest
legal value) produced height 13 but did 29.31 nodes of rebuild
work per insert on average; the conventional α = 0.75 produced height
25 at 9.02 nodes per insert; α = 0.95 (close to the
loosest legal value) produced height 147 — twelve times deeper — but only
3.52 nodes of rebuild work per insert. There's no free lunch hiding at either end:
a small alpha keeps the tree shallow (fast reads) by rebuilding aggressively (slow, frequent
writes); a large alpha keeps writes cheap by tolerating a tree that's measurably closer to a plain
unbalanced BST. 0.75 is a genuinely reasonable default, not an arbitrary one, but it's still a real
dial, not a constant to ignore.
A scapegoat tree gives search the same worst-case guarantee as AVL or red-black, for
free — but only search. It's tempting to describe this structure as "no guarantee, like a
splay tree, just without the metadata," but that undersells it: because the height invariant is
checked and restored after every insert, a plain lookup is worst-case
O(log n) at all times, the same class of guarantee AVL and red-black offer, not
merely an amortized one the way a splay tree's search is. What's amortized instead is
insert and delete themselves — any single one of those can cost
O(n) in the rare case it triggers a rebuild, the same way a single splay tree
operation can. Conflating "no per-node metadata" with "no operation has a worst-case bound" would
describe the wrong structure.
Skipping delete's global-count rebuild check doesn't just leave the tree slightly
stale — it silently breaks the height guarantee's own basis. The height bound
insert enforces is stated in terms of the current key count n, which shrinks
with every delete. If deletes never rebuilt anything, a tree that grew to a million keys and then
shrank back down to ten would still be carrying whatever height it had at a million — nowhere
close to log1/α(10) — and every future insert's own height
check would keep comparing against the wrong (now far too small) baseline for how deep is
actually reasonable at ten keys. The maxN reset is what keeps that comparison honest
across arbitrarily many grow-then-shrink cycles, not just a minor cleanup step.
O(n), with no way to know in
advance which. Red-black trees pay a small,
predictable cost on every write specifically to avoid that variance, which is why they're the
more common default for a general-purpose write-heavy container.Time: search is O(log n) worst case,
guaranteed after every insert by the height rule above — not amortized, unlike every other number
on this page. insert and delete are both O(log n)
amortized: most operations do a plain O(log n) BST walk and nothing more, but
any single one can cost O(n) if it triggers a rebuild (a subtree rebuild for insert, a
whole-tree rebuild for delete) — the same amortized-not-worst-case shape as a
splay tree's guarantee, reached by a completely
different mechanism (occasional flatten-and-rebuild instead of restructuring on every touch).
Space: O(n) for n nodes, at the minimum possible
per-node cost for any binary tree — two child pointers, nothing else — plus two O(1)
counters (n and maxN) shared by the whole structure, not stored per
node.
See Choosing a Search Tree for how this compares against AVL, red-black, splay, B-tree, and a plain BST when picking an ordered container.