Abstract (Rolf Fagerberg)

The minimum height of a binary search tree is [log(n+1)], where [] denotes the ceiling function and n is the number of nodes. Standard schemes for balancing binary search trees guarantee a maximum height within a constant factor of this optimum. For instance, in red-black trees the constant factor is 2, in AVL-trees it is 1.44, etc.

However, suppose we want to maintain a tree of real optimum height, while making insertions and deletions. Is it possible to do better than rebuilding the entire tree after each update? If not, how close to optimal height can we get with operations of reasonable complexity? For instance, can we get height [log n] + O(1) with logarithmic time updates? What tradeoffs are possible between height and time? How small can the actual update time (not counting the search time) be?

These questions are of obvious practical as well as theoretical interest, yet the existing results in this area do not seem to be very well known. Many of them are both interesting and simple, and in our opinion should have a place in any reasonably advanced textbook on algorithms and data structures.

In this talk we will give a survey of the known results (almost all of which are by Arne Andersson and Tony Lai), as well as some recent improvements by the speaker.

Along the road, we will touch upon several matters interesting in their own right, namely the list labelling problem, a certain combinatorial lemma, and a different and somewhat overlooked way to rebalance trees.


Last modified: January 17, 1996.
Kim Skak Larsen (kslarsen@imada.sdu.dk)