Balanceamento de Árvores: Árvores AVL

4.1 Problemas de árvores não balanceadas

Em árvores comuns (não balanceadas), ao adicionar elementos, podem ocorrer alguns efeitos desagradáveis.

1. Aumento da altura da árvore:

Em árvores não balanceadas, a altura pode chegar a n (onde n é o número de nós), o que leva a uma queda de desempenho.

O tempo de execução das operações principais (busca, inserção, remoção) no pior caso se torna O(n).

2. Distribuição desigual de nós:

Em árvores não balanceadas, algumas subárvores podem conter significativamente mais nós do que outras, o que leva a um uso ineficiente de memória e aumento no tempo de processamento.

3. Piora do tempo de execução das operações:

Em árvores não balanceadas, as operações de busca, inserção e remoção requerem mais tempo devido à altura aumentada da árvore.

Exemplo de árvore não balanceada:

Neste exemplo, a árvore acaba se transformando em uma lista ligada, e o tempo de execução das operações se torna linear.

4.2 Definição da árvore AVL e suas propriedades

A árvore AVL (nomeada em homenagem aos seus inventores, Adelson-Velsky e Landis) é um tipo de árvore binária de busca balanceada, onde para qualquer nó, a diferença das alturas de suas subárvores esquerda e direita não excede 1.

Propriedades da árvore AVL:

1. Balanceamento:

A diferença das alturas das subárvores esquerda e direita de qualquer nó não excede 1.

Isso garante uma altura da árvore de O(log n), onde n é o número de nós, garantindo operações eficientes de busca, inserção e remoção.

2. Árvore binária de busca:

A árvore AVL possui todas as propriedades de uma árvore binária de busca: para qualquer nó, todas as chaves na subárvore esquerda são menores que a chave do nó, e todas as chaves na subárvore direita são maiores que a chave do nó.

3. Balanceamento automático:

Após cada operação de inserção ou remoção, o balanceamento da árvore é realizado para manter suas propriedades.

4.3 Exemplos de balanceamento de árvores

Rotações são operações realizadas para restaurar o balanceamento em uma árvore AVL após inserções ou remoções de nós. Existem quatro tipos de rotações: rotação à esquerda, à direita, esquerda-direita e direita-esquerda.

1. Rotação à esquerda (Left Rotation):

Na rotação à esquerda, o nó x sobe, e seu nó filho direito y se torna seu pai. A subárvore esquerda de y se torna a subárvore direita de x.

2. Rotação à direita (Right Rotation):

Na rotação à direita, o nó x sobe, e seu nó filho esquerdo y se torna seu pai. A subárvore direita de y se torna a subárvore esquerda de x.

3. Rotação esquerda-direita (Left-Right Rotation):

Primeiro, uma rotação à esquerda é realizada no nó filho esquerdo, seguido por uma rotação à direita no próprio nó.

4. Rotação direita-esquerda (Right-Left Rotation):

Primeiro, uma rotação à direita é realizada no nó filho direito, seguido por uma rotação à esquerda no próprio nó.

4.4 Operações principais em árvores AVL

As operações principais em árvores AVL incluem inserção, remoção e busca.

Inserção (Insertion)

É preciso inserir um novo nó na árvore AVL e balanceá-lo, se necessário.

Passos:

1. Inserção de nó:
   • Começamos pela raiz da árvore e recursivamente encontramos o lugar adequado para o novo nó, comparando seu valor com os nós atuais.
   • Inserimos o novo nó na posição encontrada, como em uma árvore binária de busca comum.
2. Atualização das alturas:
   • Após a inserção, atualizamos as alturas de todos os nós no caminho do novo nó até a raiz.
3. Balanceamento da árvore:
   • Verificamos o balanceamento de cada nó no caminho do novo nó até a raiz.
   • Se o balanceamento de algum nó estiver quebrado (diferença de altura das subárvores esquerda e direita maior que 1), realizamos a rotação correspondente para restaurar o balanceamento.

Exemplo:

2. Remoção (Deletion)

É preciso remover um nó da árvore AVL e balanceá-lo, se necessário.

Passos:

1. Busca e remoção de nó:

• Começamos pela raiz da árvore e recursivamente encontramos o nó para remoção.
• Removemos o nó como em uma árvore binária de busca comum:
• Se o nó for uma folha, simplesmente o removemos.
• Se o nó tiver um filho, substituímos o nó pelo seu filho.
• Se o nó tiver dois filhos, encontramos o menor nó na subárvore direita (ou o maior na esquerda), copiamos seu valor para o nó que será removido e recursivamente removemos o menor nó na subárvore direita.

2. Atualização das alturas:

• Após a remoção, atualizamos as alturas de todos os nós no caminho do nó removido até a raiz.

3. Balanceamento da árvore:

• Verificamos o balanceamento de cada nó no caminho do nó removido até a raiz.
• Se o balanceamento de algum nó estiver quebrado, realizamos a rotação correspondente para restaurar o balanceamento.

Exemplo:

3. Busca (Search)

Precisamos encontrar um nó com um valor específico na árvore AVL.

Passos:

1. Busca recursiva:

• Começamos pela raiz da árvore e recursivamente comparamos o valor buscado com os nós atuais.
• Se o valor for menor que o nó atual, vamos para a subárvore esquerda.
• Se o valor for maior que o nó atual, vamos para a subárvore direita.
• Se o valor coincidir com o nó atual, retornamos esse nó.

Exemplo: