Lições Interativas de Matemática e Ciências

Visualizador de árvores BST / AVL

Insira valores e observe a árvore crescer. Mude para o modo AVL para ver o rebalanceamento automático.

A carregar a simulação interativa...

Entrada ordenada é a pior entrada 🖖

Uma árvore binária de busca ganha sua velocidade da forma, e a forma vem inteiramente da ordem de inserção. Dê a esta ferramenta 10, 20, 30, 40, 50, 60, 70 nessa ordem: cada chave é maior que a anterior, então cada uma pendura à direita da precedente e a árvore vira uma corrente reta de altura 7. É uma lista ligada carregando o custo dos ponteiros de árvore, e achar o 70 custa sete comparações em vez de três. Nada nos dados era patológico — eles apenas já estavam ordenados, que é como os dados normalmente chegam. Troque esses mesmos sete valores para o modo AVL e as rotações devolvem a altura para 3. Esse é todo o argumento a favor das árvores auto-balanceadas.

Cada passo descarta a metade 🖖

Uma árvore binária de busca funciona como procurar uma palavra no dicionário: em cada nó você compara e descarta de imediato toda a metade que não pode conter o seu valor. Por isso uma árvore bem formada encontra qualquer valor entre um milhão de entradas em cerca de 20 comparações. Mas o formato depende inteiramente da ordem de inserção — digite os valores já ordenados (10, 20, 30, …) e veja a árvore desabar em uma única linha inclinada, tão lenta quanto percorrer uma lista um a um.

A razão áurea se esconde nas árvores AVL 🖖

Mude para o modo AVL e pergunte: qual a maior altura que uma árvore balanceada pode atingir para um dado número de nós? A resposta esconde a razão áurea. A árvore AVL válida mais esparsa de cada altura é uma árvore de Fibonacci, construída a partir de duas árvores de Fibonacci menores, de modo que suas quantidades de nós seguem a sequência de Fibonacci. É por isso que o limite de altura carrega a constante 1.44 — ela é exatamente 1 / log₂(φ), com φ ≈ 1.618, a razão áurea.

ÁRVORES BST E AVL — OS MESMOS VALORES, QUATRO ÁRVORES DIFERENTES

Qual árvore a sua ordem de inserção vai produzir?

A forma de uma árvore binária de busca não é decidida pelos valores que ela guarda, e sim pela ordem em que eles chegaram — e essa forma é todo o preço: cada busca, inserção e remoção desce da raiz até uma folha, então o que custa é a altura. Duas perguntas resolvem em que caso você está: os valores chegaram já ordenados, e existe algo rotacionando-os de volta ao equilíbrio?

BST balanceada — a ordem de chegada se entrelaçou h = 3 = ⌈log₂(n + 1)⌉
BST degenerada — entrada ordenada e nada rebalanceando h = n = 7 ⇒ O(n)
Rebalanceamento AVL — a rotação é local e barata |hL − hR| > 1 → ↻, h = 3
AVL com entrada ordenada — o caso para o qual as rotações existem ↻ × 4 ⇒ h = 3 < 7

01

BST balanceada — a ordem de chegada se entrelaçou

O que você sabe: Modo BST puro, sem rotações. Os valores chegam começando pelo meio, então cada nova chave cai em uma subárvore ainda baixa e nenhum lado se adianta ao outro.

Quanto custa: h = 3 = ⌈log₂(n + 1)⌉

Exemplo resolvido: 50, 30, 70, 20, 40, 60, 80 → raiz 50, 7 nós, altura 3 — exatamente o ideal ⌈log₂(7+1)⌉ = 3, de modo que a busca mais profunda custa 3 comparações

Abrir este caso: Balanceado
BST balanceada — a ordem de chegada se entrelaçou. Sete nós em três níveis: cada folha à mesma distância da raiz, e não dá para fazer melhor. Modo BST puro, sem rotações. Os valores chegam começando pelo meio, então cada nova chave cai em uma subárvore ainda baixa e nenhum lado se adianta ao outro.
Sete nós em três níveis: cada folha à mesma distância da raiz, e não dá para fazer melhor.

02

BST degenerada — entrada ordenada e nada rebalanceando

O que você sabe: Modo BST puro outra vez, mas os valores chegam em ordem crescente. Cada um é maior do que tudo o que já está guardado, então vai para a direita, todas as vezes.

Quanto custa: h = n = 7 ⇒ O(n)

Exemplo resolvido: 10, 20, 30, 40, 50, 60, 70 → raiz 10, 7 nós, altura 7 em vez de 3; encontrar o 70 custa 7 comparações, e a ferramenta rotula o resultado como lista encadeada

