UNIVERSIDADE DO ALGARVE
Faculdade
de Ciências e Tecnologia
Área
Departamental de Engenharia Electrónica e Computação
|
UNIVERSIDADE DO ALGARVE Faculdade
de Ciências e Tecnologia
|
PED - Aula Nº11
Splay Tree: - É 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.
| Rotação ZIG
(Y):
| |
|
1) |
2) |
 |
|
Conclusão : Nesta rotação o filho direito do elemento Y, fica o filho esquerdo do elemento X, que é o pai de Y.
| Rotação ZIGZIG(X):
| ||
|
1) |
2) | 3) |
 |
 |
 |
1) Para fazer o ZIGZIG(X) primeiro temos que fazer o ZIG do pai de X (que é o Y).
2) Agora fazemos o ZIG de X.
Conclusão: No fundo é ZIG (Y), e ZIG (X) respectivamente.
| Rotação ZIGZAG(X):
| ||
| 1) | 2) | 3) |
 |
 |
 |
1) Ao contrário do ZIGZIG, primeiro faz-se o ZIG de X com o pai de X (que é o Y).
2) Depois faz-se o ZIG de X com o avô de X (que é o Z).
Conclusão: No fundo corresponde a fazer ZIG (X) e ZIG(X).
Algoritmos básicos da àrvore SPLAY.
Seja um elemento x e uma àrvore A.
Algotitmo de Pesquisa( x, A) :
- Inicio
- Faz percurso BST até encontrar.
- Se existe o elemento x na àrvore A
- Faz SPLAY do elemento x
- Se não existe o elemento x na àrvore A
- Faz SPLAY do sucessor esquerdo mais proximo de x
- Fim
Exemplo de pesquisa( 9, A):
| 1) | 2) | 3) |
 |
 |
 |
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.
- Inicio
- Faz SPLAY do elemento x .
- Como não existe, o elemento menor mais proximo de x fica na cabeça.
- Agora é só inserir x, ficando a cabeça o filho esquerdo do elemento inserido e a subàrvore direita o seu filho direito.
- Fim
Exemplo de inserção( 8, A):
| 1) | 2) | 3) |
 |
 |
 |
1) SPLAY(8)
2) 7 fica na cabeça
3) Inserir 8, 7 é o seu filho esquerdo,e 10 o seu filho direito.
- Inicio
- Se existe o elemento x na àrvore A.
- Faz SPLAY do elemento x.
- De seguida faz SPLAY do elemento x, na sua subàrvore filha esquerda.
- Automaticamente trouxe o elemento menor mais proximo de x para a cabeça.
- Agora é só remover o x.
- Se não existe o elemento x na àrvore A
- Faz SPLAY do elemento menor mais próximo de x.
- Fim
Exemplo de remoção(12, A):
| 1) | 2) | 3) | 4) | 5) |
|
 |
 |
 |
 |
1) Pesquisa tipo BST
2) SPLAY (12,A)
3) SPLAY (12,A') onde A' é a subàrvore filha esquerda do elemento 12, assim temos a certeza que o 12 não vai ter filho esquerdo.
4) Temos o elemento menor mais próximo de 12 à cabeça e sem filho esquerdo podemos então remover.
5) Remoção fácil, elimina-se o 12, é só ligar o pai de x (12) com o filho direito de x(15)
Links Interessantes para testar este algoritmo :
http://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/home.html
http://www.cs.mcgill.ca/~rsinge/web251.html
http://www.cs.nyu.edu/algvis/java/index.html
Para qualquer comentário contacte:
