0
$\begingroup$

Q: Prove that for any AVL tree that has $n$ nodes ($n\geq 1$)
and has a height of $h$ this property is true:
$n \geq F(h)$ where $F(h)$ is the $h$-th element in the Fibonacci sequence:
$F(0) =0, F(1)=1, F(n) = F(n-1) + F(n-2) ~~~~\forall n \geq 2$

This is my go:

We know it is an AVL tree so $h = \log_2{n}$
Thus we need to prove that $n \geq F( \log_2{n})$

$F(\log_2{n})= F(\log_2{n}-1)+F(\log_2{n}-2)$
However I am stuck from here, I don't know what this helps me with and I am clueless on what to do next..
I would appreciate your help, thank you!

$\endgroup$
1
$\begingroup$

Let $T$ be an AVL tree of $n > 0$ nodes having height $h \ge 0$. You can prove that $n > F(h)$ by induction on $h$.

For $h=0$ the claim is true since $n=1$ and $1 > 0 = F(0) = F(h)$. For $h=1$ the claim is true since $n \ge 2$ and $2 > 1 = F(1) = F(h)$.

For $h \ge 2$, let $r$ be the root of the AVL tree. The subtree $T_\ell$ rooted in the left child of $r$ and the subtree $T_r$ rooted in the right child of $r$ exist are both AVL trees. Moreover, since $T$ is balanced, at least one tree $T'$ among $T_\ell$ and $T_r$ must have height $h-1$, while the other tree $T''$ must have height at least $h-2$.

By inductive hypothesis the number $n'$ of nodes of $T'$ is more than $F(h-1)$, while the number of nodes of $T''$ is more than $F(h-2)$. Therefore, the number of nodes $n$ is: $$ n = 1 + n' + n'' \ge 3 + F(h-1) + F(h-2) = 3 + F(h) > F(h). $$

| cite | improve this answer | |
$\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.