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.

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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestOkay, 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?

Log in to reply

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.

Log in to reply

Ohhh, clever! Thanks for telling me that!

Log in to reply

Log in to reply

irregular spacesbetween 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 problemseveral 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.

Log in to reply