Please enable JavaScript.
Coggle requires JavaScript to display documents.
Balanced Search Trees, AVL Trees - Coggle Diagram
Balanced Search Trees
-
Importância
- Evitar Degeneração: Árvores binárias desbalanceadas podem degenerar em listas, aumentando a complexidade de operações como busca, inserção e remoção.
- Manter Eficiência: Garantir que a altura da árvore seja logarítmica em relação ao número de nós melhora significativamente o desempenho das operações.
-
AVL Trees
-
- Inserção: Durante a inserção, após adicionar um nó, é necessário verificar e corrigir o balanceamento ao longo do caminho percorrido. Isso pode envolver rotações simples ou duplas.
- Remoção: Após remover um nó, é essencial reavaliar o balanceamento ao longo do caminho da remoção e realizar rotações, se necessário, para restaurar o equilíbrio.
- Rotações: As rotações (simples ou duplas) são a essência da manutenção do balanceamento em AVL Trees. Elas preservam a ordem de busca enquanto ajustam a altura.
-
- Fator de Balanceamento: O fator de balanceamento é atualizado após cada inserção ou remoção.
- Rotações: Existem quatro tipos de rotações - rotação simples à esquerda, rotação simples à direita, rotação dupla à esquerda e rotação dupla à direita - que são aplicadas com base no fator de balanceamento dos nós.
- Atualizações Recursivas: A verificação e correção do balanceamento geralmente ocorrem de forma recursiva ao longo do caminho percorrido durante inserção ou remoção.
-
- Restrições de Balanceamento: Em uma AVL Tree, para cada nó, o fator de balanceamento deve estar entre -1 e 1.
- Altura Logarítmica: A altura de uma AVL Tree é mantida de forma logarítmica proporcional ao número de nós, garantindo operações eficientes.
- Árvores Binárias de Busca Balanceadas: AVL Trees são uma forma específica de árvores de busca binárias que garantem um balanceamento rigoroso para otimizar operações de busca, inserção e remoção.
cout << endl; // Não tava pulando linha
- Fator de Balanceamento: Cada nó em uma AVL Tree possui um fator de balanceamento, que é a diferença entre as alturas de suas subárvores esquerda e direita. Essa diferença deve ser -1, 0 ou 1 para garantir o balanceamento.