Normal Node
New Insert
Scapegoat
Rebuilding

α Parameter (Balance)

Tighter 0.70 Looser

α = 0.55: Frequent rebuilds, optimal balance
α = 0.95: Rare rebuilds, may degrade

Operations

Actions

Statistics

0
Nodes
0
Height
0
Max Allowed
0
Rebuilds

Operation Log

About Scapegoat Trees

  • No extra storage per node needed
  • Lazy rebalancing via complete rebuild
  • Find unbalanced "scapegoat" ancestor
  • O(log n) amortized operations
  • α parameter controls rebuild frequency