Baixe o app para aproveitar ainda mais
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.
Compartilhar