Árvores Balanceadas (AVL)
Prof. Alexandre Parra Carneiro da Silva
[email protected]
1
Roteiro

Contextualização

Árvores Balanceadas (AVL)

Operações de Balanceamento
2
Roteiro

Contextualização

Árvores Balanceadas (AVL)

Operações de Balanceamento
3
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
3
5
7
5
6
7
4
Contextualização



Idealmente, deseja-se que a árvore esteja
balanceada, para qualquer nó p da árvore.
Como saber se a árvore está balanceada ?
Para cada nó p da árvore a altura da sua sae é
aproximadamente igual à altura da sua sad.
5
Roteiro

Contextualização

Árvores Balanceadas (AVL)

Operações de Balanceamento
6
Árvores Balanceadas (AVL)



O nome AVL vem de seus criadores Adelson Velsky e Landis
(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.
Operações de consulta, inserção e remoção de nós tem custo
O(log2n).
130
100
80
110
120
120
150
130
100
200
80
110
200
150
7
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 ?


(1/2)
Subtraindo-se as alturas das suas sub-árvores.
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.
8
Como reconhecer uma árvore desbalanceada?


(2/2)
Possíveis valores de diferença para cada nó em uma
árvore balanceada: -1, 0, 1.
Fator de Balanceamento (FB) de cada nó da árvore

FB(p) = h(sad(p)) – h(sae(p))
9
Exemplos de cálculos de FB
+6
Inserção: 1, 2, 3, 4, 5, 6 e 7
1
0 Inserção: 4, 2, 3, 6, 5, 1 e 7
+5
2
4
0
+4
3
+3
4
2
0
+2
5
6
6
0 0
1
+1
0
5
3
0
7
0
7
-1 Inserção: 4, 1, 3, 6, 5, 2 e 7
4
0
+2
1
6
-1
3
0
0
5
7
0
2
10
Operação: Inserção
Inserção: 4, 6, 1, 7, 5, 3 e 2.
-1
0
4
0
+2
1
6
-1
3
0
Op. de balanceamento
0
0
5
7
0
2
0
1
4
0
0 0
3
5
6
0
7
2
11
Operação: Remoção
Inserção: 4, 6, 2 e 7.
+1
4
Remover nó 2
0
+1
2
6
0
+2
0
4
Op. de balanceamento
+1
6
0
6
0
0
4
7
7
7
12
Roteiro

Contextualização

Árvores Balanceadas (AVL)

Operações de Balanceamento
13
Operações de Inserção e Remoção


A inserção ou remoção de um nó em uma árvore AVL
pode ou não provocar seu desbalanceamento.
Se a árvore AVL ficar desbalanceada, a restauração
do seu balanceamento é realizado através de
ROTAÇÕES.
14
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
15
Exemplos 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
6
4
0 Rotação a direita (nó 8) +1
10
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.
16
Exemplo de Rotação Dupla

Suponha que queiramos inserir o nó 5 na árvore abaixo
-2
-1
0
0
2
4
8
0
6
(1/2)
8
0
10
-2
+1
0
0
4
-1
2
6
0
5
(a)
-2
10
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.
17
Exemplo de Rotação Dupla
-2
-2
0
0
2
4
6
8
0
0
(b)
0
10
0
0
(2/2)
2
4
6
0
5
+1
8
0
10
5
Logo após da rotação a esquerda: (b) rotaciona-se o nó 8 (FB = -2) na
direção oposta (direita neste caso).
18
Pseudo-Código: Rotações Simples

Rotação Simples a Esquerda
p aponta para o nó desbalanceado
q = right(p);
hold = left(q);
left(q) = p;
right(p) = hold;
p = q;

10 15 12 7 21 30
+2
10
0
+1
7
15
0
+1
12
21
0
30
Rotação Simples a Direita
p aponta para o nó desbalanceado
q = left(p);
hold = right(q);
right(q) = p;
left(p) = hold;
p = q;
-2
10 15 4 2 1 7
10
-1
0
4
15
-1
2
0
7
0
1
19
Pseudo-Código: Busca e Inserção

Busca e Inserção

Procurar pseudo-código no livro do Tenembaum “Estrutura
de Dados Usando C”. pags: 531, 532, 533 e 534.
20
Conclusões




Balanceamento de árvores busca minimizar o
número médio de comparações necessárias para
localizar qualquer dado.
Operações de inserção e remoção de nós tendem
a tornar as árvores desbalanceadas.
Há um custo extra de processamento.
Compensado quando os dados armazenados
precisam ser recuperados muitas vezes.
21
AVL Tree Applet

http://webpages.ull.es/users/jriera/Docencia/AVL/AVL
%20tree%20applet.htm
22