Splay Tree

RVORES
SPLAY
Equipe:
Flvio Gabriel
Karine Alecrim
William Aoki
INTRODUO
Inventada por Adelson Velskii e Landis - 1962.
um tipo de rvore Binria de Pesquisa (BST)
mximo 2 filhos
todos ns esquerda contem subrvores com valores
menores ao n raiz da subrvore;
todos ns direita contem valores maiores ao n raiz da
subrvore;
INTRODUO
rvores mais simples que AVL:
no foram o equilbrio;
no mantm informao de altura.
Possui trs operaes bsicas: pesquisa,
insero e remoo.
Em todas operaes a rvore faz SPLAY.
Garante pior caso amortizado O(logn)
ESPALHAMENTO
O que fazer SPLAY?
trazer um elemento X para a raiz da rvore
(BTT- Bring To Top), utilizando sucessivas
rotaes e tantas quanto necessrias.
Objetivos:
Minimizar o nmero de acessos para achar a
chave requerida.
Otimizar a eficincia das operaes, atravs da
freqncia com que cada n acessado,
mantendo estes ns na parte superior da rvore.
Torna mais acessvel o que mais usado;

Ajusta a estrutura da rvore frequncia de
acesso aos dados;
Junto raiz esto os elementos
mais usados
mais recentes
Os elementos mais inativos ficam mais
longe da raiz;
O recurso implementado por meio de
rotaes nos ns.
ROTAES NA SPLAY TREE
Acontecem dois tipos de rotaes:
1- Rotao simples:
A) Zig Direita
B) Zig Esquerda
Mesma que a AVL

2- Rotaes duplas:
A) Zig-Zig Direita
B) Zig-Zig Esquerda
C) Zig-Zag Esquerda e Direita
ROTAO ZIG
Nesta rotao, o filho direito do elemento Y ficar o filho esquerdo do

elemento X, que era pai de Y.
a rotao de um n sobre seu pai, permanecendo a rvore com a

mesma altura.
Antes
Depois
X
Y
ROTAO ZIG-ZIG
Para fazer o zig-zig de X, primeiro temos que fazer o zig do pai de X (que
Y).
Depois, fazemos o zig de X.
Concluso: no fundo feito zig (Y) e zig (X), respectivamente.
Antes
Y
X
1
4
3
X
2
Depois
1 2 3 4
ROTAO ZIG-ZAG
Ao contrrio de Zig-Zig, primeiro devemos fazer o Zig de X com o pai de X
(que o Y).
Depois fazer o Zig de X com av de X (que o Z).
Concluso: No fundo corresponde a fazer Zig (X) e Zig (X).
Antes
Y
1
Y
1
X
2
Depois
RESUMO:
(a) Zig: rotao simples.
(b) Zig-zig: duas rotaes simples
(c) Zig-zag: rotao dupla.
BUSCA / PESQUISA
Uma splay tree uma rvore de busca
binria com a diferena interessante:
sempre que um elemento procurado,
a splay tree reorganizada para mover
esse elemento para a raiz da rvore,
sem quebrar a rvore de busca binria.
Se o pedido seguinte de pesquisa para
o mesmo elemento, este pode ser
devolvido imediatamente.
Em geral, se um pequeno nmero

