0
$\begingroup$

For AVL trees, which one of the following is possible as the tree size (expressed in term of the tree height h)? Recall that the size of a tree is the number of nodes in the tree.

A. $Θ(h^{2.1})$ B. $Θ(1.1^h)$ C. $Θ(1.9^h)$ D. $Θ(2.1^h)$


So this question came up on my midterm and I don't understand why the answer is C and not D. How I solved it is: $h=log(n)$ so $n=2^h$. Does it have anything to do with the fact that it's asking for a tight bound?

$\endgroup$
  • $\begingroup$ No binary tree can have more than $2.0^h$ elements. Only perfectly balanced trees with "enough" nodes reach that. $\endgroup$ – Albert Hendriks Aug 16 '18 at 19:34
0
$\begingroup$

Let $n$ be the size of an AVL tree with height $h$. Then we have $$ \log_2(n+1) \leq h \leq c\log_2(n+2) + b$$ where $c\approx 1.44$ and $b\approx -0.328$. So, $$ 0.8(1.6)^h\lt df^h=2^{-b/c}\left(2^{1/c}\right)^h=2^{(h-b)/c}-2 \leq n \leq 2^h -1 \lt 2^h $$ where $d\approx 0.85$ and $f\approx 1.618$.

Now you can see that the only number among 1.1, 1.9 and 2.1 that is between 1.6 and 2 is 1.9. Hence the answer is C.

I would not say it is asking for a tight bound.

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