Abrir este caso: Degenerado
BST degenerada — entrada ordenada e nada rebalanceando. Cada nó tem um único filho: a busca percorre os sete níveis, não mais rápido que varrer um vetor. Modo BST puro outra vez, mas os valores chegam em ordem crescente. Cada um é maior do que tudo o que já está guardado, então vai para a direita, todas as vezes.
Cada nó tem um único filho: a busca percorre os sete níveis, não mais rápido que varrer um vetor.

03

Rebalanceamento AVL — a rotação é local e barata

O que você sabe: Modo AVL. Depois de cada inserção a árvore volta subindo em direção à raiz, e o primeiro nó cujas duas alturas de subárvore diferem em mais de 1 é rotacionado. Os selos ao lado de cada nó mostram a altura esquerda menos a direita.

Quanto custa: |hL − hR| > 1 → ↻, h = 3

Exemplo resolvido: 30, 20, 10, 25, 35, 40 no modo AVL → inserir 10 inclina o nó 30 para +2, e uma rotação à direita ergue o 20 ao seu lugar; mais tarde o 40 inclina um nó para −2 e uma rotação à esquerda conserta. 2 rotações, 6 nós, altura 3.

Abrir este caso: Rebalanceamento AVL
Rebalanceamento AVL — a rotação é local e barata. Os nós com anel foram erguidos por uma rotação; cada selo está de novo dentro de ±1. Modo AVL. Depois de cada inserção a árvore volta subindo em direção à raiz, e o primeiro nó cujas duas alturas de subárvore diferem em mais de 1 é rotacionado. Os selos ao lado de cada nó mostram a altura esquerda menos a direita.
Os nós com anel foram erguidos por uma rotação; cada selo está de novo dentro de ±1.

04

AVL com entrada ordenada — o caso para o qual as rotações existem

O que você sabe: Modo AVL, alimentado exatamente com os valores que produziram a corrente dois casos acima. Cada inserção cai na ponta direita e empurra o balanço de algum ancestral para −2, então quase toda inserção dispara uma correção.

Quanto custa: ↻ × 4 ⇒ h = 3 < 7

Exemplo resolvido: 10, 20, 30, 40, 50, 60, 70 no modo AVL → 4 rotações à esquerda, e a raiz termina como 40 em vez de 10. Altura 3, não 7 — a mesma entrada, os mesmos sete nós, menos da metade da profundidade.

Abrir este caso: Ordenado em AVL
AVL com entrada ordenada — o caso para o qual as rotações existem. Os mesmos valores ordenados do caso 2, rotacionados de volta a três níveis conforme chegam. Modo AVL, alimentado exatamente com os valores que produziram a corrente dois casos acima. Cada inserção cai na ponta direita e empurra o balanço de algum ancestral para −2, então quase toda inserção dispara uma correção.
Os mesmos valores ordenados do caso 2, rotacionados de volta a três níveis conforme chegam.
Referências (1)
  • Insight block 3 — the Fibonacci tree that sets the AVL height bound: D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.2.3. Addison-Wesley, 1998. ISBN 978-0-201-89685-5 — the sparsest legal AVL tree of each height, and the logφ bound that follows.

Problema resolvido na íntegra

  1. Uma árvore de altura sete com sete nós 5 passos

    Sete nós e uma árvore de altura sete. Uma árvore equilibrada teria altura 3. Determine o que os dados de entrada fizeram — e quanto isso custa à escala.

    1. As chaves por omissão são 10, 20, 30, … — já ordenadas. Seguindo a regra de inserção, cada nova chave é maior do que todas as presentes na árvore, pelo que vai para a direita, sempre.

    2. O resultado não apresenta qualquer ramificação. Cada nó tem um único filho, pelo que a estrutura é uma lista ligada que por acaso está desenhada como uma árvore, sendo a altura igual ao número de nós.

    3. A melhor altura possível para sete nós é 3, porque uma árvore de altura h contém no máximo 2ʰ − 1 nós e 2³ − 1 = 7 exatamente. Estes dados de entrada atingem o pior caso quando o caso equilibrado estava disponível.

    4. A pesquisa percorre a partir da raiz, pelo que o custo é a altura: 7 comparações aqui contra 3.

    5. A razão entre os valores é o ponto essencial, e aumenta. Com um milhão de nós, a altura equilibrada é 20 e a altura com dados de entrada ordenados é um milhão.

    Resposta

    A ferramenta apresenta uma altura de 7 para 7 nós, contra um ideal de 3. A lição é que O(log n) nunca foi uma propriedade da árvore binária de pesquisa — é uma propriedade da ordem de inserção, e a ordem mais natural que um programador lhe pode fornecer, dados ordenados, é precisamente a que a destrói. Essa é a razão de ser das árvores AVL e rubro-negras: custam uma rotação ou duas por inserção para tornar a garantia incondicional. Mude o modo para AVL e observe as mesmas sete chaves a estabilizar na altura 3.

· Atualizado

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo