AAED - Lista de exercícios 6

Prévia do material em texto

Pós-Graduação em Ciência da Computação Universidade Federal de São Paulo - São José dos Campos
Exerćıcios sobre Árvores B
AAED — Análise de Algoritmos e Estruturas de Dados
Prof. Jurandy G. Almeida Jr.
1o Semestre de 2020
Exerćıcios
1. Sob quais condições deve ser considerado o uso de um arquivo sequencial indexado? Justique
a sua resposta.
2. Sob quais condições o uso de uma árvore binária de pesquisa pode ser melhor do que uma
árvore B para gerir dados em memória secundária? Justifique a sua resposta.
3. Quais os problemas de se usar árvores binárias de pesquisa como estruturas para gerir dados
em memória secundária? Justifique a sua resposta.
4. Explique a seguinte sentença: “Árvores B são constrúıdas de baixo para cima, enquanto
árvores binárias são constrúıdas de cima para baixo”.
5. Por que árvores B são consideradas geralmente superiores às árvores binárias de busca para
pesquisa externa, embora árvores binárias sejam comumente usadas para pesquisa interna?
6. Dada uma árvore B de ordem m = 128, responda:
(a) Qual o número máximo de descendentes de uma página não folha?
(b) Qual o número mı́nimo de descendentes de uma página não folha que não seja a página
raiz?
(c) Qual o número mı́nimo de descendentes da página raiz?
(d) Qual o número mı́nimo de itens de uma página folha?
(e) Quantos itens há numa página não folha com 200 descendentes?
(f) Qual a profundidade máxima de uma árvore que contém 100.000 chaves?
7. Explique como encontrar o item com a menor chave armazenada em uma árvore B.
8. A que condições deve satisfazer uma árvore B de ordem m para que a inserção de um item
ocasione o aumento da altura da árvore?
9. A que condições deve satisfazer uma árvore B de ordem m para que a remoção de um item
ocasione a redução da altura da árvore?
10. Por que a redistribuição deve ser tentada antes da fusão durante a remoção de um item
situado em uma página com ocupação mı́nima de uma árvore B?
11. Quais as vantagens do uso da técnica de redistribuição quando da inserção e remoção de itens
em uma árvore B?
12. Se um item não está em uma página folha de uma árvore B, o que garante que o seu sucessor,
se existir, estará obrigatoriamente localizado em uma página folha?
13. Qual é o pior caso do algoritmo de inserção de um item em uma árvore B de ordem m? Como
deve ser a árvore nesse caso?
14. Mostre passo a passo as árvores B de ordem m = 2 resultantes da inserção das chaves abaixo.
(a) C G J X
(b) C G J X N S U O A E B H I
(c) C G J X N S U O A E B H I F
(d) C G J X N S U O A E B H I F K L Q R T V U W Z
15. Seja uma árvore B de ordem m = 3 e altura h = 3. Qual o número máximo de itens nessa
árvore? E o número mı́nimo? Justifique.
16. Para uma árvore B de ordem m > 0 e altura h > 0, calcule em função de m e h o número
mı́nimo nmin e máximo nmax de itens que ela pode possuir.
17. Suponha que você tem uma árvore B que contém n itens em um arquivo não ordenado. A
altura da árvore B é h. Indique o número mı́nimo e máximo de páginas transferidas da
memória secundária necessárias para recuperar, adicionar e remover um registro. Justifique
a sua resposta.
18. Suponha que se quer remover um item de uma página em uma árvore B. Você olha para a
direita e percebe que uma redistribuição não vai adiantar, será necessária a fusão. Você olha
para a esquerda e percebe que uma redistribuição é uma opção aqui. Você escolheria fundir
ou redistribuir?
19. Considere a afirmação: “uma árvore B não pode crescer em profundidade até que esteja 100%
cheia”. Discuta essa afirmação. Ela é correta? Explique sua resposta.
20. Mostre passo a passo as árvores obtidas a partir da inserção das chaves M D H Q U A B
C E F G I J K L N O R S T V W em uma árvore B de ordem m = 2 e, a cada passo, ou
seja, a cada inserção, determine quantas transferências de páginas da memória secundária são
necessárias para completar a operação de inserção e as páginas que foram acessadas.
21. Escreva um algoritmo que, dada uma árvore B e uma chave, retorne o sucessor imediato dessa
chave.
22. Considere a árvore B de ordem m = 1 da figura a seguir e mostre passo a passo as árvores
obtidas a partir da inserção das chaves 62, 50, 59, 10, 35, 78 e 90, nesta ordem.
• 40 • 60 •
• 30 • • • 50 • • • 65 • 68 •
23. Considere a árvore B de ordem m = 1 da figura a seguir e mostre passo a passo as árvores
obtidas a partir da remoção da chave 30 e inserção das chaves 32, 35, 40, 12 e 15, nesta ordem.
Caso necessário, dê a preferência para a promoção da maior chave da subárvore à esquerda,
ou seja, o predecessor.
• 30 • •
• 10 • 15 • • 35 • 40 •
• 5 • • • 12 • • • 16 • • • 32 • • • 38 • • • 46 • •
24. Mostre passo a passo as árvores obtidas a partir da remoção das chaves A, B, Q e R da
árvore-B de ordem m = 2 apresentada na figura abaixo. Caso necessário, dê a preferência
para a promoção da maior chave da subárvore à esquerda, ou seja, o predecessor.
• M • • • •
• D • H • • • • Q • U • • •
• A • B • C • • • E • F • G • • • I • J • K • L • • N • O • • • • R • S • T • • • V • W • • •
25. A partir da árvore B de ordem m = 2 abaixo, mostre passo a passo a árvore resultante das
operações a seguir, indicando as páginas que sofrem modificações, bem como a ocorrência de
divisão, fusão ou redistribuição.
73
22 46
7 11 25 28 32 38 54 70
81 86
74 77 83 84 91 96 99
(a) Inserção das chaves 61, 71, 65 e 55, nesta ordem, sem utilizar redistribuição.
(b) Inserção das chaves 61, 71, 65 e 55, nesta ordem, com o uso de redistribuição.
(c) Remoção das chaves 54, 32 e 28, nesta ordem. Caso necessário, dê a preferência para a
promoção da maior chave da subárvore à esquerda, ou seja, o predecessor.
(d) Remoção das chaves 4, 11, 38 e 22, nesta ordem. Caso necessário, dê a preferência para
a promoção da maior chave da subárvore à esquerda, ou seja, o predecessor.
26. Escreva um algoritmo para pesquisar itens de árvores B de acordo com a ordem de sua chave,
isto é, Search(k) encontra a k-ésima menor chave da árvore. Qual é o custo de melhor e pior
caso desse algoritmo?
27. Qual a diferença entre uma árvore B e uma árvore B*? Que melhoras a B* oferece sobre
a árvore B e que complicações ela introduz? Qual é a altura mı́nima de uma árvore B* de
ordem m comparada com uma árvore B de ordem m?
28. Mostre passo a passo as árvores obtidas a partir da inserção das chaves M D H Q U A B C
E F G I J K L N O R S T V W em uma árvore B* de ordem m = 2.
29. Mostre passo a passo as árvores obtidas a partir da inserção das chaves M D H Q U A B C
E F G I J K L N O R S T V W em uma árvore B+ de ordem m = 2.
30. A partir da árvore B+ de ordem m = 1 abaixo, mostre passo a passo a árvore resultante da
inserção das chaves 19 e 27; seguida da remoção das chaves 5, 9, 12, 4 e 11, nesta ordem.
Caso necessário, dê a preferência para a promoção da maior chave da subárvore à esquerda,
ou seja, o predecessor.
13 30
5 10
1 4 5 9 11 12
20
13 18 20 29
40 50
30 38 41 45 60 70
31. Descreva as diferenças entre uma árvore B e uma árvore B+ no que diz respeito a quantidade
de chaves, localização dos itens, número de páginas acessadas durante as operações e diferenças
entre páginas internas e externas.
32. Faça uma comparação entre árvore B, árvore B* e árvore-B+ em relação às operações de
pesquisa, inserção e remoção.