A. Andersson. Maintaining alpha-balanced trees by partial rebuilding.
International Journal of Computer Matehmathics, 38:37--48, 1990.

(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)

The balance criterion defining the class of alpha-balanced trees states that the ratio between the shortest and longest paths from a node to a leaf be at least alpha. We show that a straight-forward use of partial rebuilding for maintenance of alpha-balanced trees requires an amortized cost of Omega(sqrt(n)) per update. By slight modifications of the maintenance algorithms the cost can be reduced to O(log n)$for any value of alpha, 0 < alpha < 1.

Preprint (postscript)
Preprint (pdf)