Estrutura de dados

Prof.: Hermes Pinheiro
Faculdade Dom Pedro II

1



Árvore AVL (ou árvore balanceada pela altura)
◦ Árvore de busca binária auto-balanceada.
◦ A altura de dois nós folha difere no máximo em uma unidade. ◦ Inserções e eliminações podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações. 

O nome AVL vem das iniciais de seus criadores:
◦ Adelson Velsky e Landis

2



Balanceamento
◦ Uma árvore AVL é dita balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas subárvores (direita e esquerda) não é maior do que um.
◦ Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. ◦ O balanceamento é requerido para as operações de adição e exclusão de elementos.
◦ Todo nó passa a ter um fator de balanceamento

3



Fator de balanceamento
◦ É dado pelo seu peso em relação a sua sub-árvore.
◦ Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator.
◦ Um nó com fator de balanceamento -2 ou 2 é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.

4









Por convenção o Fator de Balanceamento é calculado como segue:
FatBal(n) = Profundidade Direita - Profundidade Esquerda
FatBal(n)=-1 indica que a subárvore à esquerda é mais “alta” que a subárvore à direita;
FatBal(n)=+1 indica que a subárvore à direita é mais “alta” que a subárvore à esquerda;
FatBal(n)=0 indica que as duas subárvores possuem a mesma altura. 0
+1

0

0

-1

0

0

0

+1

0

0

5







Tal como uma árvore Binária de Busca, a inserção em uma AVL sempre se dá em uma folha. Ocasiona aumento da altura da subárvore, podendo ocorrer desbalanceamento.
Responsabilidades do algoritmos de inserção:
◦
◦
◦
◦

Inserção propriamente dita;
Ajuste dos fatores de balanceamento;
Verificação do equilíbrio da árvore;
Execução de Rotações em árvores com equilíbrio