14_Arvore Splay

Prévia do material em texto

1
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Árvore Splay
Estrutura de Dados e 
Algoritmos
J. ACM 32, 3 (Jul. 1985), 652-686
http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
2
2
Árvore Splay
3
� É uma árvore binária de busca auto-ajustável.
� Todas as operações fazem splay
� Elemento acessado vai para a raiz
� Toda operação coloca o elemento envolvido na 
operação no topo da árvore através de rotações
� Objetivo:
� Melhorar a performance das operações, mantendo os 
nós mais acessados na parte superior da árvore
� Boa Performance: a árvore altera seu balanceamento
� Fácil de implementar
� Não tem regras explícitas para preservar a altura
Árvore Splay
4
� Overhead do splay.
� Requer mais ajustes locais. Algumas estruturas requerem
ajustes apenas na alteração e não na busca
� Operações individuais dentro de uma sequência podem
ser caras, o que pode representar uma desvantagem em
aplicações de tempo real.
3
Exemplo
5
� Pesquisar pelo nó com chave 1
� O elemento acessado vai para a raiz
2 8
6
7 9
8
6
7 9
2
1
1
Árvore Splay
6
� Mesmas rotações da árvore AVL
� Objetivo: é trazer um elemento para a raiz da árvore, 
utilizando sucessivas rotações 
� Rotação Simples (ZIG)
� Zig Direita ou Esquerda (quando nó é filho da raiz)
� Dupla Rotação (ZIG_ZIG/ZIG_ZAG)
� ZIG_ZIG Direita
� ZIG_ZIG Esquerda
� ZIG_ZAG (ZIG Esquerda e ZAG Direita) 
� ZIG_ZAG (ZIG Direita e ZAG Esquerda)
� Operações básicas
� Inserção, Remoção, Busca e Splay
4
Rotações Simples
7
ZIG_RIGHT
ZIG_LEFT
Caso 1 (terminal): se pai(x) é raiz fazemos apenas uma
rotação
Rotações Duplas (ZIG_ZIG)
8
ZIG_ZIG_RIGHT
ZIG_ZIG_LEFT
Caso 2: se pai(x) não é raiz e x e pai(x) são filhos do 
mesmo lado, fazemos duas rotações no mesmo
sentido começando pelo avô (pai(pai(x)))
5
Rotações Duplas (ZIG_ZIG)
9
Caso 2: se pai(x) não é raiz e x e pai(x) são filhos do 
mesmo lado, fazemos duas rotações no mesmo
sentido começando pelo avô (pai(pai(x)))
x sobe dois níveis na mesma direção
É como se x invertesse
de lugar com o avô ZIG_ZIG_RIGHT
ZIG_ZIG_LEFT
Rotações Duplas (ZIG_ZAG)
10
ZIG_ZAG
Caso 3: se pai(x) não é raiz e x e pai(x) são filhos do 
lado oposto, faz uma rotação em pai(x) e outra
rotação de sentido oposto no avô.
6
Rotações Duplas (ZIG_ZAG)
11
Caso 3: se pai(x) não é raiz e x e pai(x) sao filhos do 
lado oposto, faz uma rotação em p(x) e outra
rotação de sentido oposto no avô.
x sobe dois níveis em direções diferentes (ZIG_ZAG)
ZIG_ZAG
Árvore Splay
12
� Qual é a ordem de complexidade das operações de 
Splay: zig, zig_zig e zig_zag?
7
Árvore Splay
13
� Qual é a ordem de complexidade das operações de 
Splay: zig, zig_zig e zig_zag?
� O(1)
Árvore Splay (exemplo)
14
Zig-Zag
1º Passo – Zig do pai 
de 14
8
Árvore Splay (exemplo)
15
Zig-Zag
2º Passo – Zag do 
(antigo) avô de 14 
Árvore Splay (exemplo)
16
Zig-Zag
Resultado
9
Árvore Splay (exemplo)
17
Zig-Zig
1º Passo – Zig do 
avô de 14
Árvore Splay (exemplo)
18
Zig-Zig
2º Passo – Zig do 
pai de 14
10
Árvore Splay (exemplo)
19
Zig-Zig
Resultado
Árvore Splay (exemplo)
20
Zig-Zig
1º Passo – Zig do 
avô de 14
11
Árvore Splay (exemplo)
21
Zig-Zig
2º Passo – Zig do 
pai de 14
Árvore Splay (exemplo)
22
Zig-Zig
Resultado Final
12
Árvore Splay
23
� Questões de implementação
� Como fica a implementação de uma árvore splay?
Árvore Splay
24
� Questões de implementação
� Como fica a implementação de uma árvore splay?
class SplayTree<T> {
BSTNode<T> root;
}
class BSTNode<T> {
V data;
BSTNode<T> left;
BSTNode<T> right;
BSTNode<T> parent;
}
Precisamos de algum outro dado?
13
Árvore Splay
25
� Questões de implementação
� Como fica a implementação de uma árvore splay?
Podemos reusar alguma implementação anterior?
class SplayTree<T> {
BSTNode<T> root;
}
class BSTNode<T> {
V data;
BSTNode<T> left;
BSTNode<T> right;
BSTNode<T> parent;
}
Precisamos de algum outro dado?
Árvore Splay (Operações)
26
� Pesquisar
� É realizada uma pesquisa binária até que seja 
encontrado o nó pesquisado
� Se achar: splay nó
� Se não achar: splay do último nó acessado na busca. 
14
Exemplo
27
� Pesquise o nó 1
� Pesquisa com sucesso
zig_zig
2 8
6
7 9
8
6
7 9
2
1
1
Exemplo
28
� Pesquise o nó 4
� Pesquisa sem sucesso 
8
6
9
zig
2
2
6
8
9
15
Exemplo
29
� Pesquise o nó 3
zig_zig, zig
2
8
6
7 9
4
3
4 8
6
7 9
2
3
Árvore Splay (Operações)
30
� Pesquisar
� Como seria o algoritmo de uma pesquisa em uma árvore 
splay?
16
Árvore Splay (Operações)
31
� Pesquisar
� Como seria o algoritmo de uma pesquisa em uma árvore 
splay?
SPLAY-SEARCH(key)
Node x = TREE-SEARCH(key)
if (!x.isEmpty())
splay(x)
else
splay(x.parent)
Árvore Splay (Operações)
32
� Inserção
� Um nó n é inserido da mesma forma que em uma árvore 
de pesquisa binária 
� TREE-INSERT(n)
� Depois faz-se o splay do nó n
17
Exemplo
33
� Insira o nó 1
2 8
6
7 9
8
6
7 9
zig_zig
2
1
Exemplo
34
� Insira o nó 4 
8
6
9
zig_zag
2
2
4
6
8
9
18
Exemplo
35
� Insira o nó 3
zig_zig, zig
4 8
6
7 9
2
2
8
6
7 9
4
3
Árvore Splay (Operações)
36
� Inserção
� Como seria o algoritmo de inserção em uma árvore 
splay?
19
Árvore Splay (Operações)
37
� Inserção
� Como seria o algoritmo de inserção em uma árvore 
splay?
SPLAY-INSERT(z) 
TREE-INSERT(z)
splay(z) 
Árvore Splay (Operações)
38
� Remoção
� A remoção é realizada como em uma árvore de pesquisa 
binária (TREE-DELETE(x))
� Se o elemento existir:
� Fazemos o splay do pai do nó removido (se não for o root)
� Se o elemento não existir:
� Splay do último nó com dado (!= NIL) acessado
� Similar a uma busca sem sucesso
20
Exemplo
39
� Remova o nó 1
� Caso 1 da remoção em uma BST
2 8
6
1 7 94
4 8
6
7 9
zig
2
Exemplo
40
� Remova o nó 8 
� Caso 2 da remoção em uma BST
4 8
6
9
zig
2
2
6
9
4
21
Árvore Splay (Operações)
41
� Remoção
� Como seria o algoritmo de remoção em uma árvore 
splay?
SPLAY-REMOVE(key) 
Node n = TREE-SEARCH(key)
if (n.isEmpty())
splay(n.parent)
else
Node y = TREE-DELETE(n)
splay(y.parent)
Árvore Splay (Análises)
42
� Podem ficar desequilibradas no pior caso
� Na média de n operações em seqüência, a ordem 
de complexidade das operações inserir, remover e 
pesquisar é da ordem de O(log n)
� Análise amortizada
� Variação
� Splay top-down ao invés de bottom up
22
Árvore Splay
43
� Implementação
� Sleator 
� http://www.link.cs.cmu.edu/link/ftp-site/splaying/SplayTree.java
� Applet
� http://people.ksp.sk/~kuko/bak/index.html 
� http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%2
0tree%20applet.htm
Aplicações: Consulta Bancária
44
� Ao realizar alguma operação, seu registro sobe na 
árvore
� Quem realiza mais operações, terão acessos mais 
rápidos
� Os registros de clientes que não utilizam estes 
serviços, por sua vez, ficarão nos níveis mais 
inferiores da árvore.
23
Referências
45
� Seção 13.4
� 1a edição