6
$\begingroup$

I came across a proof that the an AVL tree has O(log n) height and there's one step which I do not understand.

Let $N_h$ represent minimum number of nodes that can form an AVL tree of height h. Since we're looking for minimum number of nodes, let its children's minimum number of nodes be $N_{h-1}$ and $N_{h-2}$.

Proof:

$$N_h = N_{h-1} + N_{h-2} + 1 \tag{1}$$ $$N_{h-1} = N_{h-2} + N_{h-3} + 1 \tag{2}$$ $$ N_h = (N_{h-2} + N_{h-3} + 1 + ) + N_{h-2} + 1 \tag{3}$$ $$ N_h > 2N_{h-2} \tag{4}$$ $$N_h > 2^{h/2} \tag{5} $$

I do not understand how we went from (4) to (5). If anyone could explain, that'd be great. Thanks!

$\endgroup$
5
$\begingroup$

You can continue as same as line 4 the process like that:

$$ N_h > 2N_{h-2}> 2(2 N_{h-4})>2(2(2 N_{h-6}))>\cdots$$ As you can see, the indexs are decreasing by substracting $2$ in each step when you use the inequality. So, the process stops when the index $h$ takes $0$, but from the indexs behavior the half of $h$ (floor) will be the quantity of times that we substract $2$ from $h$.

$$ N_h > 2N_{h-2}>\cdots>2(2(2(2(2h^{h-10}))))> 2^{\frac{h}{2}}$$

$\endgroup$
1
$\begingroup$

Assuming $h$ even, by induction

$$N_h>2N_{h-2}>2^2N_{h-4}>2^3N_{h-6}>\cdots 2^{h/2}N_0$$

because you go up two levels $h/2$ times.

$\endgroup$
0
$\begingroup$

After drawing some trees, I realized that the minimum number of nodes of a tree with height $h-2$ is in fact $2^{h/2}$.

$\endgroup$
  • $\begingroup$ This doesn't really answer the question. It does not explain why that is the minimum. (It's not the minimum for binary trees in general, so if it's true it has to be because of some property of AVL trees, and it's not self-evident why that property would hold.) In fact, that's basically what you're trying to prove, so relying on this unproven fact would make for circular reasoning. $\endgroup$ – D.W. Jan 16 '16 at 18:20
0
$\begingroup$

Let's consider an example of an AVL tree with height of 4, then:

$N_8 > 2 N_{6} \ \ \ \Longleftrightarrow \ \ N_8 > 2^1 N_{8 - 2 \cdot 1}$

$N_8 > 4 N_{4} \ \ \ \Longleftrightarrow \ \ N_8 > 2^2 N_{8 - 2 \cdot 2}$

$N_8 > 8 N_{2} \ \ \ \Longleftrightarrow \ \ N_8 > 2^3 N_{8 - 2 \cdot 3}$

$N_8 > 16 N_{0} \ \Longleftrightarrow \ \ N_8 > 2^4 N_{8 - 2 \cdot 4}$

recall, that a tree with only one node (root) has height of 0, so $N_{h=0} = 1$. Hence,

$N_8 > 16 N_{0} \ \ \ \ \Longleftrightarrow \ \ \ \ N_8 > 2^4$

and this is exactly $N_h > 2^{h/2}$.


The most interesting part of this proof is generalization. Did you notice a pattern in our example?

$N_h > 2^i N_{h - 2 \cdot i}$ $\qquad (1)$

Can we compute the value of $i$ when $N_{h - 2 \cdot i}$ becomes $N_{h=0}$?

Yes, we can get the value of $i$ by solving this equation: $h - 2 \cdot i = 0$. The answer of the equation is $i=h/2$.

The next step is to substitute $N_{h - 2 \cdot i}$ with $N_{h=0}$ and $i$ with $h/2$ in the $(1)$ equation, which is:

$N_h > 2^{h/2} N_0 \ \ \ \ \Longleftrightarrow \ \ N_h > 2^{h/2}$

Proved.

$\endgroup$

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.