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?

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

StackExchange Computer Science Q#53553, answer score: 2