Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores AVL, Rotações, balance = altura subárvore esquerda - altura…
Árvores AVL
COMPLEXIDADE
Busca: O(log n)
Inserção: O(log n)
Remoção: O(log n)
Custo extra: atualizações de altura + rotações
Rotações
L-Rotation (esquerda simples)
• Quando: balance < -1 e k ≥ dir->key
• Caso: inserção à direita do filho direito
R-Rotation (direita simples)
• Quando: balance > 1 e k < esq->key
• Caso: inserção à esquerda do filho esquerdo
LR-Rotation (esq-dir dupla)
• Quando: balance > 1 e k ≥ esq->key
• Caso: inserção à direita do filho esquerdo
→ esq = leftRotate(esq)
RL-Rotation (dir-esq dupla)
• Quando: balance < -1 e k < dir->key
• Caso: inserção à esquerda do filho direito
→ dir = rightRotate(dir)
balance = altura subárvore esquerda - altura subárvore direita
DEFINIÇÕES
AVL = Adelson-Velsky e Landis
Primeira árvore binária de busca auto-balanceada
Balanceamento garantido por fator de equilíbrio
valores permitidos: -1, 0, 1