Árvores espalhadas (Splay)
o Objectivo
•
árvores mais simples do que as árvores AVL
- não forçar o equilíbrio
- não manter informação de altura
•
permitir pior caso para uma só operação O(n)
•
garantir pior caso amortizado O(log n)
- uma qualquer sequência de m operações demora, no pior caso O(m log n) - não há sequências más
- reestruturar a árvore para impedir repetição de operações O(n)
o Ideia
•
cada nó acedido é puxado para a raiz por uma sequência de rotações
- é provável que volte a ser acedido proximamente, com baixo custo
- árvore auto-ajustável: alterações devem tender para equilibrar
•
Ex: registos de doentes num hospital
- podem estar no fundo da árvore se o doente não estiver internado
- passa para a raiz no momento do internamento; permanece aí perto algum tempo, com acesso rápido;
- vai afundando se não voltar a ser acedido
SPLAY
Tentativa
• fazer rotações simples até o nó
chegar à raiz
k4
k3
k2
k5
F
E
k5
D
k4
k1
A
B
k3
C
k1
F
E
D
k2
C
A
B
SPLAY
Rotações simples
k5
•••
k4
k1
F
E
k2
k1
k3
k5
k2
A
B
C
D
k4
A
k3
• o nó k3 está quase à mesma profundidade que k1 inicialmente
• uma visita a k3 seria também pesada e afundaria um outro nó
• esta solução não serve
F
B
C
E
D
SPLAY
Splaying
o
rotações ascendentes desde o nó acedido x até à raiz
o
se p (pai de x) é a raiz: rotação simples (zig)
o
senão, existe um a (avô de x) e
• se x é filho direito (esquerdo) de p e p filho direito (esquerdo) de a : zig-zig
• se x é filho direito (esquerdo) de p e p filho esquerdo (direito ) de a : zig-zag
• por acesso entende-se inserção ou pesquisa
• o zig-zag é uma rotação dupla AVL
• o zig-zig é específico do splay
SPLAY
Rotações elementares
a
x
p
D
zig-zag
p
x
A
B
a
A
C
B
a
p
D
A
A
a
C
B
D
x
p
x
C
B
zig-zig
C
D
SPLAY
Espalhando em k1
k5
k4
k3
F
E
k5
k2
D
k4
k1
A
k1
B
F
zig-zag
E
C
k2
k3
zig-zig
A
B
C
D
SPLAY
Árvore espalhada
k1
k2
k4
zig-zig
A
k3
B
C
k5
D
E
F

fazer uma pesquisa de k1 extrai a respectiva informação e tem como efeito lateral reestruturar a
árvore, tornando-a mais equilibrada

não só o nó k1 veio para raiz como os que estavam no seu caminho ficaram mais perto dela
SPLAY
Exemplo
• começar com lista vazia e inserir
sucessivamente nós com chave de 1 a 7
• consultar toda a árvore pela mesma ordem
1
1
2
2
(i) inserir 1
7
2
1
1
(ii) inserir 2 com
espalhamento
6
3
5
2
3
4
1
•••
(iii) inserir 3 com
espalhamento
3
(vii) inserir 7 com
espalhamento
2
(viii ) acesso ao nó 1
7
1
6
7
5
4
1
6
4
4
1
2
2
3
2
6
1
5
3
2
2
4
7
5
3
(ix) acesso ao nó 2
1
3
6
5
4
1
3
7
6
5
SPLAY
7
Análise do exemplo
o
o
o
Inserções
•
cada inserção é feita em tempo constante
•
total das n inserções é O(n)
•
a árvore resultante é muito má (lista) mas o processo encontra-se adiantado
relativamente a n * O(log n)
Acessos
•
acesso ao nó 1 é O(n) - acesso muito mau que faz reduzir a vantagem acumulada
•
acesso ao nó 2 já é O(n/2)
•
globalmente: calcula-se tempo amortizado
Conclusão
•
consegue-se sempre, para as primeiras m operações, manter o tempo amortizado,
mesmo no pior caso, abaixo de O(m log n)
SPLAY
Implementação
o
Implementação directa não pode ser recursiva
•
as rotações afectam pares de nós, a começar por baixo: é necessário primeiro
descer até ao nó alvo para saber se o caminho tem número par ou ímpar de nós
•
processamento em dois passos
- descer até ao nó
- subir efectuando as rotações  é preciso guardar o caminho
•
o
o
armazenamento do caminho
•
pilha
•
acrescentar a cada nó um apontador para o pai (que as rotações têm de manter)
Apagamento de um nó
•
aceder ao nó, o que o torna raiz com subárvores TL e TR; eliminar o nó;
•
procurar o maior elemento de TL, rodá-lo para a raiz de TL;
•
TL não tem subárvore direita; ligar TR como subárvore direita de TL.
Implementação mais simples do que versão não recursiva das árvores AVL
SPLAY
Árvores Splay Top-Down

Método de splay em apenas 1 passagem top-down
 mantém o custo amortizado
 não requer espaço adicional para a pilha dos nós no caminho

Operação de Splay vai manter 3 árvores
 árvore com raiz no nó corrente - árvore “do meio”
 árvore da esquerda L: nós menores que X que não estão na subárvore de X
 árvore da direita R: nós maiores que X que não estão na subárvore de X
 Início: L e R vazias e a raiz da árvore em X

Splay: realizado de cima para baixo
 zig, zig-zag e zig-zig definidos como operações entre as 3 árvores
 passo final reúne a árvore
SPLAY
Operações Top-down
X
L
R
zig
Y
L
Y
R
A
A
X
B
B
X
L
R
L
Z
R
A
Y
C
zig-zig
Y
Z
A
X
B
B
C
SPLAY
Operações Top-down
X
L
R
zig-zag
Y
Z
L
R
B
C
Y
X
Z
A
A
B
X
L
Y
R
C
C
Y
L
Z
zig-zag
A
Z
A
simplificado
R
X
B
C
B
SPLAY
Reunião das árvores
X
L
X
R
união
A
B
L
R
A
B
SPLAY