AED-I-Lista-7

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 7ª Lista de Exercícios 
 
1. Em aula assumimos que a raiz de uma árvore se encontra no nível zero. Altere adequadamente as 
definições, fórmulas e algoritmos vistos em aula assumindo que a raiz se encontra no nível um. 
 
2. Indique quais árvores são árvores binárias de busca: 
 
2
9
12
14
13 30
15
2
9
12
14
13 30
15
 
2
1
3
4
5 7
6
2
1
3
4
5 7
6
 
10
5
15
20
17 22
211816
10
5
15
20
17 22
211816
 
(a) (b) (c) 
 
3. Considerando uma árvore binária de busca (ABB), qual a relação entre o número de comparações entre a 
chave procurada e as chaves dos nós e a altura da árvore, sendo que esta árvore possui n nós? 
 
4. Seja a seqüência de chaves 1, 2, ..., n, onde 1 ≤ n ≤ 7. Desenhe a ABB: 
a) com altura máxima 
b) com altura mínima 
c) quantas árvores distintas existem para cada valor de n? 
 
5. Escreva versões recursivas para os seguintes métodos de árvores binárias de busca: Minimum, 
Maximum, Insert, Preorder, Inorder, Posorder. 
 
6. Assuma uma ABB com elementos entre 1 e 1000 e chave de busca x = 363. Quais seqüências a seguir 
não podem ser uma seqüência de nós examinados na operação de busca? 
a) 2, 252, 401, 398, 330, 344, 397, 363 
b) 924, 220, 911, 244, 898, 258, 362, 363 
c) 925, 202, 911, 240, 912, 245, 363 
d) 2, 399, 387, 219, 266, 382, 381, 278, 363 
e) 935, 278, 347, 621, 299, 392, 358, 363 
 
7. Desenhe a ABB construída ao inserir a seqüência de número naturais 1, 2, 3, ..., n. Faça o mesmo para a 
seqüência inversa n, ..., 3, 2, 1. As árvores são idênticas? Isto é esperado? Explique. 
 
8. Escrever o algoritmo de inserção em uma ABB, tendo como entrada um conjunto ordenado de chaves; o 
algoritmo deve garantir que a ABB resultante tenha altura mínima. 
 
9. Desenhe a ABB construída ao inserir a seqüência de número naturais 50, 100, 30, 80, 20, 10, 90, 95, 99, 
15, 25, 40, 150, 1, 3, 7, 12. 
 
10. Quais as seqüências de nós visitados quando se percorre a seguinte ABB em pré-ordem, em-ordem e 
pós-ordem? 
 2 
15
3 30
201 4 40 
18 25 35
32 36
15
3 30
201 4 40 
18 25 35
32 36
 
 
11. Ainda considerando a árvore do exercício anterior, mostre como a árvore fica após a remoção das chaves 
3, 30, 35, 20, 15. A árvore obtida é a mesma que aquela se a ordem de remoção das chaves fosse 3, 35, 
30, 15, 20? Explique. 
 
12. Na remoção de elemento de uma ABB foi visto o caso em que, caso o nó tenha as duas subárvores, então 
se procura pelo elemento de menor valor na subárvore direita para substituir o elemento sendo removido. 
Altere a implementação fornecida para procurar o maior elemento da subárvore da esquerda. 
 
13. Nos métodos de ABB, muitos parâmetros do tipo TreePointer são passados por referência apenas por 
questões de eficiência. Indique em quais métodos esta estratégia foi utilizada, ou seja, caso a passagem 
de parâmetros seja alterada para passagem por valor, o método apresentaria o mesmo comportamento, 
embora de forma menos eficiente. Indique também em quais métodos há realmente a necessidade de 
passagem por referência, ou seja, o método não funcionaria adequadamente caso isso fosse alterado. 
 
14. Mostre que é possível obter uma ABB na qual existe uma única folha, mesmo se os elementos da árvore 
não forem inseridos em ordem estritamente crescente ou decrescente. 
 
15. Escreva um método Delete(TreeEntry x1, TreeEntry x2) para eliminar todos os elementos com chaves 
entre x1 e x2 (inclusive) de uma ABB. É permitido o uso do método Delete(TreeEntry x) em sua 
solução; entretanto, sua solução deve ser o mais eficiente possível. Assim, se sua solução consistir em 
percorrer todos os nós da árvore e somente remover aqueles entre x1 e x2, ela será considerada incorreta. 
 
16. Como no caso de listas, uma representação alternativa para ABB consiste em utilizar um elemento 
sentinela. Com isso, todos os nós terminais apontam para o nó sentinela, ou seja, a estrutura resultante é 
uma árvore em que todas as folhas ficam ancoradas em um único ponto, o nó sentinela. 
root
30
20 40
35 50
45 60
25
23 28
10
sentinel
root
30
20 40
35 50
45 60
25
23 28
10
sentinel
 
 
 3 
O nó sentinela pode ser considerado como um representante comum, compartilhado por todos os nós folhas, 
que foi usado para estender a árvore original. Escreva os algoritmos vistos para manipular uma ABB para 
ABB com sentinela. 
 
17. Considere uma ABB na qual a freqüência de acesso a cada elemento é medida empiricamente atribuindo-
se a cada nó um contador de acesso. Regularmente, a determinados intervalos de tempo (por exemplo, a 
cada k consultas), a organização da árvore é atualizada percorrendo-se a mesma e gerando uma nova 
árvore, inserindo as chaves, na nova árvore, em ordem decrescente de freqüência. Por exemplo, 
considere que inicialmente as chaves são inseridas na seguinte ordem: D, E, G, F, A, B, C formando a 
árvore: 
D
A E
B G
FC
D
A E
B G
FC
 
 
Assumindo que após k=460 consultas, a freqüência de acesso para cada chave foi: 
 
A B C D E F G 
60 50 100 10 70 90 80 
 
O número de comparações resultante é 10 + 2*(60+70) + 3*(50+80) + 4*(100+90) = 1420 para o período de 
k buscas. Colocando as chaves na ordem decrescente de freqüências, temos: C, F, G, E, A, B, D que se 
inseridos nesta ordem na nova árvore resulta em: 
C
A F
B G
D
E
C
A F
B G
D
E
 
 
Com essa nova árvore, se tivermos uma mesma freqüência de acesso para as chaves que no intervalo de 
tempo anterior, o número total de comparações é 100 + 2*(60+90) + 3*(50+70+80) + 4*(10) = 1040 o que 
melhora o tempo de busca. Escrever um algoritmo que efetue essa reorganização usando apenas ABB.