patternMinor
Don't understand one step for AVL tree height log n proof
Viewed 0 times
heightlogproofoneunderstandstepforavltreedon
Problem
I came across a proof that an AVL tree has $O(\log n)$ height and there's one step which I do not understand.
Let $N_h$ represent the minimum number of nodes that can form an AVL tree of height $h$. Since we're looking for the minimum number of nodes, let its children's 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.
Let $N_h$ represent the minimum number of nodes that can form an AVL tree of height $h$. Since we're looking for the minimum number of nodes, let its children's 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.
Solution
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}}$$
$$ 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}}$$
Context
StackExchange Computer Science Q#27899, answer score: 6
Revisions (0)
No revisions yet.