AED-I-Lista-8

Prévia do material em texto

1
 
Algoritmos e Estruturas de Dados I IBm1014 
Departamento de Computação e Matemática 1º Semestre/2012 
Prof. Dr. José Augusto Baranauskas 8ª Lista de Exercícios 
 
1. Calcule o fator de balanceamento de cada nó nas seguintes árvores. Há alguma árvore AVL? 
 
15
3 30
201 4 40 
18 25 35
32 36
15
3 30
201 4 40 
18 25 35
32 36
 
18
3 35
201 4 36
18
3 35
201 4 36
 
18
3 35
201 4
25
36
18
3 35
201 4
25
36
 
(a) (b) (c) 
 
2. Indique na árvore AVL seguinte em quais nós a inserção de um único elemento não causa 
rebalanceamento. Indique também em quais nós a inserção de um único elemento causa 
rebalanceamento. Neste último caso, indique o ancestral mais próximo onde a rotação deve ocorrer. 
 
 
 
3. A partir de uma árvore AVL vazia, realize a inserção da seguinte seqüência de chaves: 99, 44, 71, 80, 74, 
63, 59, 120, 98, 150. Mostre a árvore após cada inserção, indicando o nó onde ocorre a rotação e o tipo 
de rotação necessária para rebalancear a árvore. 
 
4. Considerando a árvore do exercício anterior, indique as árvores AVL resultantes da exclusão das chaves 
59 e 63. 
 
5. Mostre a árvore AVL (passo-a-passo) para a inserção das seguintes chaves, indicando a cada passo qual 
elemento foi inserido ou qual rotação foi realizada 
a) 50, 30, 20, 70, 40, 35, 37, 38, 10, 32, 45, 42, 25, 47, 36 
b) 100, 80, 60, 40, 20, 70, 30, 50, 35, 45, 55, 75, 65, 73, 77 
 
6. Escreva um algoritmo que verifica se uma dada árvore binária de busca é uma árvore AVL. Suponha que 
exista uma função que retorna a altura de uma árvore binária apontada por um ponteiro p. 
 
7. Desenhe uma árvore AVL de 20 nós de maior altura possível. 
 
8. Desenhe uma árvore AVL de altura 7 com o menor número possível de nós. 
 
 2
9. Considere uma árvore AVL T na qual a inserção de um nó q em T, tornou T desbalanceada. Seja p o nó 
desbalanceado mais próximo das folhas. 
a) Qual o valor exato de |hL(p) – hR(p)|? Por que não pode ser nem mais nem menos? 
b) Supondo hR(p) > hL(p) então existe um filho direito u de p. Por que necessariamente |hR(u) – hL(u)| = 
1? Por que não pode ser 2? Por que não pode ser 0? 
c) De acordo com (b), quando hR(p) > hL(p) existem dois casos a serem considerados: hL(u) = hR(u) + 1 
ou hR(u) = hL(u) + 1. Para cada um desses casos, apresente a rotação que rebalanceia p. Mostre que 
realmente todos os nós originalmente em T ficam balanceados (através da análise das alturas das 
subárvores). 
d) Por que o rebalanceamento de p rebalanceia toda a árvore? 
 
10. Sem utilizar estruturas auxiliares (pilhas, filas, etc) escreva um método não recursivo para determinar a 
altura de uma árvore AVL, visitando o menor número possível de nós. 
 
11. Considere a seguinte árvore AVL: 
25
15
30
45
41 56
504335
25
15
30
45
41 56
504335
 
 
a) Realize a inserção das chaves 49, 60, 65; em seguida, remova as chaves 45 e 41. Mostre todas as 
rotações e o formato da árvore após cada operação de rebalanceamento; 
b) Seja q um nó recém inserido e p o seu ancestral mais próximo que se tornou desbalanceado. Quais os 
possíveis valores para o fator de balançeamento de p após a inserção? Examinar o fator de 
balanceamento de p é suficiente para concluir se a inserção foi à esquerda ou a direita de p? Por quê? 
 
12. Considere a inserção das seguintes chaves (nesta ordem) em uma árvore AVL: 5,3,8,2,4,7,10,1,6,9,11. 
Desenhe a árvore AVL resultante e determine o fator de balanceamento de cada nó. Para essas inserções 
quais e quantas rotações foram necessárias? Por quê?