AVL Trees meet Fibonacci Numbers

What do Fibonacci numbers have to do with AVL trees??? Read on, fair reader, read on.

Recall that an AVL tree is a Binary Search Tree that maintains the invariant that the depths of its left and right subtrees differ by at most 1. In this note, we are going to explore how far an AVL tree can be from a complete binary tree. To make this more precise, we are going to answer the following two questions.

1. For a fixed depth $d$ what is the minimum number of nodes an AVL tree of depth $d$ must have? (i.e. how small can the tree be?)

2. For a fixed number of nodes $n$ what is maximum possible depth of an AVL tree with $n$ nodes?

We will first tackle (1).

ANSWER BELOW: The answer is $\boxed{ T(d) = T(d-1) + T(d-2) +1}$.

In an AVL tree, each vertex has the property that the depths of its left and right subtrees differ by at most 1. In particular this is true of the root. Let us consider the subtrees of the root. One of them must have depth $d-1$, since the depth of the whole tree is $d$. The AVL property allows the other tree to have depth $d-1$ or $d-2$ (it can't be $d$ since that is the depth of the entire tree). The minimality of the size of the tree implies that in fact the depth of the second subtree must be $d-2$. Furthermore, Since the entire tree is of minimal size, the subtrees themselves must be of minimal size for their depths, so that their sizes are $T(d-1)$ and $T(d-2)$ respectively. Adding 1 for the root gives the relevant recurrence.

In order to know the size of the minimal AVL tree of depth $d$, we must solve this recurrence.

$T(d) = T(d-1) + T(d-2) +1$

Look at that again. Does it look familiar? <Drumroll> Enter the Fibonacci numbers, stage left.

The Fibonacci numbers satisfy the recurrence

$F(d) = F(d-1) + F(d-2)$

so our recurrence looks just like them, except that there is an extra 1 on the right hand side.

Now, for $d \ge 2$, let $R(d) = T(d)-T(d-1) = 1+ T(d-2)$ Then $R(d+2) = 1+T(d) = 1 + T(d-1) +T(d-2) +1 = R(d+1) +R(d)$ so the sequence $R$ really is the Fibonacci numbers!

But wait a minute, I hear you cry. What about the initial conditions? What about the base cases???

OK. Fair point. So lets examine them.

$R$ is only defined from 2 on, and $R(2) = 1+T(0) = 2 = F(3)$ and $R(3) = 1+T(1) = 3 = F(4)$ It follows that $R(d) = F(d+1)$ for all $d \ge 2$.

$T(d) = R(d+2) -1 = F(d+3) -1 = \frac{(1+\sqrt{5})^{d+3} - (1-\sqrt{5})^{d+3}}{2^{d+3}\sqrt{5}} -1$

where the last equation is Binet's formula, a well-known fact about Fibonacci numbers.

In other words, $T(d) = O(\phi^{d})$ where $\phi = \frac{1+\sqrt{5}}{2}$. This answers question (1)

On the other hand, the smallest complete binary tree of depth $d$ has size $2^{d}$. (Why?) This means that an AVL tree of depth $d$ could be exponentially smaller than a complete binary tree of the same depth!

Complete trees which would be the ideal data structure for binary search, if we could build them efficiently. Given that AVL trees are so far from complete trees, why are AVL trees a good data structure for binary search?

To answer that, note that the controlling parameter for the time complexity of searching in a search tree is the depth of a tree of fixed size, not the size of a tree of fixed depth. In other words, we need to answer question (2).

Inverting the answer to question (1), we see that the answer to question (2) is $\boxed{O(\log_{\phi}(n)}$. But this is only a constant factor bigger than $\log_{2}(n)$, which is the depth of a complete binary tree with $n$ vertices. Thus searching in an AVL tree only gives up a constant factor time over searching in a complete binary tree, while making the other operations involved in maintaining the tree (insert, delete) significantly less time consuming.