(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.