Please enable JavaScript.
Coggle requires JavaScript to display documents.
M9 (Árvores AVL, Árvores de Busca Balanceadas) - Coggle Diagram
M9
Árvores AVL
AVL (Adelson-Velsky e Landis): Primeira estrutura de árvore de busca balanceada, proposta em 1962. Cada nó na árvore possui um fator de balanceamento que é a diferença de altura entre suas subárvores esquerda e direita
Propriedades
Balanceamento: A diferença de altura entre subárvores de qualquer nó (fator de balanceamento) deve ser no máximo 1.
Altura: Garante que a altura da árvore é aproximadamente logarítmica em relação ao número de nós, proporcionando eficiência nas operações.
Operações
Inserção: Após a inserção de um novo nó, a árvore pode precisar ser reequilibrada. O balanceamento é mantido através de rotações (simples e duplas).
-
-
-
-
Exclusão: Similar à inserção, mas pode exigir múltiplas rotações para manter o balanceamento após a remoção de um nó.
Busca: A operação de busca em uma árvore AVL é eficiente devido ao balanceamento, com complexidade O(log n).
Vantagens
Eficiência: Operações de busca, inserção e exclusão são realizadas em tempo logarítmico.
Estrutura Balanceada: Mantém a árvore balanceada automaticamente, evitando degradação para uma lista encadeada.
Desvantagens
Complexidade de Implementação: Mais complexa de implementar devido à necessidade de rotações para manter o balanceamento.
Sobrecarga: O processo de reequilíbrio pode introduzir uma pequena sobrecarga em termos de tempo e processamento, especialmente em casos de inserções ou exclusões frequentes.
-