Árvores
Balanceadas
(AVL)
Prof. Luiz José Hoffmann Filho
[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:
o 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? (1/2)
• Como saber se a árvore está desbalanceada ?
o Verificando se existe algum nodo “desregulado”.
• Como saber se um nodo está desregulado ?
o 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
o 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:
o Rotação a Esquerda
o Rotação a Direita
• Rotação Dupla:
o Rotação a Esquerda
o 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
8
0
6
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 (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
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)
-2
-2
0
0
2
4
6
8
0
0
(b)
0
10
0
0
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
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://www.qmatica.com/DataStructures/Trees/AV
L/AVLTree.html
• http://people.ksp.sk/~kuko/bak/
22
Exercícios
• Insira em uma árvore AVL, itens com as chaves
apresentadas nos itens a seguir (na ordem em que
aparecem). Desenhe a árvore resultante da
inserção, sendo que uma nova árvore deve ser
desenhada quando houver uma rotação. Indique
qual a rotação que foi executada.
a)30, 40, 24, 58, 48, 26, 11, 13, 14
b)20, 15, 25, 10, 30, 24, 17, 12, 5, 3
c) 40, 30, 50, 45, 55, 52
d)20, 15, 25, 12, 17, 24, 30, 10, 14, 13
e) 20, 15, 25, 12, 17, 30, 26
f) 35, 39, 51, 20, 13, 28, 22, 32, 25, 33
23
Exercícios
• Dadas as seguintes chaves M, G, B, H, S, P, F, C
como entrada (nesta ordem), desenhe a
respectiva árvore AVL (balanceando-a quando for
necessário).
24
Exercícios
Nesta questão, você deverá executar duas inserções e duas
remoções na árvore AVL acima, desenhe cada uma das
operações necessárias.
Insira 105
Insira 20
Remova 99
Remova 36
25