Please enable JavaScript.
Coggle requires JavaScript to display documents.
AVL - Coggle Diagram
AVL
Inserção em AVL
Insere como numa BST normal
Atualiza altura e FB
Se |FB| > 1 → Rebalancear com rotações
Complexidade: O(log n)
Árvore AVL
Nome vem de Adelson-Velsky e Landis (1962)
Usada em bancos de dados, sistemas de arquivos, IA
Altura O(log n)
Árvore binária de busca auto-balanceada
Fator de Balanceamento
FB = altura(esquerda) - altura(direita)
FB válido ∈ {–1, 0, 1}
Altura
Nó nulo: –1
Nó folha: 0
Nó interno: 1 + máx(altura(esq), altura(dir))
Remoção em AVL
Remove como numa BST
Atualiza altura
Rebalanceia se necessário
Mesmo raciocínio dos casos LL, RR, LR, RL
Pode ocorrer em qualquer ponto do caminho até a raiz
Tipos de Rotações
Simples
LL (R-Rotation / Rotação à direita)
FB > 1 e chave inserida à esquerda do filho esquerdo
RR (L-Rotation / Rotação à esquerda)
FB < –1 e chave inserida à direita do filho direito
Duplas
LR (Left-Right)
FB > 1 e chave inserida à direita do filho esquerdo
RL (Right-Left)
FB < –1 e chave inserida à esquerda do filho direito