Lista6_Splay_Skiplist

Prévia do material em texto

Universidade Federal de Campina Grande 
Centro de Engenharia Elétrica e Informática 
Departamento de Sistemas e Computação 
Graduação em Ciência da Computação 
 
Aula de exercícios sobre Splay e SkipList 
1. Dada uma árvore splay inicialmente vazia, insira as chaves 0, 2, 4, 6, 8 nessa ordem nela e 
desenhe a árvore depois de cada operação (faça o splay a cada operação). 
 
2. Considerando a árvore splay construída na questão anterior pesquise pelas chaves 0, 3, 5, 8 
nessa ordem e mostre as árvores splay resultando após cada procura (faça o splay a cada 
operação). 
 
3. Considerando a árvore splay da questão anterior, delete as chaves 0, 2, 4, 6, 8 nessa ordem e 
mostre as árvores resultantes após cada operação (faça o splay após cada operação). 
 
4. Dada a seguinte árvore splay: 
 
8 
 / \ 
 / \ 
 / \ 
 / \ 
 / \ 
 3 10 
 \ \ 
 4 11 
 \ \ 
 6 12 
 / \ \ 
 5 7 15 
 / \ 
 / \ 
 13 17 
 \ 
 14 
 
a. Mostre a árvore resultante do splay do nó 14. 
b. Encontre uma sequência de operações (inserir, excluir ou pesquisar) na árvore 
inicialmente vazia, que resultará na seguinte árvore. 
 
 2 
 / \ 
 1 3 
 \ 
 4 
 
 
5. Mostre o resultado da inserção (árvore final) dos elementos 3, 1, 4, 5, 2, 9, 6, 8 em uma 
árvore splay inicialmente vazia. Em seguida remova o elemento 3 e mostre a árvore 
resultante. 
6. Dada a árvore splay abaixo, realize as seguintes operações (faça o splay após cada operação): 
a. Procure o 13 
b. Remova o 15 
c. Insira o 21 
d. Procure o 5 
 
 
 
 
 
 
 
 
 
7. Modificar o método search da skip lista para que ele vá diretamente para o nó quando ele estiver 
presente na skip list. Ou seja, o algoritmo vai descendo nos nós forward. Se encontrar em algum 
nó forward o valor da chave então segue na horizontal e pára. Caso contrário vai descendo até 
encontrar um nó com menor chave e caminha para ele repetindo o processo. 
 
8. Faça um algoritmo na skip list que imprime os nós da skip list por altura e ordem crescente e suas 
alturas na ordem decrescente. Por exemplo, se uma skip list possui nós com altura 4 (8, 14, 21) e 
nós com altura 3 (4, 12, 18) e nós com altura 2 (17, 25): 
[(4,3),(8,4),(12,3),(14,4),(17,2),(18,3),(21,4),(25,2)], o algoritmo imprimiria a sequência 8, 14, 21, 
4, 12, 18, 17, 25.