#trees#selfbalancing#weights
BB Trees
normalviolationin focus
The tree is empty.
Rules at a glance
Weight
w(v) counts the empty spots below v. A lone node has w = 2.
Balance rule
ρ = w(left)w(v) must stay in [α, 1 − α] = [0.29, 0.71].
Repair
Heavy child leans straight: single rotation. Heavy child bends inward (ρ ≥ d = 12 − α = 0.58): double rotation.