Árvore AVL: Conceitos e Exercícios

Prévia do material em texto

Árvore AVL
⚫ O rebalanceamento da árvore pode ser realizado
localmente se apenas uma porção da árvore foi
afetada por uma inserção ou remoção de um elemento.
⚫ Um algoritmo é o AVL Adel´son-Vel´skii e Landis.
⚫ Uma árvore AVL é uma árvore na qual as alturas das
subárvores esquerda e direita de cada nó diferem no
máximo por um.
Árvore AVL
⚫ Os números nos nós indicam os fatores de
balanceamento, que são as diferença entre as alturas das
subárvores esquerda e direita.
⚫ Na AVL todos os fatores devem ser +1, 0 ou -1
⚫ A árvore AVL não garante que a árvore esteja
perfeitamente balanceada. (Que ela possua a altura
mínima necessária para conter seus nós)
-1
0
+1
0 -1
0
+1
+10
0
0
-1 -1
Árvore AVL
⚫ Análise
⚫ O pior caso em uma árvore AVL é 44% pior 
(exige 44% mais comparações) do que a 
configuração da árvore de melhor caso.
⚫ Estudos mostram que o número médio de 
busca está muito mais perto do melhor caso 
que do pior caso, e é igual a 𝑙𝑔𝑛 + 0,25 para 
𝑛 grande (Knuth)
Árvore AVL
⚫ Inserção
⚫ Inserção da mesma forma da pesquisa
binárias
⚫ Se o fator de balanceamento de
qualquer nó se tornar menor do que -1
ou maior do que 1, a árvore tem que ser
balanceada.
⚫ 4 casos são possíveis sendo que 2 são
simétricos.
Árvore AVL - Inserção (caso 1)
+1
0
h +1
h
h h
+2
+1
h
h
h +1
0
0
h h
h+1
h+2
P
Q
P
Q
P
Q
Inserido 1 
nó no verde
Rotação Simples
Q com P
Árvore AVL - Inserção (caso 2)
+1
0
h
h h
P
Q
+2
-1
h
h
P
Q
h +1
+2
-1
h
h
P
Q
h-1
+1
h
R
+2
0
h
h
P
Q
h-1
+2
h
R
-1 0
h h
P Q
h-1
0
h
R
Inserido 1 
nó no verde
Abrindo o h+1
Rotação Dupla
R com Q
Rotação Dupla
R com P
Árvore AVL - Exercício
1. Crie uma árvore AVL para a entrada 
10, 3, 5, 15, 19, 8, 6, 9, 7
1. Remova os nós 19, 6, 7, 5
Árvore AVL - Exercício
Inserir: 10, 3, 5, 15, 19, 8, 6, 9, 7
Insere 10
Árvore AVL - Exercício
Inserir: 10, 3, 5, 15, 19, 8, 6, 9, 7
10
0
Insere 3
Árvore AVL - Exercício
Inserir: 10, 3, 5, 15, 19, 8, 6, 9, 7
10
-1
3
0
Insere 5
Árvore AVL - Exercício
Inserir: 10, 3, 5, 15, 19, 8, 6, 9, 7
10
-2
3
1
5
0
Rotação Dupla
Fatores: -2 e 1
Rotação 3 e 5
Árvore AVL - Exercício
Inserir: 10, 3, 5, 15, 19, 8, 6, 9, 7
10
5
3
Rotação Dupla
Rotação 5-10
Árvore AVL - Exercício
Inserir: 10, 3, 5, 15, 19, 8, 6, 9, 7
5
0
3
0
10
0Rotação Dupla
Fim da rotação
Insere 15
Árvore AVL - Exercício
Inserir: 10, 3, 5, 15, 19, 8, 6, 9, 7
5
1
3
0
10
1
15
0
Insere 19