Algoritmos e Estruturas

de Dados II
Árvores - AVL

Prof. Raimundo BARRETO

DCC/ICE/UFAM
Introdução

Árvore Balanceada
• Uma árvore binária balanceada é aquela em que, para
qualquer nó, suas sub-árvores esquerda e direita têm a
mesma altura.

Árvore AVL
• Uma árvore binária de busca é considerada balanceada
quando, para cada nó, as alturas de suas sub-árvores
esquerda e direita diferem de, no máximo, 1.
• Essa diferença é chamada fator de balanceamento, ou
FB(n).
Introdução

Seja um nó n qualquer da árvore:

•FB(n) = altura(sad) – altura(sae).
• se FB(n) = 0, as duas sub-árvores têm a mesma
altura;
• se FB(n) = -1, a sub-árvore esquerda é mais
alta que a direita em 1;
• se FB(n) = +1, a sub-árvore direita é mais alta
que a esquerda em 1.
Introdução - Exemplo 1

Montar uma ABB, inserindo, sucessivamente, os

valores seguintes, na ordem dada, e determinar o
fator de balanceamento de cada nó: 30, 20, 40,
10, 35, 25, 22 e 50.
Introdução

Exemplos de Árvores AVL

Introdução

Exemplos de Árvores Não-AVL

Introdução

A vantagem de uma árvore AVL sobre uma degenerada
está na maior eficiência nas suas operações de busca,
pois, sendo a altura da AVL bem menor, o número
necessário de comparações diminui sensivelmente.

Por exemplo, numa árvore degenerada de 10.000 nós,
são necessárias, em média, 5.000 comparações, numa
busca; numa árvore AVL, com o mesmo número de nós,
essa média baixa para 14.

A solução é adotar um algoritmo que, a cada inserção,
faça as correções necessárias para manter sempre a
árvore como uma árvore AVL, ou seja, onde qualquer nó
n tenha |FB(n)| <= 1.
Balanceamento

Como fazemos então para manter uma árvore AVL
balanceada?
• Inicialmente inserimos um novo nodo na árvore
normalmente.
• A inserção deste novo nodo pode ou não violar a propriedade
de balanceamento.
• Caso a inserção do novo nodo não viole a propriedade de
balanceamento podemos então continuar inserindo novos
nodos.
• Caso contrário precisamos nos preocupar em restaurar o
balanço da árvore.
• A restauração deste balanço é efetuada através do que
denominamos ROTAÇÕES na árvore.
Balanceamento

Serão usados dois ponteiros A e B, para auxiliar:
• A é nó ancestral mais próximo do nó inserido com
FB(nó) ≠ 0 antes da inserção, ou a própria raiz se
não há nenhum nó com FB(nó) ≠ 0 (antes da
inserção) no caminho da busca.
• A é também chamado de Pivô;
• B é filho de A na sub-árvore onde ocorreu a
inserção.
Exemplo de Desbalanceamento

Antes da Inserção Após a Inserção

do valor 2 do valor 2
(-1) (-2)
10 10 A

(0) (-1)
5 5 B

(0)
2 novo nó inserido

Quem é A e quem é B?
Inserção Balanceada

Há 4 casos para serem analisados.

Solução rotação simples:
• Inserção na sub-árvore esquerda do filho esquerdo de A
• Inserção na sub-árvore direita do filho direito de A

Solução rotação dupla:
• Inserção na sub-árvore esquerda do filho direito de A
• Inserção na sub-árvore direita do filho esquerdo de A
Rotação Simples

proc rotação simples

se FB(A) = +1 // antes da inserção
então rotação simples à esquerda
senão rotação simples à direita
fim se
zera fatores de A e de B
fim proc
Rotação Simples à Esquerda
A->dir = B->esq;
B->esq = A;

A A
(+2) B
10 10
B 20
B A
(+1)
20
20 10 30
30 (0)
30
 Rotação Simples à Direita
A->esq = B->dir;
B->dir = A;

A A
(-2) B
10 10
5
B A
(-1)
B
5 10
5 2
(0)
2 2
Inserção - Exercício

Mostrar as rotações necessárias para a construção

da seguinte árvore AVL: 3, 2, 1, 4, 5, 6 e 7

A
3 (-2)

B
2 (-1)

1 (0)

Quem é A? Quem é B? Quais os FB’s?

O que é necessário fazer para equilibrar essa árvore?
Inserção - Exercício
O resultado da rotação à direita fica...

1 3

Após a inserção de 4 e 5 fica...

2

1 3

O que tem que ser feito 4

para re-equilibrar?
5
Inserção - Exercício
O resultado da rotação à esquerda fica...

1 4

3 5
A
2
Mas quando o 6 é inserido o resultado fica...
B
1 4

O que tem que ser feito 3 5

para re-equilibrar?
6
Inserção - Exercício
A->dir = B->esq;
2
4

1 3 5

B->esq = A;
6
4

2 5

1 3 6
Inserção - Exercício
4

2 5

1 3 6

Mas quando o 7 é inserido o resultado fica... 4

2 5

O que tem que ser feito 1 3 6

para re-equilibrar?
7
Inserção - Exercício
O resultado da rotação à esquerda fica...

2 6

1 3 5 7
Rotação Dupla

proc rotação dupla

