Please enable JavaScript.
Coggle requires JavaScript to display documents.
M9 Balanced Search Trees - Coggle Diagram
M9
Balanced Search Trees
AVL Trees
Inventadas por Adelson-Velsky e Landis em 1962
Fator de equilíbrio de cada nó é 0, +1 ou -1
Rotações para manter o equilíbrio
rotação simples à direita
rotação simples à esquerda
rotação dupla esquerda-direita
rotação dupla direita-esquerda
Características de eficiência
Altura logarítmica
complexidade logarítmica para busca
inserção
deleção
Desvantagens
Rotações frequentes
necessidade de manutenção de equilíbrio
Características de Eficiência das Árvores AVL
Limites de altura: log2 n ≤ h < 1.4405 log2 (n + 2) − 1.3277
Complexidades de busca e inserção no pior caso: O(log n)
Dificuldade média de altura, mas aproximadamente 1.01log2 n + 0.1
Eficiência da deleção: Logarítmica
Árvores AVL como uma estrutura poderosa com compensações de eficiência
Árvores de Busca Binária (BST)
Desafios com Árvores de Busca Binária Básicas
Eficiência temporal no caso médio e pior
Degeneração da árvore
Abordagens para Superar Desafios
Variedade de Simplificação de Instância
Árvores autoequilibráveis (AVL, rubro-negras)
Rotações para manter o equilíbrio
Variedade de Mudança de Representação
Múltiplos elementos em um nó (árvores 2-3, B-trees)