Lista 3 - Estrutura de dados II

Prévia do material em texto

Universidade Federal de Rondônia 
Departamento Acadêmico de Ciência da Computação 
Estrutura de Dados II 
Lista 4 – Árvores B e variações e Hashing 
 
Alunos: Aden Hercules Pinto de Azevedo e André Luis Mendes Ferreira 
 
PARTE I – Leia o material da aula e responda: 
1. Quando não é possível utilizar pesquisa binária em disco? Por quê? 
Quando o índice é grande não cabe na memória principal. Aumenta muito o número 
de acessos a disco. 
2. Quais são as características de um método desejável para que seja possível realizar 
busca em um índice com uma grande quantidade de dados? 
Método com inserção e eliminação com apenas efeitos locais, isto é que não exige 
reorganização total do índice. 
3. Quais são as vantagens de se usar Árvores Binárias de Busca (ABBs)? Qual é o 
problema desta abordagem? 
Ordem lógica dada por ponteiros esq e dir e registros não precisam estar fisicamente 
ordenados, a desvantagens é o número de seeks que vai ter quer fazer, pôs a árvore ficara 
desbalanceada inserindo em ordem alfabética. 
4. Quais seriam as vantagens e as desvantagens em se usar árvores‐AVL? 
Vantagens: Garantem eficiência e dispensam a ordenação de registros. 
Desvantagens: Se as chaves estão em memoria secundaria ainda tem muitos acessos. 
5. Do que se trata a solução por Árvores Binárias Paginadas? Quais são suas vantagens e 
desvantagens (preço a pagar...)? Como é realizada sua construção? 
Árvores Binárias Paginadas os registros serão agrupados em blocos que vão ser 
chamados de páginas, podendo assim acessar aos dados sequencialmente. Vantagens: Reduz 
o número de acessos já que só precisa de uma seeks pra verificar todos os registros que estão 
em uma página, porém tem maior tempo de transmissão de dados e necessários manter a 
organização da árvore, sua construção é top‐down da raiz pras folhas. 
 
6. Descreva as características de uma Árvore B, considerando, ideia geral, construção, 
características do nó e sua estrutura lógica. 
Características: Completamente balanceadas, construção bottom‐up( em disco), tem 
um número máximo de ponteiros é igual ao número máximo de descendentes de um nó, 
construção da árvore a partir de seus nós folhas até o nó raiz assim deixando a árvore 
balanceada, o nó é uma página no disco. 
 
7. Descreva como ocorre a inserção de nós em uma Árvore B. 
Verifica se a árvore está vazia se estiver vazia cria uma página, Verifica se é um nó 
folha e tiver espaço você apenas insere, se não tiver espaço tem que fazer uma divisão e insere 
no nó raiz se também não tiver espaço tem que fazer as quebras para aumentar os níveis. 
 
8. Insira as seguintes chaves em um índice Árvore‐B, na qual a ordem da árvore‐B é 4, em 
cada nó (página de disco) possui 3 chaves e 4 ponteiros: C S D T A M P I B W N G U R K. 
 
 
Inserir C,S,D
0
C D S
Inserir
2 2
S
0 1 0 1
C D T A C D T
2
D S
0 1
A C M T
Inserir M
2
D S
0 1
A E C I M P T U W
Inserir N
2
D N S
0 1 4 1
A B C G T M P R T U W
Inserir K
F
N
1 6
D R 5 M
0 3 5 4 2
A R G G I M P R T U w
 
 
PARTE II – Exercícios de fixação 
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? 
 
 
BYDE 
 
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? 
 
Pesquisa binária exige muitos acessos a disco; manter em disco um índice ordenado para 
busca binária tem custo proibitivo; inserir ou eliminar, mantendo o arquivo ordenado custa 
muito caro. 
 
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? 
 
 
 
 
 
Efeito: nós‐folha só ficarão com um elemento. Sim, a árvore degenerou. 
 
 
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? Redistribuição (para correção de underflow devido a eliminação). 
Inserção por redistribuição: Essa estratégia resulta em uma melhor utilização do espaço já 
alocado para a árvore. 
Remoção por redistribuição: redistribuição pode provocar uma alteração na chave separadora 
que está no nó pai 
Procurar uma página irmã (i.e., que possui o mesmo pai) adjacente que contenha mais chaves 
do que o mínimo 
 – se encontrou 
• redistribuir as chaves entre as páginas 
• reacomodar a chave separadora, modificando o conteúdo do nó pai 
 
 
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ê? 
 Redistribuição, porque se fosse utilizada a concatenação, poderia haver underflow da 
página pai e teria que ser feita outra concatenação. Com redistribuição isso não ocorre, pois há 
apenas uma troca de uma folha para outra. 
 
10. Qual a diferença entre uma árvore‐B e uma árvore‐B*? Quais as vantagens e as 
desvantagens da árvore‐B*? 
Uma árvore B* utiliza two‐to‐ three spliting, ou seja, o processo de divisão é adiado até 
que duas páginas irmãs estejam cheias. Realiza‐se então a divisão do conte údo das duas 
páginas em 3. Em árvore B, utiliza‐se one‐to‐two spliting onde uma folha cheia é dividida em 
duas. 
Vantagem: cada página tem no mínimo 2/3 das chaves (menos a fragmentação 
interna). 
Desvantagem: deve‐se tomar um cuidado especial com o nó raiz e para ele usar one‐
to‐ two spliting (algoritmos mais complexos). Como B* tem no mínimo 2/3 das chaves, ela vai 
ter uma altura m ínima menor que a árvore B. 
 
 
11. O que é uma árvore‐B virtual? Quais as vantagens e as desvantagens da árvore‐B virtual? 
Árvore que mantemos na memória. É a tentativa de manter o máximo de folhas na 
RAM. Quando se coloca parte da árvore B na memória. Coloca‐se a raiz e alguns de seus 
descendentes na memória, deixando algum espaço para manipular as páginas. 
Vantagens: Quando se procura uma chave, pode ser que ela j á esteja na memória o 
que diminui em um acesso ao disco. 
Desvantagens: Pode‐se deixar na memória páginas que não estão sendo usadas nunca. 
É necessário substituí‐las. 
12. O que é uma árvore‐B+? Quando ela é necessária? 
As árvores B+ possuem seus dados armazenados somente em seus nós folha e, seus 
nós internos e raiz, são apenas referências para as chaves que estão em nós folha. Assim é 
possível manter ponteiros em seus nós folha para um acesso sequencial ordenado das chaves 
contidas no arquivo. 
Pra que serve? Organizar um arquivo de modo que seja eficiente tanto para processamento 
sequencial quanto aleatório. 
 
13. O que são separadores? Qual a diferença entre separadores e chaves? 
Separadores são prefixos de chaves, ou seja, uma parte pequena da chave. 
Diferença: separadores são mantidos no índice, ao invés das chaves de busca, e possuem 
tamanho variável. As chaves estão apenas nas páginas folhas e são organizadas como árvore‐B. 
 
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 dadosque contém os dados que são associados à chave 
(abordagem 2). Compare essas duas abordagens em termos de vantagens e desvantagens. 
 
Primeira abordagem Vantagem: Consegue carregar mais dados para a memória e 
diminui os acessos ao disco. Desvantagem: É necessário fazer um seek a mais. 
https://pt.wikipedia.org/wiki/%C3%81rvores_B%2B
Segunda abordagem Vantagem: Não precisa fazer seek, pois o dado já vai estar lá. 
Desvantagem: A gente consegue carregar menos dados para a memória, e mais acessos ao 
disco seriam necessários. 
 
 
 
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. 
 
Abordagem 1 
Vantagem: Trabalha com chave de campo de tamanho variável, ocupa só a quantidade 
de byte necessário, reduz o tamanho de ocupação, e consegue carregar mais dados para a 
memória. 
Desvantagem: Fragmentação interna. Abordagem 2 Vantagem: Evita fragmentação 
interna. 
Desvantagem: Utilizar delimitadores, temos que fazer conversão; fragmentação externa. 
 
 
	Lista3_aden-andre
	questao 8 lista 3
	Lista3_aden-andre