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

22

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,μ

Há alguns tal que todas as árvores AVL suficientes grandes são -balanced?μμ>0μ

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

Aryabhata
fonte

Respostas:

18

Reivindicação : Não, não existe tal .μ

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. hChh2h+11

Seja a árvore de Fibonacci de altura ; possui nós. [ 1 , 2 , TAoCP 3 ] H F H + 2 - 1ShhFh+21

Agora deixe com a sequência de árvores que afirmamos ser um exemplo contrário. T h = N ( S h , C h )(Th)i1Th=N(Sh,Ch)

Considere o valor de balanceamento de peso da raiz de para alguns : h N +ThhN+

Fh+22h+1+Fh+21=11+2h+1Fh+21Fh+2Fh+22h+1=15(ϕh+2ϕ^h+2)2h+1ϕh+252h+1h0

Isso conclui a prova.

Notação :

  • Fn é o th número de Fibonaccin
  • & Phi;- 0,62ϕ1.6 é a proporção áurea , seu conjugado.ϕ^0.62
  • f g lim n f ( n )fg significa que e são assintoticamente iguais, isto é, .fglimnf(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 - 2hh1h2

Primeiras quatro árvores de Fibonacci
[ fonte ]

Montamos uma recorrência para o número de nós na árvore assim construída com altura :hf(h)h

f(1)=1f(2)=2f(h)=f(h1)+f(h2)+1n3

A resolução leva a que usamos acima.f(h)=Fh+21


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

Rafael
fonte