As árvores AVL não têm peso equilibrado?

Em uma pergunta anterior, havia uma definição de árvores com peso equilibrado e uma pergunta sobre árvores vermelho-pretas.

Esta pergunta é para fazer a mesma pergunta, mas para árvores AVL .

A questão é, dada a definição de árvores equilibradas como na outra questão,$\mu$

Há alguns tal que todas as árvores AVL suficientes grandes são -balanced?$\mu \gt 0$$\mu$

Presumo que exista apenas uma definição de árvores AVL e que não haja ambiguidade.

Reivindicação : Não, não existe tal .$\mu$

Prova : damos uma sequência infinita de árvores AVL de tamanho crescente, cujo valor de equilíbrio de peso tende a , contradizendo a afirmação.$0$

Seja a árvore completa da altura ; possui nós.$C_h$$h$$2^{h+1}-1$

Seja a árvore de Fibonacci de altura ; possui nós. [ 1 , 2 , TAoCP 3 ] H F H + 2 - $S_h$$h$$F_{h+2} - 1$

Agora deixe com a sequência de árvores que afirmamos ser um exemplo contrário. T h = N ( S h , C h$(T_h)_{i\geq 1}$$T_h = N(S_h,C_h)$

Considere o valor de balanceamento de peso da raiz de para alguns : h ∈ N$T_h$$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*}$

Isso conclui a prova.

Notação :

• $F_n$ é o th número de Fibonacci$n$
• & Phi; ≈ - $\phi \approx 1.6$ é a proporção áurea , seu conjugado.$\hat{\phi} \approx -0.62$
• f g lim n → ∞ f ( n $f \sim g$ significa que e são assintoticamente iguais, isto é, .$f$$g$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$

Nota bene : As árvores de Fibonacci são exatamente aquelas árvores AVL com menos nós para uma determinada altura (ou, equivalentemente, a altura máxima para um determinado número de nós).

Adendo : Como podemos criar árvores de Fibonacci se não ouvimos um professor mencioná-las? Bem, como seria uma árvore AVL de altura com o menor número possível de nós? Certamente, você precisa de uma raiz. Uma das subárvores precisa ter altura , e precisamos escolhê-la com o menor número possível de nós. O outro pode ter altura sem violar a condição de balanceamento de altura, e a escolhemos também com o menor número possível de nós. Em essência, construímos as árvores que queremos recursivamente! Estes são os quatro primeiros:h - 1 h - $h$$h-1$$h-2$

^{[ fonte ]}

Montamos uma recorrência para o número de nós na árvore assim construída com altura :$f(h)$$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*}$

A resolução leva a que usamos acima.$f(h) = F_{h+2} - 1$

A mesma prova é dada (com menos detalhes) nas árvores de busca binária de equilíbrio limitado por Nievergelt e Reingold (1972).