AVL trees are not weight-balanced?

Problem Detail: 

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.

Asked By : Aryabhata

Answered By : Raphael

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:

^[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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/421