Lista5_AVL_Heap

Prévia do material em texto

Universidade Federal de Campina Grande 
Centro de Engenharia Eletrica e Informática 
Departamento de Sistemas e Computação 
Graduação em Ciência da Computação 
Aula de exercícios 
(Árvores AVL e Heaps) 
Obs: Considere as representações (e implementações) vistas em sala de aula. Nas estruturas recursivas, 
resolva as questões usando recursão. 
 
1. Mostre como implementar uma pilha usando apenas uma fila de prioridade (heap) e uma 
instância de uma variável adicional. Dica: procure pensar que os dados armazenados contém uma 
chave e dados satélites. A chave é usada para ordenar os elementos. 
 
2. O vetor [23,17,14,6,13,10,1,5,7,12] representa uma heap? Justifique sua resposta. 
 
3. Partindo de uma árvore AVL vazia, realize a inserção da seguinte sequência de chaves: 99, 44, 71, 
80, 74, 63, 59, 120, 98, 150. Redesenhe a árvore após cada inserção. Indique para cada rotação 
feita, o nó desregulado e a rotação aplicada (LL,RR,LR,RL). É necessário indicar também as 
inserções onde não houve rotação. 
 
4. Usando a árvore construída no exercício anterior, remova os nós 59 e 63 mostrando as árvores 
resultantes a cada exclusão e a rotação aplicada (ou se não foi necessário fazer rotação). 
 
5. Um programador A inseriu os elementos do vetor [14,8,25,19,16,6,3,4,5] em ordem em uma 
árvore AVL inicialmente vazia. Um programador B inseriu os elementos do vetor 
[14,8,25,19,16,6,3,5,4] em ordem em uma outra árvore AVL inicialmente vazia. Ambos 
programadores afirmam que apenas rotações simples aconteceram. Eles estão corretos? 
Justifique sua resposta. 
 
6. Imagine que você tem o vetor [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] e quer inseri-los numa 
árvore AVL inicialmente vazia de forma a evitar rotações. Note que se você inserir nessa ordem, a 
árvore começa a pesar para a direita e as rotações inevitavelmente acontecem. Você teria alguma 
ideia para inserir esses elementos na árvore AVL de forma a evitar qualquer rotação? Se sim, 
descreva sua ideia.