# 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$. – Yuval Filmus Feb 24 '16 at 5:58
• @YuvalFilmus what is the correct intuition then? – Charlie Parker 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. – Yuval Filmus Feb 24 '16 at 13:54

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