Aula de exercicios splay e skip list

Prévia do material em texto

Monitoras: Isabelly Cavalcante e Letícia Barbosa 
isabelly.cavalcante@ccc.ufcg.edu.br , leticiabarbosa94@gmail.com 
 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). 
 Insert(0) 
 
0 
 Insert(0) 
 Insert(2) 0 
2 
 Insert(0) 
 Insert(2) 
2 
0 
 Insert(0) 
 Insert(2) 
 Insert(4) 
2 
0 4 
 Insert(0) 
 Insert(2) 
 Insert(4) 
4 
2 
0 
 Insert(0) 
 Insert(2) 
 Insert(4) 
 Insert(6) 
4 
2 
0 
6 
 Insert(0) 
 Insert(2) 
 Insert(4) 
 Insert(6) 4 
2 
0 
6 
 Insert(0) 
 Insert(2) 
 Insert(4) 
 Insert(6) 
 Insert(8) 
4 
2 
0 
6 
8 
 Insert(0) 
 Insert(2) 
 Insert(4) 
 Insert(6) 
 Insert(8) 
4 
2 
0 
6 
8 
 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). 
 Search(0) 
4 
2 
0 
6 
8 
 Search(0) 
4 
2 
0 
6 
8 
 Search(0) 
4 
2 
0 
6 
8 
 Search(0) 
4 
2 
0 
6 
8 
 Search(0) 
4 
2 
0 
6 
8 
 Search(0) 
 Search(3) 
4 
2 
0 
6 
8 
 Search(0) 
 Search(3) 
4 
2 
0 
6 
8 
 Search(0) 
 Search(3) 
4 
2 
0 
6 
8 
 Search(0) 
 Search(3) 
4 
2 
0 6 
8 
 Search(0) 
 Search(3) 
 Search(5) 
4 
2 
0 6 
8 
 Search(0) 
 Search(3) 
 Search(5) 4 
2 
0 
6 
8 
 Search(0) 
 Search(3) 
 Search(5) 
 Search(8) 
4 
2 
0 
6 
8 
 Search(0) 
 Search(3) 
 Search(5) 
 Search(8) 4 
2 
0 
6 
8 
 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). 
 Delete(0) 
4 
2 
0 
6 
8 
 Delete(0) 
4 
2 
6 
8 
 Delete(0) 
2 
6 
4 8 
 Delete(0) 4 
2 6 
8 
 Delete(0) 
 Delete(2) 
4 
2 6 
8 
 Delete(0) 
 Delete(2) 
4 
6 
8 
 Delete(0) 
 Delete(2) 
 Delete(4) 
 
4 
6 
8 
 Delete(0) 
 Delete(2) 
 Delete(4) 
6 
8 
 Delete(0) 
 Delete(2) 
 Delete(4) 
6 
8 
 Delete(0) 
 Delete(2) 
 Delete(4) 
 Delete(6) 
6 
8 
 Delete(0) 
 Delete(2) 
 Delete(4) 
 Delete(6) 
8 
 Delete(0) 
 Delete(2) 
 Delete(4) 
 Delete(6) 
8 
 Delete(0) 
 Delete(2) 
 Delete(4) 
 Delete(6) 
 Delete(8) 
8 
 Delete(0) 
 Delete(2) 
 Delete(4) Empty 
 Delete(6) 
 Delete(8) 
Dada a seguinte árvore splay: 
 
 
 
 
 
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. 
A) Splay(14) 8 
4 
3 
13 17 
11 
10 
12 
15 
14 
5 7 
6 
A) Splay(14) 
8 
4 
3 
13 
17 
11 
10 
12 
15 
14 
5 7 
6 
A) Splay(14) 
8 
4 
3 
13 
17 
11 
10 
12 
15 
14 5 7 
6 
A) Splay(14) 
8 
4 
3 
13 
17 
11 
10 
12 
15 
14 
5 7 
6 
A) Splay(14) 
8 
4 
3 
13 17 11 
10 
12 15 
14 
5 7 
6 
A) Splay(14) 
8 
4 
3 
13 17 11 
10 
12 15 
14 
5 7 
6 
A) Splay(14) 
8 
4 
3 
13 
17 
11 
10 
12 
15 
14 
5 7 
6 
B) 
• Insert(4) 
4 
B) 
• Insert(4) 
• Insert(3) 
3 
4 
B) 
• Insert(4) 
• Insert(3) 
3 
4 
B) 
• Insert(4) 
• Insert(3) 
• Insert(1) 
3 
4 1 
B) 
• Insert(4) 
• Insert(3) 
• Insert(1) 
 
