Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

In a previous question there was a definition of weight balanced trees and a question regarding red-black trees.

This question is to ask the same question, but for AVL trees.

The question is, given the definition of $\mu$-balanced trees as in the other question,

Is there some $\mu \gt 0$ such that all big enough AVL trees are $\mu$-balanced?

I presume there is only one definition of AVL trees and there is no ambiguity.

share|improve this question
add comment

1 Answer

up vote 13 down vote accepted

Claim: No, there is no such $\mu$.

Proof: We give an infinite sequence of AVL trees of growing size whose weight-balance value tends to $0$, contradicting the claim.

Let $C_h$ the complete tree of height $h$; it has $2^{h+1}-1$ nodes.

Let $S_h$ the Fibonacci tree of height $h$; it has $F_{h+2} - 1$ nodes. [1,2,TAoCP 3]

Now let $(T_h)_{i\geq 1}$ with $T_h = N(S_h,C_h)$ the sequence of trees we claim to be a counter example.

Consider the weight-balancing value of the root of $T_h$ for some $h \in \mathbb{N}_+$:

$\qquad \displaystyle \begin{align*} \frac{F_{h+2}}{2^{h+1} + F_{h+2} - 1} &= \frac{1}{1 + \frac{2^{h+1}}{F_{h+2}} - \frac{1}{F_{h+2}{}}} \\ &\sim \frac{F_{h+2}}{2^{h+1}} \\ &= \frac{\frac{1}{\sqrt{5}}(\phi^{h+2} - \hat{\phi}^{h+2})}{2^{h+1}} \\ &\sim \frac{\phi^{h+2}}{\sqrt{5}\cdot 2^{h+1}} \underset{h \to \infty}{\to} 0 \end{align*}$

This concludes the proof.

Notation:

  • $F_n$ is the $n$th Fibonacci number
  • $\phi \approx 1.6$ is the Golden Ratio, $\hat{\phi} \approx -0.62$ its conjugate.
  • $f \sim g$ means that $f$ and $g$ are asymptotically equal, i.e. $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$.

Nota bene: Fibonacci trees are exactly those AVL trees with the least nodes for a given height (or, equivalently, the maximum height for a given number of nodes).

Addendum: How can we come up with Fibonacci trees if we had not overheard a professor mentioning them? Well, what would an AVL tree of height $h$ with as few nodes as possible look like? Certainly, you need a root. One of the subtrees needs to have height $h-1$, and we have to choose it with as few nodes as possible. The other one can have height $h-2$ without violating the height balancing condition, and we choose it also with as few nodes as possible. In essence, we construct the trees we want recursively! These are the first four:

First four Fibonacci trees
[source]

We set up a recurrence for the number of nodes $f(h)$ in the thusly constructed tree with height $h$:

$\qquad \displaystyle \begin{align*} f(1) &= 1 \\ f(2) &= 2 \\ f(h) &= f(h-1) + f(h-2) + 1 \qquad n \geq 3 \end{align*}$

Solving it leads to $f(h) = F_{h+2} - 1$ which we used above.


The same proof is given (with less detail) in Binary search trees of bounded balance by Nievergelt and Reingold (1972).

share|improve this answer
    
Thank you...... –  Aryabhata Mar 15 '12 at 19:06
2  
@Aryabhata Do you think an explanation is in order as to how to come up with those Fibonacci trees? –  Raphael Mar 15 '12 at 21:21
    
Yes, the way to get the answer would definitely help. –  Aryabhata Mar 15 '12 at 22:39
    
Since I can't upvote your answer again, +1 to your comment :-) –  Aryabhata Mar 16 '12 at 0:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.