Lista-rvore_B_Filipe_Macedo docx_1

Prévia do material em texto

Fundação Universidade Federal de Rondônia 
Estrutura de Dados II – Atividade de 12/08/2016 – 
Estudo Dirigido – Árvores B – Parte I – árvores de busca paginadas 
Entregar dia 16/08/2016 
FILIPE MACEDO 
Leia o material enviado por e-mail e responda às questões seguintes. 
1. Quando não é possível utilizar pesquisa binária em disco? Por quê? 
R: 
● arquivo muito grande e não cabe na memória RAM (cada busca exige vários 
acessos lentos ao disco) 
● Os dados estão desordenados ou sofrem muitas atualizações (manter a ordem 
exige reorganização constante) 
● Precisamos de desempenho rápido para buscas em bancos de dados reais 
 
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? 
R: 
● Minimizar os acessos ao disco (3-4 no máximo) 
 
● Manter-se organizado automaticamente sem precisar reordenar tudo 
 
● Crescer junto com os dados sem perder performance 
 
● Agrupar informações em blocos que o disco lê de uma só vez 
 
3. Quais são as vantagens de se usar Árvores Binárias de Busca (ABBs)? Qual é o 
problema desta abordagem? 
R: 
 Vantagens: 
● Fáceis de implementar 
● Rápidas quando balanceadas 
● Boas para memória RAM 
 
Problema principal: 
● Podem desbalancear facilmente, virando uma "lista ligada" lenta. 
 
4. Quais seriam as vantagens e as desvantagens em se usar árvores-AVL? 
R: 
Vantagens: 
● Balanceamento garantido (altura limitada a 1.44*log₂(n+2)). 
● Operações de busca, inserção e remoção em O(log n). 
 
Desvantagens: 
● Rotações frequentes aumentam a complexidade de inserções/remoções. 
● Ainda requerem muitos acessos a disco (Slide 14, Parte Ia: "28 seeks 
inaceitáveis"). 
 
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? 
R: 
Conceito: 
● Cada nó corresponde a uma página de disco contendo múltiplas chaves 
● Combina busca binária com transferência eficiente de blocos de dados. 
 
Vantagens: 
● Reduz acessos a disco 
● Reduz drasticamente os acessos (de 20 para apenas 3 em alguns casos). 
● Aproveita leitura sequencial de páginas. 
 
Desvantagens: 
● Complexidade na construção/manutenção (Mais trabalhosas para manter 
atualizadas.). 
● Overhead de gerenciamento de páginas. 
 
Construção: 
● Top-down: Ordenação prévia e inserção balanceada . 
● Dinâmica: Balanceamento por rotações (similar a AVL) dentro das páginas. 
● Ordenar tudo antes (mais simples) 
● Ajustar dinamicamente (mais complexo, mas flexível). 
 
 
 
6. Descreva as características de uma Árvore B, considerando, ideia geral, construção, 
características do nó e sua estrutura lógica. 
R: 
Como uma árvore genealógica organizada: 
Cada pessoa (nó) pode ter vários filhos (não apenas 2) 
Todos os "primos" estão no mesmo nível 
A árvore cresce de baixo para cima 
 
Ideia geral: 
Generalização de ABBs paginadas, com nós não-binários e construção bottom-up 
 
Construção: 
Inserções começam nas folhas; splits propagam-se para a raiz. 
 
Estrutura do nó: 
Contém até m-1 chaves ordenadas e m ponteiros . 
Folhas estão no mesmo nível . 
 
Propriedades : 
Nós não folhas com k ponteiros têm k-1 chaves. 
Mínimo de ⌈m/2⌉ filhos (exceto raiz) 
 
 
7. Descreva como ocorre a inserção de nós em uma Árvore B. 
R: 
1. Sempre inserir nas folhas. 
2. Se o nó estiver cheio: 
● Divida ao meio. 
● Promova a chave central para o pai. 
3. Se o pai também estiver cheio: propague o split até a raiz. 
A árvore cresce de baixo para cima e sempre mantém o balanceamento, garantindo 
buscas rápidas. 
 
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 
R: