4
$\begingroup$

I have came across following problem:

What is the maximum height of any AVL-tree with 7 nodes?

The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows:

$n(h)=n(h-1)+n(h-2)+1$

$n(0)=1$

$n(1)=2$

So if we follow this recurrence, we get the height of the AVL tree with 7 nodes = 3 as follows

$n(2)=n(1)+n(0)+1=2+1+1=4$

$n(\color{red}{3})=n(2)+n(1)+1=4+2+1=7$

However I find two formulae, both listed on this page:

  1. The first one is stricter one:

    $h < 1.475 \times log_2(n(h)) - 1.475$

    According to this formula, I get

    $h < 1.475 \times log_2(7)-1.475$

    $h<\color{red}{2.665}$

  2. The second one is rough estimate and it is taken from Goodrich's book:

    $h < 2 \times log_2(n(h)) + 2$

    According to this formula, I get

    $h < 2 \times log_2(7) + 2$

    $h<\color{red}{7.61}$

So with these different answers, I don't get what should I infer. Am I doing any miscalculations? Or should I just stick to what is yielded by recurrence and ignore formulae as they are mere estimates? Or should the first formula have ceil function to give perfect answer rather than the estimates as follows?

$h \color{red}{=} \color{red}{\lceil} 1.475 \times log_2(n(h)) - 1.475 \color{red}{\rceil}$

$\endgroup$
  • $\begingroup$ Do the respective authors claim that the inequalities hold for all $n$, or just for "sufficiently large" ones? (There is not reasons why different authors should not have different calculations and get to different upper bounds.) $\endgroup$ – Raphael Apr 10 '16 at 16:40
  • $\begingroup$ there is absolutely no reason to think that the inequality hold for $n$ in specific range...at least that's what it looks like if you look at their proofs. Else those authors would have made it an explicit point that those formula apply on certain range of values of $n$. $\endgroup$ – anir Apr 10 '16 at 18:26
  • $\begingroup$ Note that $n(h) = fib(h+3) - 1$ where $fib(k)$ stands for the $k$-th Fibonacci number. You can check this by induction. $\endgroup$ – chi May 11 '16 at 17:27
2
$\begingroup$

Perhaps the simplest way out is to solve the recurrence explicitly. Let $m(h) = n(h) + 1$. Then $m(h)$ satisfies the recurrence $$ m(h) = n(h) + 1 = n(h-1) + n(h-2) + 2 = m(h-1) + m(h-2). $$ The initial conditions are $m(0) = 2$ and $m(1) = 3$. Define $F(h) = m(h-3)$, so that $F(3) = 2$, $F(4) = 3$, and $F(h) = F(h-1) + F(h-2)$ for $h > 4$. It is well-known that $$ F(n) = \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]. $$ Since $m(h) = F(h+3)$ and $n(h) = m(h)-1$, we see that $n(h) = F(h+3)-1$ and so $$ \begin{align*} n(h) &= \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^{h+3} - \left(\frac{1-\sqrt{5}}{2}\right)^{h+3}\right] - 1 \\ &= \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h - \frac{2-\sqrt{5}}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^h - 1. \end{align*} $$ The second term is very small, and in particular $$ \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h - 2 < n(h) < \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h. $$ This shows that $$ \log_{(1+\sqrt{5}))/2} n(h) < h + \log_{(1+\sqrt{5}))/2} < \log_{(1+\sqrt{5}))/2} [n(h)+2], $$ from which you can deduce whichever excellent bounds you want.

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