Aula sobre Árvore AVL
Introdução
- Árvore AVL é uma árvore binária de busca balanceada.
- Segue as mesmas regras de inserção, busca e remoção das árvores binárias comuns.
- Mantém o equilíbrio através de rotações.
- Criada por Adelson-Velsky e Landis.
Importância do Equilíbrio
- Operações básicas (busca, inserção, remoção) têm tempo proporcional ao número de níveis da árvore.
- Desequilíbrios aumentam o tempo das operações.
- Exemplo: Inserção sequencial de 1 a 9 resulta em árvore desequilibrada.
Detecção de Desequilíbrio
- Medido pela diferença de níveis entre subárvores esquerda e direita.
- Se a subtração for maior que 1 ou menor que -1, há desequilíbrio.
- Tolerância para fatores de equilíbrio entre -1 e 1.
Correção de Desequilíbrio
- Utiliza rotações para corrigir o desequilíbrio.
- Quatro tipos de rotações:
- Rotação à Esquerda
- Mover nós da subárvore direita para a esquerda.
- Novo nó raiz vira o antigo filho da direita.
- Rotação à Direita
- Mover nós da subárvore esquerda para a direita.
- Novo nó raiz vira o antigo filho da esquerda.
- Rotação Dupla à Esquerda
- Combina rotação à direita e depois à esquerda.
- Usada quando rotação simples à esquerda não resolve.
- Rotação Dupla à Direita
- Combina rotação à esquerda e depois à direita.
- Usada quando rotação simples à direita não resolve.
Decidindo a Rotação
- Calcular o fator de equilíbrio (Q = R - L, R: níveis à direita, L: níveis à esquerda).
- Verificar o intervalo:
- Se Q está entre -1 e 1, a árvore está equilibrada.
- Se Q > 1:
- Se subárvore direita tem Q < 0, realizar rotação dupla à esquerda.
- Caso contrário, realizar rotação simples à esquerda.
- Se Q < -1:
- Se subárvore esquerda tem Q > 0, realizar rotação dupla à direita.
- Caso contrário, realizar rotação simples à direita.
Conclusão
- Árvore AVL mantém o equilíbrio com rotações adequadas.
- Importante para eficiência de operações básicas.
Próxima Aula: Técnicas avançadas de balanceamento em árvores AVL.