Árvores SplayÁrvores Splay
Estruturas de DadosEstruturas de Dados
Prof. Dr. Paulo Roberto Gomes LuzzardiProf. Dr. Paulo Roberto Gomes Luzzardi
Aluno: Edécio Fernando IepsenAluno: Edécio Fernando Iepsen
Splay TreeSplay Tree
É uma árvore binária de pesquisa (BST)É uma árvore binária de pesquisa (BST) É uma árvore auto-equilibrada.É uma árvore auto-equilibrada. Em qualquer operação (pesquisa, inserção, Em qualquer operação (pesquisa, inserção,
remoção) a árvore faz SPLAY.remoção) a árvore faz SPLAY. Basicamente fazer SPLAY, é trazer um Basicamente fazer SPLAY, é trazer um
elemento x para a raiz da árvore (BTT- Bring elemento x para a raiz da árvore (BTT- Bring To Top), utilizando sucessivas rotações e To Top), utilizando sucessivas rotações e tantas quanto necessárias, chamadas ZIG, tantas quanto necessárias, chamadas ZIG, ZIGZIG e ZIGZAG.ZIGZIG e ZIGZAG.
Splay TreeSplay Tree
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 usadosmais 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 UsoExemplo 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.
Splay Tree: zig e zagSplay Tree: zig e zag
Splay Tree: zig-zigSplay Tree: zig-zig
Splay Tree: zig-zagSplay Tree: zig-zag
Algoritmo de Pesquisa(x, A)Algoritmo de Pesquisa(x, A)
InícioInício Faz percurso BST até encontrar.Faz percurso BST até encontrar. Se existe o elemento x na árvore ASe existe o elemento x na árvore A Faz SPLAY do elemento xFaz SPLAY do elemento x SenãoSenão Faz SPLAY do sucessor esquerdo mais próximo de xFaz SPLAY do sucessor esquerdo mais próximo de xFimFim
Exemplo 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)Algoritmo de Inserção(A, x)
InícioInício
Faz SPLAY do elemento x .Faz SPLAY do elemento x .
Como não existe, o elemento menor mais próximo de x fica na raizComo 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 árvoreAgora é só inserir x, que passa a ser a raiz da árvore
FimFim
Exemplo 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)Algoritmo de Remoção(A, x) InícioInícioSe existe o elemento x na árvore A.Se existe o elemento x na árvore A. Faz SPLAY do elemento x.Faz SPLAY do elemento x. Faz SPLAY do elemento x, na sua subárvore esquerda.Faz SPLAY do elemento x, na sua subárvore esquerda. Traz o elemento menor mais próximo de x para a raiz.Traz o elemento menor mais próximo de x para a raiz. Remove o x.Remove o x.SenãoSenão Faz SPLAY do elemento menor mais próximo de x.Faz SPLAY do elemento menor mais próximo de x.FimFim
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ãoConclusã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ênciasReferênciasBibliografia:Bibliografia:Drozdek, Adam. Estrutura de Dados e Algoritmos em C++ (Árvores Drozdek, Adam. Estrutura de Dados e Algoritmos em C++ (Árvores
Auto-Ajustadas)Auto-Ajustadas)
Sites:Sites:http://www.cs.nyu.edu/algvis/java/SplayTree.htmlhttp://www.cs.nyu.edu/algvis/java/SplayTree.htmlhttp://w3.ualg.pt/~hshah/ped/Aula%2011/A11/aula11.htmlhttp://w3.ualg.pt/~hshah/ped/Aula%2011/A11/aula11.htmlhttp://inf.unisinos.br/~ari/estrut/splay.pdfhttp://inf.unisinos.br/~ari/estrut/splay.pdfhttp://dct.ual.pt/historial/2004_05/aed2/teoricas/Semana6.pdfhttp://dct.ual.pt/historial/2004_05/aed2/teoricas/Semana6.pdf
Demonstrações:Demonstrações:http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htmhttp://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/SplayTree-Example.http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/SplayTree-Example.htmlhtml