Lista Estrutura de Dados 2

Prévia do material em texto

Fundação Universidade Federal de Rondônia
Departamento Acadêmico de Ciência da Computação
Estrutura de Dados II
Giullia de Souza Santos
Thauan Costa da Silva
Exercícios ‐ Árvores B e variações
1. Criar uma árvore‐B+ pela inserção das chaves A, B, C, D, E, F, G, H, I e J, nesta
ordem.
∙ Ordem da árvore: 3
∙ Blocos de 3 registros.
2. Dada uma árvore ‐B+ abaixo, remova L, M, K e A, nesta ordem.
∙ Número mínimo de registros por bloco=2
∙ Número máximo de registros por bloco=4
∙ Ordem da árvore=3
3. Quais os separadores dos blocos, considerando uma
árvore‐B+ pré‐fixada?
R: BY e DE.
4. Construa a árvore‐B+ pré‐fixada sobre os blocos do exercício 3.
5. Realize as seguintes operações sobre a árvore‐B+ pré‐fixada do
exemplo anterior
a) inserção de CARTER
b) inserção de DRAG
c) remoção de BIXBY
d) remoção de COLE
6. Quais os problemas de se usar árvores binárias de busca e árvores AVL
como estruturas de índices para grandes volumes de dados?
R: Um dos maiores problemas é o elevado número de acessos ao disco ao
utilizar essas estruturas de dados para grandes volumes de dados. Assim,,
como exemplo as ABB’s podem facilmente se tornar desbalanceadas, o que
leva a operações de busca, inserção e remoção com complexidade O(n) no
pior caso. Além disso, as AVL’s necessitam de constantes operações de
balanceamento, o que pode ocasionar um overhead significativo em termos
de tempo.
7. Considere uma árvore‐B de ordem 3. Considere que o primeiro elemento
do segundo nó é a chave promovida durante o particionamento do nó. Insira
as seguintes chaves no índice: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q,
R, S, T, U, V, X, Z. Qual o efeito da inserção das chaves em ordem alfabética?
A árvore degenerou?
R: A árvore não degenerou,e se manteve completa em níveis, porém não ficou
perfeitamente balanceada
8. Quais as vantagens do uso da técnica de redistribuição quando da
inserção e remoção de chaves em uma árvore‐B?
R: A redistribuição oferece como principal vantagem uma melhor taxa de
ocupação dos nós, tornando mais eficiente o uso do espaço e possibilitando
uma árvore de menor altura, assim, diminuindo o número de acessos ao
disco necessários durante as operações de busca, inserção e remoção.
9. Suponha que você vai remover uma chave em uma árvore‐B, a qual causa
underflow na página. Se pela página irmã do lado direito é necessária
concatenação, e pela página irmã do lado esquerdo é possível redistribuição,
qual opção você escolheria? Por quê?
R: Nesse cenário, a melhor opção se dá pela redistribuição. Visto que a
redistribuição não modifica a estrutura da árvore e proporciona uma maior taxa
de ocupação das páginas/nós.
10. Qual a diferença entre uma árvore‐B e uma árvore‐B*? Quais as
vantagens e as desvantagens da árvore‐B*?
R: Na inserção da árvore-B*, é priorizado a redistribuição pelo split dois-três.
R: A principal diferença se dá pela implementação do split durante a operação
de inserção. Nas árvores B* o split é dado por “two-to-three split”, já nas
árvores B é por “One-to-two split”.
● Árvores B*: Uma página folha contém no mínimo (2m-1)/3 e no máximo
m-1 chaves.
● Árvores B; Uma página folha contém no mínimo m/2 -1 e, no máximo,
m-1 chaves.
A principal vantagem das árvores B* se dá pela melhor taxa de ocupação das
páginas proporcionadas pela redistribuição durante as operações, tornado
uma árvore com nível menor.
11. O que é uma árvore‐B virtual? Quais as vantagens e as desvantagens
da árvore‐B virtual?
R: É uma árvore onde algumas de suas páginas são mantidas carregadas na
memória RAM para melhorar a eficiência de acesso ao disco, geralmente
tendo o nó raiz sempre carregado na memória. Sua principal vantagem é o
acesso rápido aos dados, no entanto sua maior desvantagem se torna o maior
uso da memória RAM e o método de gerenciamento ao selecionar quais
páginas devem ou não serem mantidas previamente na memória.
12. O que é uma árvore‐B+? Quando ela é necessária?
R: Uma árvore-B+ é uma estrutura de dados do tipo árvore derivada das
árvores-B, porém com uma forma diferente de armazenamento de suas
chaves, onde as chaves são armazenadas nas folhas e as folhas são ligadas
umas às outras através de ponteiros, permitindo uma varredura sequencial
eficiente. Usamos uma árvore-B+ quando buscamos organizar um arquivo
de modo que seja eficiente para processamento sequencial de busca.
13. O que são separadores? Qual a diferença entre separadores e chaves?
R: São prefixos armazenados em índices, cada um de tamanho mínimo
variável, usados para distinguir entre os diferentes blocos de dados que estão
armazenados nas folhas. O que diferencia uma chave de um separador é que
a chave é o dado real, já o separador é somente um prefixo que indica um
caminho a uma determinada página folha procurada.
14. Para aplicações reais, juntamente com cada chave da árvore‐B é
armazenada uma referência para o registro do arquivo de dados que contém
os dados que são associados à chave (abordagem 1). Outra solução consiste
em, juntamente com cada chave da árvore‐B, armazenar o registro completo
de dados que contém os dados que são associados à chave (abordagem 2).
Compare essas duas abordagens em termos de vantagens e desvantagens.
R: Abordagem 1:
Vantagens:
- Melhor uso do espaço, visto que armazena apenas referências para os
registros, economizando espaço na árvore.
- Menor Overhead de Armazenamento, pois mantém os registros
separados das chaves, reduzindo o espaço ocupado pela estrutura da
árvore em si.
Desvantagens:
- Requer um acesso adicional ao disco, primeiro para obter a referência
do registro na árvore-B e depois para acessar o próprio registro no
arquivo de dados, aumentando o tempo de execução.
Abordagem 2:
Vantagens:
- Acesso direto ao disco, é possível acessar o registro completo sem
necessidade de buscar em outro local.
Desvantagens:
- Maior consumo do espaço, pois cada chave armazena o registro
completo, resultando em maior uso de espaço na árvore.
15. Em sala de aula, considerou‐se que os campos da árvore‐B que
armazenam as chaves de busca são campos de tamanho fixo (abordagem 1).
Entretanto, a árvore‐B pode ser implementada considerando campos de
tamanho variável para armazenar as chaves de busca (abordagem 2).
Compare essas duas abordagens em termos de vantagens e desvantagens.
R:Abordagem 1:
Vantagens:
- Acesso direto e mais rápido, visto que campos de tamanho fixo
estrutura da árvore-B são dados em posições previsíveis, otimizando
operações como busca e inserção.
Desvantagens:
- Possibilidade de desperdicio de espaço quando as chaves não ocupam
o tamanho fixo definido.
Abordagem 2: Campos de Tamanho Variável
Vantagens:
- Uso eficiente do espaço, pois cada chave ocupa apenas a quantidade
de memória necessária.
Desvantagens:
- Complexidade ao acessar, já que se torna necessário gerenciar o
tamanho das chaves e ajustar os ponteiros e índices conforme as
chaves variam.
16. Considere a seguinte trie de ordem (raio) 2, com ponteiros para buckets
com capacidade para abrigar 100 chaves (ou registros):
a. Desenhe a trie estendida e o diretório de endereços hash correspondente.
b. Considerando que os buckets A, B e C contêm, respectivamente, 100, 50 e
03 registros, dê a configuração do diretório, e a condição de cada bucket após
a inserção de uma nova chave cujo valor da função hash é 00.
c. Ainda na configuração inicial, considere agora que todas as chaves de B são
eliminadas. O que acontece com o diretório? R: Diminui o nível do diretório.
17. Considere um máximo de 3 elementos por bucket, e que a função hash
gera 4 bits para uma chave. Simule a inserção de chaves que geram os
seguintes endereços: 0000, 1000, 1001, 1010, 1100, 0001, 0100, 1111, 1011
br/images/7/72/Alg2_17.Hashing_Externo.pdf