Algoritmos e Estrutura de Dados III
Árvore AVL
Contextualização
• As ABP estudadas têm uma séria desvantagem que pode afetar
o tempo necessário para recuperar um item armazenado.
• A desvantagem é que o desempenho da ABP depende da
ordem em que os elementos são inseridos.
1, 2, 3, 4, 5, 6, 7
4, 6, 2, 5, 1, 7, 3
1
4
2
6
2
3
4
1
5
6
7
URI - DECC - Ciência da Computação
3
5
7
Árvores AVL
• Nome com origem em seus inventores:
– Georgii Adelson-Velsky e Yevgeniy Landis;
– Publicaram um documento chamado: "Algoritmos para
organização da informação“, em 1962;
• Uma árvore binária de pesquisa T é denominada AVL
se:
– Para todos nós de T, as alturas de suas duas subárvores diferem no máximo de uma unidade.
• Para cada inserção ou exclusão no pior caso é de O(log
n).
URI - DECC - Ciência da Computação
Como reconhecer uma árvore
desbalanceada?
• Como saber se a árvore está desbalanceada ?
– Verificando se existe algum nodo “desregulado”.
• Como saber se um nodo está desregulado ?
– Subtraindo-se as alturas das suas sub-árvores.
– Fator de Balanceamento
• Por questões de eficiência, estas diferenças são
pré-calculadas
e
armazenadas
nos
nós
correspondentes, sendo atualizadas durante as
operações.
URI - DECC - Ciência da Computação
Fator de Balanceamento
• Fator de Balanceamento de um nó:
– dado pelo seu peso em relação a sua sub-árvore
fb = altura árvore direita – altura árvore esquerda
– O fator de balanceamento de uma folha é sempre 0
– Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator;
–
–
–
Fatbal = -1, quando a sub-árvore da esquerda é um nível mais alto que a direita.
Fatbal = 0, quando as duas sub-árvores tem a mesma altura.
Fatbal = 1, quando a sub-árvore da direita é um nível mais alto que a esquerda.
– Um nó com fator de balanceamento -2 ou 2 é considerada um árvore
não-AVL
•
requer um balanceamento por rotação ou dupla-rotação.
URI - DECC - Ciência da Computação
Propriedade da AVL
• Procurar manter todas as folhas mais ou
menos na mesma altura de forma a
respeitar o FB < 2
• Ou seja,
Para todo nó
| altura(dir) - altura(esq) | < 2
URI - DECC - Ciência da Computação
Relembrando as definições...
• Altura de uma árvore (também denominada profundidade) é a
distância entre x e o seu descendente mais afastado. Mais
precisamente, a altura de x é o número de passos do mais longo
caminho que leva de x até uma folha somando um.
– Por definição a altura de uma árvore vazia é -1
E
/
\
D
I
/
Altura de I é 2
/
B
\
G
/ \
A
Altura dessa árvore é 3
/
C
F
K
\
H
Altura de K é 1
/
J
Altura de J é 0
URI - DECC - Ciência da Computação
Exemplos de cálculos de FB
0
+6
4
Inserção: 1, 2, 3, 4, 5, 6 e 7
1
+5
2
+4
3
+3
4
1
+2
5
Inserção: 4, 2, 3, 6, 5, 1 e 7
0
0
2
6
0
0
0
0
3
5
7
+1
6
0
-1 Inserção: 4, 1, 3, 6, 5, 2 e 7
7
4
0
+2
6
1
-1
3
0
0
5
0
2
URI - DECC - Ciência da Computação
7
Operação: Inserção
Inserção: 4, 6, 1, 7, 5, 3 e 2.
-1
0
4
+2
3
0
1
2
6
-1
3
0
Op. de balanceamento
1
0
0
1
5
7
0
0
0
2
0
1
2
0
Altura
Fb
URI - DECC - Ciência da Computação
4
0
0 0
3
5
6
0
7
Operação: Remoção
Inserção: 4, 6, 2 e 7.
+1
4
Remover nó 2
0
+1
2
6
2
0
1
0
7
4
+2
Op. de balanceamento
6
6
+1
0
4
7
0
0
0
Altura
Fb
URI - DECC - Ciência da Computação
7
0
Operações
– Adição e exclusão requerem que a árvore
esteja balanceada, se a árvore não estiver
balanceada é necessário seu balanceamento
• através da rotação ou dupla-rotação.
URI - DECC - Ciência da Computação
Rotação
• A operação básica em uma árvore AVL geralmente
envolve os mesmos algoritmos de uma árvore de busca
binária desbalanceada.
• A rotação na árvore AVL ocorre devido ao seu
desbalanceamento
– uma rotação simples ocorre quando um nó está
desbalanceado e seu filho estiver no mesmo sentido da
inclinação.
– Uma rotação-dupla ocorre quando um nó estiver
desbalanceado e seu filho estiver inclinado no sentido inverso
ao pai
URI - DECC - Ciência da Computação
Tipos de Rotações
• Rotação Simples:
– Rotação a Esquerda
– Rotação a Direita
• Rotação Dupla:
– Rotação a Esquerda
– Rotação a Direita
URI - DECC - Ciência da Computação
Dicas
a) Para identificar quando uma rotação é simples
ou dupla deve-se observar os sinais dos FBs do
nodo desbalanceado e do filho que gerou o
desbalanceamento:
• Sinal for igual, a rotação é simples
• Sinal for diferente a rotação é dupla
b) Se Fb for positivo (+) a rotação para à esquerda
c) Se Fb for negativa (-) a rotação para à direita
URI - DECC - Ciência da Computação
Rotação Simples à Direita
Inserção à esquerda de árvore
desbalanceada à esquerda (bal = -1)
Promover o elemento do meio através
de um giro no sentido horário.
URI - DECC - Ciência da Computação
Rotação Simples à Esquerda
Inserção à direita de árvore
desbalanceada à direita (bal = +1)
Promover o elemento do meio através
de um giro no sentido anti-horário.
URI - DECC - Ciência da Computação
Exemplo de Rotação Simples
• Suponha que nós queiramos inserir o nó 3 na árvore inicial
abaixo
-1
0
0
4
2
8
0
6
3
-2
0
10
8
-1
+1
2
0
4
0
0
4
0 Rotação a direita (nó 8) +1
10
6
2
0
0 0
3
6
8
0
10
3
A inserção do nó 3 produziu um desbalanço no nó 8 verificado pelo FB = -2 neste nó.
Neste caso, como os sinais dos FB são os mesmos (nó 8 com FB = -2 e nó 4 com
FB = -1) significa que precisamos fazer apenas uma ROTAÇÃO SIMPLES.
URI - DECC - Ciência da Computação
Rotação Dupla à Esquerda
- Inserção do elemento 20
(rotação simples à direita + rotação simples à esquerda)
URI - DECC - Ciência da Computação
Rotação Dupla à Direita
- Inserção do elemento 20
(rotação simples à esquerda + rotação simples à direita)
URI - DECC - Ciência da Computação
Exemplo de Rotação Dupla (1/2)
• Suponha que queiramos inserir o nó 5 na árvore abaixo
-2
-1
0
0
2
4
8
0
6
8
0
10
-2
+1
0
0
4
-1
2
(a)
-2
10
6
0
5
0
0
2
4
6
8
0
10
0
5
Observe que o nó 8 tem FB = -2 e tem um filho com FB = +1 (sinais opostos).
Neste caso, o balanceamento é alcançado com duas rotações. Primeiro: (a)
rotação simples sobre o nó 4 (com FB = +1) para a esquerda.
URI - DECC - Ciência da Computação
Exemplo de Rotação Dupla (2/2)
-2
-2
0
0
2
4
6
8
0
(b)
6
0
4
0
8
0
5
0
10
2
+1
10
0
0
5
Logo após da rotação a esquerda: (b) rotaciona-se o nó 8 (FB = -2) na
direção oposta (direita neste caso).
URI - DECC - Ciência da Computação
Caso I: Rotação Simples
• Suponha que inserimos os números 50, 40 e 30 em uma
árvore. Obteremos então:
•
A inserção novamente produziu um desbalanceamento.
•
Neste caso, como os sinais dos FB são os mesmos, significa que precisamos fazer apenas
uma ROTAÇÃO SIMPLES à direita no nodo com FB -2.
•
No caso simétrico (nodo com FB 2) faríamos uma rotação simples à esquerda.
URI - DECC - Ciência da Computação
Caso I: Rotação Simples
•
Após a rotação simples teremos:
• A árvore está balanceada dentro das propriedades de AVL.
URI - DECC - Ciência da Computação
Exemplo:
• Considerando a árvore abaixo:
•
•
A árvore está balanceada, como podemos observar pelos Fb de cada nodo.
São dois os possíveis casos de desbalancemento
URI - DECC - Ciência da Computação
Caso II: Rotação Dupla
• Ao inserir o número 5 na árvore teremos a seguinte
árvore:
•
•
O nodo 8 fica com o FB -2 e tem um filho com FB +1. Neste caso para manter o
balanceamento devemos aplicar duas rotações, também denominada ROTAÇÃO DUPLA.
Primeiro rotaciona-se o nodo com FB 1 para a esquerda.
URI - DECC - Ciência da Computação
Caso II: Rotação Dupla
• Logo rotaciona-se o nodo que possuía FB -2 na direção
oposta, nesse caso a direita.
URI - DECC - Ciência da Computação
Caso II: Rotação Dupla
•
Os FB dos nodos voltaram a ficar dentro do esperado das árvores AVL.
•
O caso simétrico ao explicado acima acontece com os sinais de FB
trocados, ou seja, um nodo com FB +2 com um filho com FB -1. Também
utilizariamos uma rotação dupla, mas nos sentidos contrários, ou seja, o
nodo com FB -1 seria rotacionado para a direita e o nodo com FB +2 seria
rotacionado para a esquerda.
URI - DECC - Ciência da Computação
• A descrição do algoritmo em pseudo-código para
a construção de uma árvore AVL seria:
– Inserir o novo nodo normalmente
– Iniciando com o nodo pai do nodo recém-inserido, testar se a propriedade
AVL é violada no novo nodo. Temos aqui 2 possibilidades:
– A condição AVL foi violada
• Execute as operações de rotação conforme for o caso (Caso I ou Caso
II).
• Volte ao passo de Inserção.
– A condição AVL não foi violada.
– Se o nodo recém-testado não tem pai, ou seja, é o nodo raiz da árvore,
volte para inserir novo nodo.
URI - DECC - Ciência da Computação