Estruturas de Dados: Conhecendo e Dominando AVL Tree / Árvore AVL
Algoritmos são procedimentos ou fórmulas utilizados para resolver problemas, enquanto estruturas de dados, como AVL Tree / Árvore AVL, são mecanismos que armazenam e organizam informações de maneira eficiente. Juntos, formam a base fundamental da ciência da computação.
O que é AVL Tree / Árvore AVL?
Uma AVL Tree / Árvore AVL é uma árvore binária de busca auto-balanceada. O nome “AVL” é derivado dos inventores, Adelson-Velsky e Landis, que a introduziram em 1962. A principal característica que diferencia a Árvore AVL das árvores binárias de busca convencionais é que ela mantém um equilíbrio durante as operações de inserção e remoção. Esse equilíbrio é garantido assegurando que, para qualquer nó da árvore, as alturas das duas subárvores desse nó diferem no máximo por uma unidade.
Manter esse equilíbrio garente que a árvore tenha uma altura logarítmica em relação ao número de nós, o que, por sua vez, garante operações eficientes de busca, inserção e remoção, todas com uma complexidade de tempo aproximada de O(log n).
A história por trás da AVL Tree / Árvore AVL
A ideia por trás da AVL Tree / Árvore AVL surge da necessidade de otimizar as operações de busca em árvores binárias. Enquanto uma árvore binária de busca permite inserções, remoções e buscas eficientes em sua forma ideal (quando está perfeitamente balanceada), na prática, operações repetidas podem desequilibrá-la, fazendo com que ela se assemelhe a uma lista ligada, o que degrada significativamente sua eficiência.
G.M. Adelson-Velsky e E.M. Landis reconheceram esse problema e, em 1962, introduziram a Árvore AVL como solução. O conceito central era manter a árvore balanceada a cada inserção ou remoção, garantindo que a diferença de alturas entre as subárvores esquerda e direita de qualquer nó nunca excedesse uma unidade.
Esse balanceamento assegura que a árvore mantém uma forma aproximadamente ideal, evitando o problema do desequilíbrio que pode ocorrer em árvores binárias de busca convencionais. Com isso, as operações de busca, inserção e remoção permanecem eficientes, mesmo após muitas operações.
O que são Estruturas de Dados de Árvore Binária?
Uma árvore binária é uma estrutura de dados hierárquica na qual cada nó tem, no máximo, dois filhos: geralmente referidos como filho esquerdo e filho direito. Cada nó contém um valor (ou chave) e dois ponteiros, um para cada filho. A raiz é o nó superior da árvore e não possui um nó pai, enquanto todos os outros nós são conectados por exatamente um caminho à raiz. As árvores binárias são usadas para implementar estruturas de dados como árvores binárias de busca, montes e árvores sintáticas.
O que é o balanceamento na AVL Tree / Árvore AVL?
Balanceamento, no contexto de árvores binárias, refere-se à garantia de que a árvore mantenha uma configuração em que as operações, como inserção, busca e remoção, sejam eficientes. Uma árvore é considerada balanceada quando a diferença de alturas entre subárvores esquerda e direita de qualquer nó é no máximo um. O balanceamento evita que a árvore se torne demasiadamente inclinada ou “degenerada” em uma lista vinculada, o que poderia comprometer a eficiência das operações. Estruturas de Dados como a Árvore AVL e Árvore Vermelho-Preto implementam técnicas específicas para manter o balanceamento após cada operação.
Qual é a complexidade das Estruturas de Dados do AVL Tree / Árvore AVL?
A Árvore AVL garante operações eficientes ao manter a árvore balanceada. Sua complexidade em termos de notação Big O é:
- Inserção: O(log n)
- Busca: O(log n)
- Remoção: O(log n)
Explicação:
A notação O(log n) descreve algoritmos que se dividem aproximadamente pela metade a cada passo. No contexto de árvores binárias de busca balanceadas, como a Árvore AVL, essa complexidade significa que, no pior caso, a operação terá que percorrer a altura da árvore. Devido ao balanceamento garantido pela Árvore AVL, a altura da árvore é sempre proporcional ao logaritmo do número de elementos (n).
Para entender intuitivamente, imagine que você está procurando uma palavra em um dicionário físico. Em vez de começar do início e passar palavra por palavra, você abre o livro na metade, e dependendo se a palavra está antes ou depois dessa página, você divide novamente a metade relevante. Continuando dessa forma, você reduz rapidamente o número de páginas que precisa verificar. Esse processo é análogo à busca em uma Árvore AVL, e é por isso que a complexidade é O(log n).
Aplicando a Estruturas de Dados AVL Tree / Árvore AVL
Nesta implementação, temos a representação de uma Árvore AVL através das classes No e Arvore. A classe No define os elementos individuais da árvore, armazenando o valor do nó, referências para seus filhos Esquerda e Direita, e a Altura do nó. A classe Arvore abstrai as operações e comportamentos da árvore AVL. Durante o processo de inserção, o caminho percorrido é mantido numa pilha, permitindo o reequilíbrio subsequente dos nós. As funções RotacionarEsquerda e RotacionarDireita são empregadas para assegurar que a árvore mantenha seu balanceamento após cada inserção. Adicionalmente, a árvore pode ser navegada em ordem através do método NavegarOrdenado, que retorna os valores em uma sequência ordenada.
Essencialmente, o código aproveita a natureza intrínseca das árvores AVL de auto-balanceamento para garantir que as operações de busca mantenham uma eficiência de tempo logarítmico. O método de Inserir, ao combinar as operações de rotação e rastrear o caminho de inserção, assegura que a árvore permaneça equilibrada, proporcionando assim consultas eficientes e ordenação inerente dos elementos.
public class No<T>
{
public T Valor;
public No<T> Esquerda;
public No<T> Direita;
public int Altura;
public No(T valor)
{
Valor = valor;
Altura = 1;
}
}
public class Arvore<T> where T : IComparable<T>
{
private No<T>? raiz;
public No<T> Raiz => raiz!;
public void Inserir(T valor)
{
if (raiz == null)
{
raiz = new No<T>(valor);
return;
}
Stack<No<T>> caminho = new Stack<No<T>>();
No<T> atual = raiz;
while (atual != null)
{
caminho.Push(atual);
if (valor.CompareTo(atual.Valor) < 0)
atual = atual.Esquerda;
else if (valor.CompareTo(atual.Valor) > 0)
atual = atual.Direita;
else
return;
}
No<T> novoNo = new No<T>(valor);
if (valor.CompareTo(caminho.Peek().Valor) < 0)
caminho.Peek().Esquerda = novoNo;
else
caminho.Peek().Direita = novoNo;
Arvore<T>.Balancear(caminho);
}
private static void Balancear(Stack<No<T>> caminho)
{
while (caminho.Count > 0)
{
No<T> no = caminho.Pop();
no.Altura = 1 + Math.Max(Arvore<T>.ObterAltura(no.Esquerda), Arvore<T>.ObterAltura(no.Direita));
int balanceamento = Arvore<T>.ObterAltura(no.Esquerda) - Arvore<T>.ObterAltura(no.Direita);
if (balanceamento > 1)
{
if (Arvore<T>.ObterAltura(no.Esquerda.Esquerda) < Arvore<T>.ObterAltura(no.Esquerda.Direita))
no.Esquerda = Arvore<T>.RotacionarEsquerda(no.Esquerda);
Arvore<T>.RotacionarDireita(no);
}
else if (balanceamento < -1)
{
if (Arvore<T>.ObterAltura(no.Direita.Direita) < Arvore<T>.ObterAltura(no.Direita.Esquerda))
no.Direita = Arvore<T>.RotacionarDireita(no.Direita);
Arvore<T>.RotacionarEsquerda(no);
}
}
}
private static No<T> RotacionarEsquerda(No<T> x)
{
No<T> y = x.Direita;
x.Direita = y.Esquerda;
y.Esquerda = x;
x.Altura = Math.Max(Arvore<T>.ObterAltura(x.Esquerda), Arvore<T>.ObterAltura(x.Direita)) + 1;
y.Altura = Math.Max(Arvore<T>.ObterAltura(y.Esquerda), Arvore<T>.ObterAltura(y.Direita)) + 1;
return y;
}
private static No<T> RotacionarDireita(No<T> y)
{
No<T> x = y.Esquerda;
y.Esquerda = x.Direita;
x.Direita = y;
y.Altura = Math.Max(Arvore<T>.ObterAltura(y.Esquerda), Arvore<T>.ObterAltura(y.Direita)) + 1;
x.Altura = Math.Max(Arvore<T>.ObterAltura(x.Esquerda), Arvore<T>.ObterAltura(x.Direita)) + 1;
return x;
}
private static int ObterAltura(No<T> no)
{
return no?.Altura ?? 0;
}
public List<T> NavegarOrdenado()
{
List<T> resultado = new();
NavegarOrdenado(raiz, resultado);
return resultado;
}
private void NavegarOrdenado(No<T> no, List<T> resultado)
{
if (no == null) return;
NavegarOrdenado(no.Esquerda, resultado);
resultado.Add(no.Valor);
NavegarOrdenado(no.Direita, resultado);
}
}FAQ: Perguntas Frequentes
1. O que é uma árvore AVL?
Uma árvore AVL é uma árvore binária de busca auto-balanceada. Para cada nó, a altura das duas subárvores filhas difere no máximo por um, garantindo que a árvore esteja balanceada e que as operações de adição, remoção e busca sejam eficientes.
2. Como a árvore AVL se auto-balanceia?
Sempre que um nó é inserido ou removido, a árvore verifica o fator de balanceamento. Se o fator exceder 1 ou -1, então são realizadas operações de rotação para balancear a árvore.
3. O que são rotações em uma árvore AVL?
Rotações são operações realizadas para corrigir o desequilíbrio em uma árvore AVL. Existem quatro tipos principais: rotação simples à direita, rotação simples à esquerda, rotação dupla à direita e rotação dupla à esquerda.
4. Como a inserção funciona em uma árvore AVL?
A inserção começa como em qualquer árvore binária de busca: o novo nó é inserido de forma apropriada (esquerda ou direita, com base na comparação). Após a inserção, a árvore é verificada para desequilíbrios e, se necessário, realiza-se a rotação para balanceá-la.
5. O que é fator de balanceamento?
É a diferença entre as alturas das subárvores esquerda e direita de um nó. Uma árvore AVL garante que o fator de balanceamento de qualquer nó esteja no intervalo [-1, 1].
6. Árvores AVL são aplicáveis para qualquer tipo de dados?
Sim, desde que o tipo de dado possua uma forma de comparação, ou seja, é possível determinar se um elemento é menor, igual ou maior que outro.
7. Qual é a vantagem de usar árvores AVL sobre árvores binárias de busca regulares?
Árvores AVL garantem que a árvore esteja sempre balanceada, evitando o pior caso de árvores binárias de busca onde a árvore se degenera em uma lista encadeada, tornando as operações ineficientes.
8. Como funciona a rotação simples à direita?
É realizada quando a subárvore da esquerda é mais alta que a da direita. A raiz da subárvore da esquerda torna-se a nova raiz, e a antiga raiz move-se para ser o filho direito da nova raiz.
9. Como a árvore AVL mantém a propriedade de ordenação?
Assim como em árvores binárias de busca, a inserção e remoção em árvores AVL são realizadas de forma a manter a propriedade de ordenação, onde todos os nós à esquerda de um nó são menores que ele e todos os nós à direita são maiores.
