A TOP-DOWN UPDATING ALGORITHM FOR WEIGHT-BALANCED TREES
Tony W. Lai, Derick Wood · International Journal of Foundations of Computer Science · 1993
We prove that during any update in a weight-balanced tree, or BB[α] tree, a top-down restructuring pass is sufficient to rebalance the tree if 2/11<α≤1/4. We also prove that if updates are known to be nonredundant, then a top-down pass is sufficient to rebalance the tree during an update if [Formula: see text].