How Unoptimal are AVL Search Trees?
Sandra Hedetniemi
Committee:
Technical Report(May 1980)
Keywords:

The following two questions can be asked about AVL search trees:

  1. Given any integer k, does there exist an AVL tree with two leaves at level numbers differing by k?
  2. What is the minimum number of nodes such a tree can have?

It is shown that a subset of the Fibonacci search trees have the minimum number of nodes among all AVL search trees with two leaves at level numbers differing by k.