de elementos est sendo muito
utilizado, eles tendem a ser
alocados perto do topo da rvore
e, assim, so encontrados
rapidamente.
COMO PESQUISAR
Uma idia simples para a pesquisa de apenas um elemento
que quando este acessado, rotaes da rvore so usadas
para mov-lo para o topo da rvore.
PASSO A PASSO
Inicia-se uma pesquisa do tipo BST;
- BST um tipo especial de busca em rvore binria: para cada n
x, todos os ns na subrvore esquerda de x tm chave menor que
x.key e todos os ns na subrvore direita de x tm chave maior que
x.key.
Caso 1 - N no encontrado:
- Faz-se um splay do ltimo n no nulo encontrado na busca(menor ou maior
que o valor procurado)
Caso 2 N encontrado:
- Faz-se splay com o n encontrado(coloc-lo no topo da rvore)
Para finalizar a busca o valor deve estar na raiz da rvore e os valores
equilibrados
ESTRUTURA DE DADOS
EXEMPLO DE INSERO
1) Inserir 8.
2) 7 vai para a raiz (primeiro elemento menor que 8).
3) Inserir 8, 7 ficar o seu filho esquerdo, e 10 o seu
filho direito.
7
6
12
9
10
10
11 15
12
10
9
6
11 15
12
11
15
EXEMPLO
DE
Incio
Pesquisa o elemento. Se existe o elemento 12 na rvore:
Faz SPLAY do elemento 12.
Faz SPLAY do elemento 12, na sua subrvore esquerda.
Traz o elemento menor mais prximo de 12 para a raiz. (continua no prx. slide)
Remove o 12.
REMOO
(ELEM. 12)
Seno
Faz SPLAY do elemento menor mais prximo de 12.
Fim
10
11
7
6
10
11
15
11
15
10
12
12
12
6
6
15
EXEMPLO
DE
REMOO
(ELEM. 12)
Incio
Se existe o elemento 12 na rvore A.
Seno
Faz SPLAY do elemento 12.

Faz SPLAY do elemento 12, na sua subrvore esquerda.
Traz o elemento menor mais prximo de 12 para a raiz.
Remove o 12.
Faz SPLAY do elemento menor mais prximo de 12.
Fim
11
10
12
Antes
10
15
12
8
7
9
7
11
15
APLICAES
Consultas bancrias
Ao fazer uma consulta, o registro de um cliente ser levado para o topo
da rvore, diminuindo o tempo de acesso para as prximas consultas.
Assim, clientes que fazem consultas frequentemente, tero acesso mais
rpido. Os registros de clientes que no utilizam estes servios, por sua
vez, ficaro nos nveis mais inferiores da rvore.
Sistemas de Arquivos
Microsoft Windows utiliza na sua indexao de arquivos por rvore Splay.
APLICAES
Hospital
Registro de pacientes recentes vai para a raiz no momento da internao
e permanece por algum tempo. Vai afundando, caso no seja acessado.
Particularmente til na implementao de caches:
Proxy Squid utiliza rvores Splay para manipular o cache interno de
pginas Web.
CONCLUSO
rvores Splay podem ficar desequilibradas, mas garantem uma complexidade
O(log n) ao longo do tempo de utilizao (complexidade amortizada).
Ajusta a rvore frequncia de acesso aos dados: Junto raiz esto os
elementos mais usados / mais recentes (mais disponveis). Os mais inativos ficam
mais longe da raiz.
importante notar que em um acesso uniforme, a performance da rvore Splay
ser considerada pior que em outro tipo de rvore.
H estudos empricos, que defendem que, em muitos casos reais, se verifica que
90% dos acessos so feitos apenas 10% dos elementos.
REFERNCIAS BIBLIOGRFICAS
http://cs.usfca.edu/~galles/visualization/SplayTree.html
www.ufjf.br/jairo_souza/files/2009/12/5-Indexao-Splay-Tree.pdf
www.en.wikipedia.org/wiki/Splay_tree
DESAFIO
DESAFIO
Insira,
em uma Splay tree vazia, os

seguintes nmeros: 7, 3, 1, 5, 2.
Remover o nmero 3.

Splay Tree

Enviado por

Direitos autorais:

Formatos disponíveis

Splay Tree

Enviado por

Dados do documento

Descrição original:

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Splay Tree

Enviado por

Direitos autorais:

Formatos disponíveis

RVORES

Torna mais acessvel o que mais usado;

ROTAES NA SPLAY TREE

Acontecem dois tipos de rotaes:

Mesma que a AVL

Nesta rotao, o filho direito do elemento Y ficar o filho esquerdo do

a rotao de um n sobre seu pai, permanecendo a rvore com a

(b) Zig-zig: duas rotaes simples

(c) Zig-zag: rotao dupla.

Em geral, se um pequeno nmero

Faz SPLAY do elemento menor mais prximo de 12.

Faz SPLAY do elemento 12.

em uma Splay tree vazia, os

Você também pode gostar