se FB(A) = +1 // antes da inserção
então rotação dupla à direita
senão rotação dupla à esquerda
fim se
ajusta fatores dos nós envolvidos na rotação
fim proc
Rotação Dupla à Esquerda

É composta por uma rotação simples á esquerda

(B e Aux) seguida de uma rotação simples à
direita (A e Aux)

Aux é o filho direito de B.
Rotação Dupla à Esquerda
Aux = B->dir;
// rotação simples à esquerda (B – Aux)
B->dir = Aux->esq;
Aux->esq = B;
// rotação simples à direita (A – Aux)
A->esq = Aux->dir;
Aux->dir = A;

A A Aux
20
20 15
B
Aux A
10 15 B 10 20
Aux B
15 10
Rotação Dupla à Direita

É composta por uma rotação simples à direita (B

e Aux) seguida de uma rotação simples à
esquerda (A e Aux)

Aux é o filho esquerdo de B.
Rotação Dupla à Direita
Aux = B->esq;
// rotação simples à direita (B – Aux)
B->esq = Aux->dir;
Aux->dir = B;
// rotação simples à esquerda (A – Aux)
A->dir = Aux->esq;
Aux->esq = A;

A
20 A 20
Aux
B Aux
25 25
30 A
B B
30 20 30
Aux 25
Rotação Dupla - Exemplo

2 6

1 3 5 7

Como ficaria se fosse inserido o valor 16?

Rotação Dupla - Exemplo

2 6

1 3 5 7

16

A Árvore ainda fica OK!

Como ficaria se fosse inserido o valor 15?

Rotação Dupla - Exemplo

2 6
Aux
1 5 A 15
3 7 7

B 16 15 7 16

15 Aux 16

Desequilíbrio no nó 7. Rotação dupla à direita.

Rotação Dupla - Exemplo

2 6

1 3 5 15

7 16

Agora a árvore está OK!

E se inseríssemos o 14?
Rotação Dupla - Exemplo

4 B->esq = Aux->dir;
A
Aux->dir = B;
2 6
B
7
1 3 5 15

Aux 7 15
16

14 16
14

Desequilíbrio no nó 6. Rotação dupla à direita

Primeira fase: Rotação simples à direita (B – Aux)
Rotação Dupla - Exemplo

4
A->dir = Aux->esq;
A Aux->esq = A;
2 6

Aux 7 Aux
1 3 5 7

B 6 15
15

5 14 16
14 16

Segunda fase: Rotação simples à esquerda (A – Aux)

Rotação Dupla - Exemplo

2 7

1 3 6 15

5 14 16

Agora a árvore está OK!

Remoção

Inicialmente, faz-se a retirada do nó, usando o algoritmo
de busca e retirada de uma ABB.

Se não desbalanceou, o processo está encerrado.

Se desbalanceou a árvore, isto é, se um ou mais nós ficou
com |FB(nó)|>1, raciocina-se em termos de inserção,
perguntando:
• se o desbalanceamento ocorresse devido a uma inserção, que nó
teria sido inserido para causar tal desequilíbrio?

Identificado o nó, simula-se sua inserção e faz-se a
rotação necessária.
Remoção

Retirando o 5 resulta uma árvore desbalanceada no nó 10.

Que nó inserido teria causado esse desequilíbrio? o 30.
Uma rotação simples à esquerda resolve o problema.
Remoção
Retirando o 12 desbalanceia a raiz.
Podemos supondo que a inserção recente foi o 8.
Uma rotação dupla à esquerda corrige o problema.
Remoção
A retirada da folha 2 desbalanceia a raiz 6.
Essa configuração jamais pode vir de uma seqüência de inserções, pois,
se ela fosse 8, 12 ou 12, 8, a primeira dessas inclusões já provocaria rotação.

Solução: escolhe-se arbitrariamente um desses dois nós, despreza-se

o outro (mantendo-o na árvore, obviamente), e simula-se a sua inserção.
Escolhemos o 12, que exige uma operação mais simples:
rotação simples à esquerda.
 Remoção
Infelizmente, há situações mais complexas, onde o próprio processo de
balanceamento devido a retirada de um nó de uma subárvore, pode
provocar um novo desequilíbrio na árvore.
A solução será reaplicar o método para a árvore que desbalanceou. E novo
desequilíbrio pode ser provocado mais acima, exigindo novo balanceamento.
E assim por diante, até que toda a árvore volte a ser uma AVL.
Remoção
Isso causará o desequilíbrio da subárvore cuja raiz é 70; aplicando nosso
método para esta subárvore apenas, simulamos o ingresso do 90, fazendo
uma rotação simples à esquerda entre 70 e 80, o que resulta na árvore
abaixo:

Esta árvore é AVL?

Remoção
A árvore não é AVL, pois |FB(60)|>1. Temos que reaplicar o
método para o 60. Considerando que, neste caso, tanto faz escolhermos
o 42, o 52 ou o 56 para ser o nó de inserção simulada, a rotação exigida é a
dupla à esquerda (60-40), o resultado é a árvore abaixo que, finalmente,
é uma AVL:
Remoção

Isso mostra porque a remoção é mais complicada

que a inserção. Enquanto nesta operação, no máximo
uma rotação (simples ou dupla) servirá para manter a
árvore balanceada, na remoção de um único nó, mais
de uma rotação poderá ser necessária.