We show that, in order to
achieve efficient maintenance of a balanced binary search tree,
no shape restriction other than a logarithmic height is required. The
obtained class of trees, general balanced trees, may be maintained
at a logarithmic amortized cost with no balance information stored in the nodes.
Thus, in the case when amortized bounds are sufficient, there is
no need for sophisticated balance criteria.
The maintenance algorithms use partial rebuilding.
This is important for certain applications, and has previously been used
with weight-balanced trees.
We show that the amortized cost incurred by general balanced trees
is lower than what has been shown for weight-balanced trees.
Full paper (postscript)
Full paper (pdf)