Embed Size (px)
Citation preview
1
Árvores Balanceadas (AVL)
2
Roteiro
Contextualização
Árvores Balanceadas (AVL)
Operações de Balanceamento
3
Roteiro
Contextualização
Árvores Balanceadas (AVL)
Operações de Balanceamento
4
Contextualização
As ABP estudadas têm uma séria desvantagem que podeafetar o tempo necessário para recuperar um itemarmazenado.
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
2
3
4
5
6
7
2
4
6
1 3 5 7
5
Contextualização
Idealmente, deseja-se que a árvore estejabalanceada, 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.
6
Roteiro
Contextualização
Árvores Balanceadas (AVL)
Operações de Balanceamento
7
Á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-árvoresdiferem no máximo de uma unidade.
Operações de consulta, inserção e remoção de nós tem custoO(log2n).
130
100 150
120 20080
110
120
100
11080
130
200
150
8
Como reconhecer uma árvore desbalanceada? (1/2)
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.
Por questões de eficiência, estas diferenças sãopré-calculadas e armazenadas nos nóscorrespondentes, sendo atualizadas durante asoperações.
9
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))
10
Exemplos de cálculos de FB
1
2
3
4
5
6
7
+6
+5
+4
+3
+2
+1
0
Inserção: 1, 2, 3, 4, 5, 6 e 7
2
4
6
1 3 5 7
0 0
0
0 0
00
Inserção: 4, 2, 3, 6, 5, 1 e 7
4
1 6
3
2
5 7
-1
0
00
+2
-1
0
Inserção: 4, 1, 3, 6, 5, 2 e 7
11
Operação: Inserção
2
4
6
1 3 5 7
0 0
0
0 0
00
Op. de balanceamento
4
1 6
3
2
5 7
0
00
+2
-1
0
Inserção: 4, 6, 1, 7, 5, 3 e 2.-1
12
Operação: Remoção
4
6
7
+2
0
+1Remover nó 2
4
6
7
0
0
0
Op. de balanceamento4
2 6
7
+1
0
+10
Inserção: 4, 6, 2 e 7.
13
Roteiro
Contextualização
Árvores Balanceadas (AVL)
Operações de Balanceamento
14
Operações de Inserção e Remoção
A inserção ou remoção de um nó em uma árvore AVLpode ou não provocar seu desbalanceamento.
Se a árvore AVL ficar desbalanceada, a restauraçãodo seu balanceamento é realizado através deROTAÇÕES.
15
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
Dicas:
a) Para identificar quando uma rotação é simplesou dupla deve-se observar os sinais do Fb:
• 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
Rotação:
17
Exemplos de Rotação Simples
Suponha que nós queiramos inserir o nó 3 na árvore inicial abaixo
3
08
4 10
2 6
0
0 0
-18
4 10
2 6
3
-1 0
+1 0
-2
0
Rotação a direita (nó 8)
0
0
0 0
4
2 8
1063
+1 0
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.
18
Exemplo de Rotação Dupla (1/2)
Suponha que queiramos inserir o nó 5 na árvore abaixo
08
4 10
2 6
0
0 0
-1
0
8
4 10
2 6
5
0
0
-1
+1
-2
(a)8
6 10
4
52
0
0
0
0-2
-2
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.
19
Exemplo de Rotação Dupla (2/2)
8
6 10
4
52
0
0
0
0-2
-2
Logo após da rotação a esquerda: (b) rotaciona-se o nó 8 (FB = -2) na direção oposta (direita neste caso).
(b)6
4 8
2 105
0
0
0
00
+1
20
Pseudo-Código: Rotações Simples
Rotação Simples a Esquerdap aponta para o nó desbalanceado
q = right(p);
hold = left(q);
left(q) = p;
right(p) = hold;
p = q;
Rotação Simples a Direitap aponta para o nó desbalanceado
q = left(p);
hold = right(q);
right(q) = p;
left(p) = hold;p = q;
10
12
157
30
21
+2
0
+10
+10
10 15 12 7 21 30
2
10
1
154
7
0
0
0
-1
-1
-210 15 4 2 1 7
21
Conclusões
Balanceamento de árvores busca minimizar onúmero médio de comparações necessárias paralocalizar qualquer dado.
Operações de inserção e remoção de nós tendema tornar as árvores desbalanceadas.
Há um custo extra de processamento.
Compensado quando os dados armazenadosprecisam ser recuperados muitas vezes.
22
AVL Tree Applet
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
Árvore Splay
É uma árvore binária de pesquisa (BST)
É uma árvore auto-equilibrada.
Em qualquer operação (pesquisa, inserção, remoção) a árvore faz SPLAY.
Basicamente fazer SPLAY, é trazer um elemento x para a raiz da árvore (BTT- Bring To Top), utilizando sucessivas rotações e tantas quanto necessárias, chamadas ZIG, ZIGZIG e ZIGZAG.
Árvore Splay
Lema: “Tornar mais acessível o que é mais usado”
Ajusta a estrutura da árvore à freqüência de acesso aos dados
Junto à raiz estão os elementos
mais usados
mais recentes
Os mais inativos ficam mais “longe” da raiz
Cada vez que um elemento é pesquisado o nó respectivo é puxado para a raiz usando rotações duplas AVL
Exemplo de Uso
Consultas bancárias
Ao fazer uma consulta, o registro de um cliente será levado para o topo da árvore, diminuindo o tempo de acesso para as próximas consultas. Assim, clientes que fazem consultas freqüentemente terão acesso mais rápido. Os registros de clientes que não utilizam estes serviços, por sua vez, ficarão nos níveis mais inferiores da árvore.
Árvore Splay: zig e zag
Árvore Splay: zig-zig
Árvore Splay: zig-zag
Algoritmo de Pesquisa(x, A)
Início
Faz percurso BST até encontrar.
Se existe o elemento x na árvore A
Faz SPLAY do elemento x
Senão
Faz SPLAY do sucessor esquerdo mais próximo de x
FimExemplo de pesquisa(9, A):
1) Pesquisa tipo BST até encontrar, existe então, faz SPLAY do x (neste caso 9).Caso não existisse faria SPLAY do 8, que é o elemento menor mais próximo de 9.2) Neste caso para fazer SPLAY é utilizado o ZIGZAG(x).3) Árvore final com o x na raiz.
Algoritmo de Inserção(A, x)
Início
Faz SPLAY do elemento x .
Como não existe, o elemento menor mais próximo de x fica na raiz
Agora é só inserir x, que passa a ser a raiz da árvore
FimExemplo de inserção(8, A):
1) SPLAY(8)
2) 7 vai para a raiz
3) Inserir 8, 7 é o seu filho esquerdo,e 10 o seu filho direito.
Algoritmo de Remoção(A, x)
InícioSe existe o elemento x na árvore A.
Faz SPLAY do elemento x.Faz SPLAY do elemento x, na sua subárvore esquerda.Traz o elemento menor mais próximo de x para a raiz.Remove o x.
SenãoFaz SPLAY do elemento menor mais próximo de x.
Fim
Exemplo de remoção(12, A):
1) Pesquisa tipo BST
2) SPLAY (12,A)
3) SPLAY (12,A') onde A' é a subárvore esquerda do 12, assim temos a certeza que o 12 não vai ter filho esquerdo.
4) Elemento menor mais próximo de 12 na raiz e sem filho esquerdo podemos então remover.
5) Elimina-se o 12 e liga-se o pai de x (12) com seu filho direito (15)
Conclusão
Árvores Splay podem ficar desequilibradas mas garantem uma complexidade O(log n) ao longo do
tempo de utilização (complexidade amortizada)
Ajusta a árvore à freqüência de acesso aos dados Junto à raiz estão os elementos
mais usados mais recentes os mais inativos ficam mais longe da raiz
Referências
Bibliografia:Drozdek, Adam. Estrutura de Dados e Algoritmos em C++ (Árvores Auto-
Ajustadas)
Sites:http://www.cs.nyu.edu/algvis/java/SplayTree.htmlhttp://w3.ualg.pt/~hshah/ped/Aula%2011/A11/aula11.htmlhttp://inf.unisinos.br/~ari/estrut/splay.pdfhttp://dct.ual.pt/historial/2004_05/aed2/teoricas/Semana6.pdf
Demonstrações:http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20app
let.htm
http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/SplayTree-Example.html