3 
4 
1 
B) 
• Insert(4) 
• Insert(3) 
• Insert(1) 
• Insert(2) 
3 
4 
1 
2 
B) 
• Insert(4) 
• Insert(3) 
• Insert(1) 
• Insert(2) 
3 
4 
1 
2 
B) 
• Insert(4) 
• Insert(3) 
• Insert(1) 
• Insert(2) 
3 
4 
1 
2 
 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. 
 Insert(3) 
3 
 Insert(3) 
 Insert(1) 
3 
1 
 Insert(3) 
 Insert(1) 
3 
1 
 Insert(3) 
 Insert(1) 
 Insert(4) 
3 
1 
4 
 Insert(3) 
 Insert(1) 
 Insert(4) 
3 
1 4 
 Insert(3) 
 Insert(1) 
 Insert(4) 
3 
1 
4 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
3 
1 
4 
5 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 3 
1 
4 
5 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
3 
1 
4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
3 
1 
4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
3 1 
4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
3 1 
4 
5 2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
3 
1 4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 9 
3 
1 4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
9 
3 
1 
4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
3 
1 
4 
5 
2 
9 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
3 
1 
4 
5 
2 
9 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 
3 
1 
4 
5 
2 
9 
6 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 
3 
1 4 
5 
2 
9 
6 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 3 
1 4 
5 
2 
9 
6 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 
3 
1 4 
5 
2 
9 
6 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 Insert(8) 
 
9 
6 
8 
3 
1 4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 Insert(8) 
 
9 
6 
8 
3 
1 4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 Insert(8) 
 
9 6 
8 
3 
1 4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 Insert(8) 
 Delete(3) 
 
 
9 6 
8 
3 
1 4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 Insert(8) 
 Delete(3) 
 
9 6 
8 
1 4 
5 
2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) Insert(9) 
 Insert(6) 
 Insert(8) 
 Delete(3) 
 
9 6 
8 
1 
4 
5 2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 Insert(8) 
 Delete(3) 
 
9 
6 
8 
1 
4 
5 2 
 Insert(3) 
 Insert(1) 
 Insert(4) 
 Insert(5) 
 Insert(2) 
 Insert(9) 
 Insert(6) 
 Insert(8) 
 Delete(3) 
 
9 
6 
8 1 
4 
5 
2 
 Dada a árvore splay abaixo, realize as seguintes operações 
(faça o splay após cada operação): 
◦ Procure o 13 
◦ Remova o 15 
◦ Insira o 21 
◦ Procure o 5 
 
10 
3 
9 
8 
1 
5 
16 
18 
17 
12 
11 20 
2 6 
4 7 
14 
13 15 
19 
 Search (13) 10 
3 
9 
8 
1 
5 
16 
18 
17 
12 
11 20 
2 6 
4 7 
14 
13 15 
19 
 Search (13) 10 
3 
9 
8 
1 
5 
16 
18 
17 
12 
11 20 
2 6 
4 7 
14 
13 
15 
19 
 Search (13) 10 
3 
9 
8 
1 
5 
16 
18 
17 
12 
11 20 
2 6 
4 7 
14 
13 
15 
19 
 Search (13) 10 
3 
9 
8 
1 
5 
16 
18 
17 
12 
11 
20 
2 6 
4 7 
14 
13 
15 
19 
10 
3 
9 
8 
1 
5 
16 
18 
17 12 
11 
20 
2 6 
4 7 
14 
13 
15 
19 
 Search (13) 
