2
$\begingroup$

Recall the standard argument for showing an AVL free is of size $\log n$:

Let $n_h = $ be the minimum number of nodes of an AVL tree of height $h$. Then we have:

$$ n_{h} \geq 1 + n_{h-1} + n_{h-2} \implies n_h > 2n_{h-2}$$ $$ n_h > 2^{\frac{h}{2} } \implies h < 2 \log n_h $$

so the height of the tree is $O( \log n)$.

I understand the recurrence but I just don't understand why we argue about:

be the minimum number of nodes of an AVL tree of height $h$

maybe my intuition is wrong but I thought that we'd want to argue about as many nodes as we can fit in a tree of height $h$ and show that it still balanced and show its $\log n$. Why is that reasoning incorrect?

$\endgroup$
  • 2
    $\begingroup$ Your intuition is wrong since an AVL tree is not strictly balanced. That's why you only get $2\log n$ rather than $\log n$. $\endgroup$ – Yuval Filmus Feb 24 '16 at 5:58
  • $\begingroup$ @YuvalFilmus what is the correct intuition then? $\endgroup$ – Charlie Parker Feb 24 '16 at 6:01
  • $\begingroup$ Instead of asking three questions at the same time, you should have asked the most fundamental first and waited if answers cleared up all the issues for you. $\endgroup$ – Raphael Feb 24 '16 at 9:44
  • $\begingroup$ The intuition is that an AVL tree is somewhat balanced, and that's enough to keep it shallow. This is what the calculation you state shows. $\endgroup$ – Yuval Filmus Feb 24 '16 at 13:54
2
$\begingroup$

First of all AVL trees are binary trees so you can't argue as many nodes as we can fit in a tree of height h because the maximum nodes you can fit in a AVL tree with h is 2h+2h-1+...+20. Also the minimum number of nodes on an AVL tree with h is 1+2h-1+2h-2+..+20.

be careful for the first 1 at minimum number rather than 2h. If that plus one node would not exists, the AVL tree would be simply of height h-1, and we don't want that.

So you have to define n as be the minimum number of nodes of an AVL tree of height h. Because your algorithm has at least that much of nodes to traverse , and you do the analyze with that assumption

$\endgroup$
  • $\begingroup$ Ah nice thanks, the phrase "your algorithm has at least that much of nodes to traverse , and you do the analyze with that assumption" was key! Makes sense. Also, yuvals comments on "Your intuition is wrong since an AVL tree is not strictly balanced. That's why you only get 2log⁡n rather than log⁡n" was helpful. Thanks! $\endgroup$ – Charlie Parker Feb 24 '16 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.