# AVL Trees meet Fibonacci Numbers

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).

Let $T(d)$ denote the smallest size of an AVL tree of depth $d$. Clearly $T(0) = 1$ and $T(1) = 2$

Which of the following recurrences does $T$ satisfy?

1. $T(d) = T(d-1) + T(d-2)$
2. $T(d) = T(d-1) + T(d-2) +1$
3. $T(d) = 1 + 2T(d-1)$
4. $T(d) = 2T(d-2)$
5. $T(d) = T(d/2)^2$
6. None of the above

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).

Consider an AVL tree with $n$ vertices. What is its maximum possible depth?

In the answer choices, $\phi = \frac{1+\sqrt{5}}{2}$ and $\phi' = \frac{1-\sqrt{5}}{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.

Note by Varsha Dani
1 year, 8 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Okay, I am sorry if this bothers you, but can I ask how do you get the problems to have the looks like the one in the wikis. Is this limited to staff and selected members or not?

- 1 year, 8 months ago

I opened up a wiki page, clicked "edit wiki" and looked at how it was formatted there and copied that :D

And no, it doesn't bother me at all.

- 1 year, 8 months ago

Ohhh, clever! Thanks for telling me that!

- 1 year, 8 months ago

I think brilliant has recently updated this option. 2 months back I tried this format in notes but with no result.

- 1 year, 8 months ago

I also tried doing so, I think three months ago and it didn't come back with any good results. Also, after solving the problem, you can see that there are irregular spaces between the lines "Correct!", "...% got this right" and "Continue", "View Solution" (even there aren't any explanation, it still show "View Solution"). And if you are the creator of a problem that you posted on a note, it will update on how many percentages of people got it right, very slowly. And I mean, very slowly. On a problem on mine posted there, it showed that "17% of people got it right". But after trying to click on the problem several times (because occasionally, if you click on a problem or the "Edit note" button, it only takes you to the last problem you posted on that note.), it shows that only "10% of people got it right".

There are many more mistakes in this that I can't say right now. It is best if you check a set with a similar format from a different creator to really see all of the mistakes if you and others used that format.

Here's one: Olay, let's try this. Brilliant needs to fix all of the problems they got with using similar concepts in a different writing environment, in this case, it's between the wikis and the notes.

- 1 year, 8 months ago