Guia de estudos de árvores AVL

Altura de uma árvore

Busca em Árvore Binária

Pode-se verificar que todo filho esquerdo contém um elemento menor do que o elemento armazenado no seu pai e todo filho direito contém um elemento maior ou igual do que o elemento armazenado no seu pai. Um elemento a pode ser pesquisado em uma árvore binária utilizando-se um algoritmo de travesia como o colocado a seguir:

Dessa maneira, a cada interação é esperado que o número de possibilidades seja dividido por dois O(log n).

O que é uma Árvore AVL?

Uma Árvore AVL é um tipo especial de Árvore Binária de Busca (ABB) que é auto-balanceável. Ela mantém sua altura a menor possível, garantindo que operações como busca, inserção e remoção sejam extremamente eficientes, com complexidade de tempo de O(log n) no pior caso. O seu nome vem da junção das iniciais de seus criadores: Adelson Velsky e Landis.

Enquanto uma ABB normal pode se degenerar em uma estrutura semelhante a uma lista ligada (levando a um desempenho O(n)), a AVL evita isso realizando pequenas reorganizações chamadas rotações sempre que um desbalanceamento é detectado.

Uma árvore balanceada é uma árvore binária na qual a diferença entre a altura das duas subárvores (esquerda e direita) de qualquer nó da árvore não é maior do que 1.

Fator de Balanceamento

Em uma árvore balanceada, o balanceamento de cada nó é –1, 0 ou 1.

• Balanceamento -1: altura da subárvore esquerda é menor do que a altura da direita


• Balanceamento 0: ambas as subárvores possuem a mesma altura


• Balanceamento 1: a altura da subárvore esquerda é maior do que a altura da direita.

A "mágica" da AVL reside em monitorar o Fator de Balanceamento (FB) de cada nó. O FB de um nó é calculado da seguinte forma:

FB = Altura(Subárvore Esquerda) - Altura(Subárvore Direita)

Se, após uma inserção ou remoção, o FB de algum nó se torna -2 ou 2, a árvore está desbalanceada e uma rotação é necessária para corrigir o problema.

As Rotações: Corrigindo o Desbalanceamento

Existem quatro tipos de desbalanceamento que podem ocorrer, cada um corrigido por um tipo específico de rotação.

1. Rotação Simples à Direita (Caso Esquerda-Esquerda)

Ocorre quando um nó (Z) fica desbalanceado (FB = 2) porque seu filho esquerdo (Y) também está "pesado" para a esquerda (FB = 1). A solução é uma única rotação à direita em Z.

Algoritmo

• Node novaRaiz = raiz.esquerda
• Node temp = novaRaiz.direita
• novaRaiz.direita = raiz
• raiz.esquerda = temp

2. Rotação Simples à Esquerda (Caso Direita-Direita)

É o espelho do caso anterior. Ocorre quando um nó (Z) fica desbalanceado (FB = -2) porque seu filho direito (Y) também está "pesado" para a direita (FB = -1). A solução é uma única rotação à esquerda em Z.

Algoritmo

• Node novaRaiz = raiz.direita
• Node temp = novaRaiz.esquerda
• novaRaiz.esquerda = raiz
• raiz.direita = temp

3. Rotação Dupla: Esquerda-Direita (Caso Esquerda-Direita)

Este é um caso "em zigue-zague". O nó (Z) fica desbalanceado para a esquerda (FB = 2), mas seu filho esquerdo (Y) está pesado para a direita (FB = -1). Para corrigir, são necessários dois passos:

• Passo 1: Uma rotação à esquerda no filho (Y).
• Passo 2: Uma rotação à direita no nó original (Z).

4. Rotação Dupla: Direita-Esquerda (Caso Direita-Esquerda)

O espelho do caso Esquerda-Direita. O nó (Z) fica desbalanceado para a direita (FB = -2), mas seu filho direito (Y) está pesado para a esquerda (FB = 1). A correção também é em dois passos:

• Passo 1: Uma rotação à direita no filho (Y).
• Passo 2: Uma rotação à esquerda no nó original (Z).