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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
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.