10 
3 
9 
8 
1 
5 
16 
18 
17 
12 
11 
20 
2 6 
4 7 
14 
13 
15 
19 
 Search (13) 
 Search (13) 
 Delete (15) 10 
3 
8 
1 
5 
16 
18 
17 
20 
2 6 
4 7 
14 
13 
15 
19 
12 
11 9 
 Search (13) 
 Delete (15) 10 
3 
8 
1 
5 
16 
18 
17 
20 
2 6 
4 7 
14 
13 
19 
12 
11 9 
 Search (13) 
 Delete (15) 10 
3 
8 
1 
5 
16 18 
17 
20 
2 6 
4 7 
14 
13 
19 
12 
11 9 
 Search (13) 
 Delete (15) 
3 
1 
5 
16 
18 
17 
20 
2 6 
4 7 
14 
13 
19 
10 
8 12 
11 9 
 Search (13) 
 Delete (15) 
3 
1 
5 
16 
18 
17 
20 
2 6 
4 7 
14 
13 
19 
10 
8 12 
11 9 
 Search (13) 
 Delete (15) 
 Insert (21) 
3 
1 
5 
16 
18 
17 
20 
2 6 
4 7 
14 
13 
19 21 
10 
8 12 
11 9 
 Search (13) 
 Delete (15) 
 Insert (21) 
3 
1 
5 
16 
18 
17 
20 
2 6 
4 7 
14 
13 
19 
21 
10 
8 12 
11 9 
 Search (13) 
 Delete (15) 
 Insert (21) 
3 
1 
5 
16 
18 
17 
20 
2 6 
4 7 
14 
13 
19 
21 10 
8 12 
11 9 
 Search (13) 
 Delete (15) 
 Insert (21) 
3 
1 
5 
16 
18 
17 
20 
2 6 
4 7 
14 
13 
19 
21 
10 
8 12 
11 9 
 Search (13) 
 Delete (15) 
 Insert (21) 
18 
17 
20 
19 
21 
3 
1 
5 
16 
2 6 
4 7 
14 
13 
10 
8 12 
11 9 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
 
3 
1 
5 
16 
2 6 
4 7 
14 
13 
10 
8 12 
11 9 
18 
17 
20 
19 
21 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
 
1 
16 
14 
13 
10 
8 12 
11 9 
3 
5 
2 6 
4 
7 
18 
17 
20 
19 
21 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
 
1 
16 
14 
13 
10 
8 12 
11 9 
3 
5 2 
6 4 
7 
18 
17 
20 
19 
21 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
 
16 
14 
13 
10 
8 12 
11 3 9 
1 5 
2 6 4 
7 
18 
17 
20 
19 
21 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
 
16 
14 
13 
10 
8 12 
11 
3 
9 
1 
5 
2 
6 
4 
7 
18 
17 
20 
19 
21 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
10 
3 9 
8 
1 
5 
16 
12 
11 
2 
6 
4 
7 
14 
13 
18 
17 
20 
19 
21 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
10 
3 
9 
8 
1 
5 
16 
12 
11 
2 
6 4 
7 
14 
13 
18 
17 
20 
19 
21 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
10 
3 
9 
8 
1 
5 16 
12 
11 
2 
6 4 
7 
14 
13 
18 
17 
20 
19 
21 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
10 
3 
9 
8 1 
5 
12 
11 
2 
6 
4 
7 
14 
18 
17 
20 
19 
21 
16 
13 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
10 
3 
9 
8 1 
5 
16 18 
17 
12 
11 
20 
2 
6 
4 
7 
14 
13 
19 
21 
 Search (13) 
 Delete (15) 
 Insert (21) 
 Search (5) 
10 
3 
9 
8 
1 
5 
16 
18 
17 
12 
11 
20 2 
6 
4 
7 
14 
13 
19 
21 
 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. 
 Faça um algoritmo na skip list que imprime os nós da skip 
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.