Technical Report No. 6, December 1987 - Abstract

Rolf Klein, Derick Wood:
A Tight Upper Bound for the Path Length of AVL Trees

This report is not available in electronic form!

We prove that the internal path length of an AVL tree of size N is bounded from above by

1.4404N(log_2 N - log_2(log_2 N))+O(N)

and show that this bound is achieved by an infinite family of AVL trees. But AVL trees of maximal height do not have maximal path length. These results carry over to the comparison cost of brother trees.