Compreendendo Árvores na Computação #3

 

As árvores binárias de busca (BST) são estruturas de dados muito úteis para armazenar e organizar informações de forma rápida e eficiente. No entanto, ao inserir ou remover elementos de forma desordenada, a árvore pode se desequilibrar, tornando as operações de busca e inserção menos eficientes.

Para resolver este problema, foram criadas as árvores balanceadas, que garantem que a altura da árvore seja sempre menor do que a altura máxima possível para uma árvore binária de busca com o mesmo número de nós.

Uma das implementações mais conhecidas de árvores balanceadas é a AVL (Adelson-Velsky e Landis). Ela foi a primeira árvore balanceada a ser proposta e ainda é considerada uma das mais eficientes.

 

Fator de balanceamento

A chave para o balanceamento em uma árvore AVL é o fator de balanceamento (FB) de cada nó. Ele é calculado como a diferença entre a altura da subárvore esquerda e a altura da subárvore direita. Se o FB de um nó for -1, 0 ou 1, significa que a árvore está balanceada. Se o FB for maior do que 1 ou menor do que -1, significa que a árvore está desequilibrada e precisa ser reestruturada.

A imagem acima é um exemplo de uma árvore desbalanceada, enquanto na de baixo foi balanceada.

Para reestruturar a árvore, são utilizadas as operações de Rotação Simples à Esquerda (RSL), Rotação Simples à Direita (RSD), Rotação Dupla à Esquerda (RDL) e Rotação Dupla à Direita (RDR). Cada uma delas é aplicada dependendo do fator de balanceamento e da estrutura da árvore.

 

Rotações

Rotação à esquerda (Left Rotation)

A rotação à esquerda é realizada quando o nó desbalanceado está localizado na subárvore direita e a diferença de altura entre as subárvores esquerda e direita é maior que 1. Nessa rotação, o nó desbalanceado é movido para a esquerda, e seu filho à direita assume sua posição anterior. Isso equilibra a árvore e aumenta a altura da subárvore esquerda.

A figura abaixo mostra os passos ao inserirmos três nós com chaves 1,2 e 3:

 

Rotação à direita (Right Rotation)

A rotação à direita é realizada quando o nó desbalanceado está localizado na subárvore esquerda e a diferença de altura entre as subárvores esquerda e direita é maior que 1. Nessa rotação, o nó desbalanceado é movido para a direita, e seu filho à esquerda assume sua posição anterior. Isso equilibra a árvore e aumenta a altura da subárvore direita.

A figura abaixo mostra os passos ao inserirmos três nós com chaves 3,2 e 1:

 

Rotação dupla à esquerda (Left-Right Rotation):

A rotação dupla à esquerda é realizada quando o nó desbalanceado está localizado na subárvore esquerda e a diferença de altura entre as subárvores esquerda e direita é maior que 1. Nessa rotação, é realizada primeiramente uma rotação à direita no filho à esquerda do nó desbalanceado, e em seguida uma rotação à esquerda no próprio nó desbalanceado. Isso equilibra a árvore e aumenta a altura da subárvore esquerda.

A figura abaixo mostra os passos ao inserirmos três nós com chaves 3,1 e 2:

 

Rotação dupla à direita (Right-Left Rotation):

A rotação dupla à direita é realizada quando o nó desbalanceado está localizado na subárvore direita e a diferença de altura entre as subárvores esquerda e direita é maior que 1. Nessa rotação, é realizada primeiramente uma rotação à esquerda no filho à direita do nó desbalanceado, e em seguida uma rotação à direita no próprio nó desbalanceado. Isso equilibra a árvore e aumenta a altura da subárvore direita.

A figura abaixo mostra os passos ao inserirmos três nós com chaves 1,3 e 2:

 

Código

Aqui está o código das estruturas de uma árvore AVL em C:

As principais funções de uma árvore AVL são:

• A função de inserção, que insere um novo nó na árvore e verifica se é necessário reestruturar a árvore para mantê-la balanceada:

• As funções de rotação que realizam as reestruturações da árvore:

• A função de remover um nó específico da estrutura, levando em conta a necessidade de manter o equilíbrio da árvore:

 

Código completo

É importante notar que essas funções não são exclusivas para árvores AVL, elas também podem ser utilizadas em árvores binárias de busca simples. A diferença está na forma como a árvore é balanceada após cada operação, garantindo que a altura da árvore seja sempre a menor possível.

Vale ressaltar que essas funções são apenas uma implementação básica de uma árvore AVL e podem ser melhoradas ou adaptadas de acordo com as necessidades do seu projeto. Além disso, é recomendado sempre testar o código em diferentes casos de uso antes de implementá-lo em um sistema real.

 

Conclusão

Em resumo, as árvores balanceadas são estruturas de dados que garantem alta performance em operações de busca, inserção e remoção, mantendo um equilíbrio entre as alturas dos nós da árvore. A árvore AVL é uma das implementações mais comuns de árvores balanceadas, que garante uma altura máxima de log2(n) para árvores com n nós, garantindo assim uma complexidade temporal O(log n) para as principais operações.

 

Referências

Estrutura de Dados Descomplicada - Em Linguagem C , por André Backes

Obrigado pela leitura!