Why do you reason about the minimum number of nodes of an AVL tree of height h to argue the height is $\log n$ of an AVL tree?

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?

• 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$. Feb 24 '16 at 5:58
• @YuvalFilmus what is the correct intuition then? Feb 24 '16 at 6:01
• 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.
– Raphael
Feb 24 '16 at 9:44
• 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. Feb 24 '16 at 13:54