Resposta Lista 4 - EDD2 Profª Vânia

Prévia do material em texto

Grupo 1 - Paulo Henrique, Alan Leones, Gabriel Nogueira e Jonathan Santos. 
 
1 - ​Quando se insere uma chave numa árvore B, ela é colocada sempre numa folha 
e por meio de split promote cria-se um nó pai, a árvore fica sempre balanceada. 
Numa árvore binária a inserção começa pela raiz e então as folhas são criadas, 
pode ser que, ao inserir uma chave, a árvore não fique balanceada. Então será 
necessário fazer algoritmos para fazer as operações que garantam que a árvore 
fique sempre balanceada. Os nós podem ser inseridos em qualquer posição. 
 
2) Começando da página raiz, verifica-se se a primeira chave(chave extrema 
esquerda) tem filho a esquerda, se não tiver página filha a esquerda, a menor chave 
será a chave atual. 
Se tiver página filha a esquerda, a menor chave será a primeira chave (chave 
extrema esquerda) da página filha à esquerda da chave atual e repete-se a primeira 
verificação até encontrar uma chave extrema esquerda que não possui filhos à 
esquerda dela. 
 
3) As folhas, diferente dos nós internos, não possuem apontadores para páginas 
filhas. 
As folhas devem conter um número mínimo de chaves = ⌈d/2⌉-1 e máximo de 
chaves = d-1; Não possuir apontadores para páginas filhas. 
 
4) 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. 
5) Inserção: 
 
 
Remoção: 
 
 
 
 
6 - a) Todas páginas já tenham o máximo de filhos ocupados e o máximo de chaves 
ocupadas. 
 b) Quando todas as páginas tiverem o seu número mínimo de filhos e cada 
página tenha um número mínimo de nós, tal que a remoção cause um underflow. 
 c) Caso a chave seja a última da página não-folha, obrigatoriamente o seu 
sucessor está em um nó filho. 
Caso não seja a última chave (posição n), temos entre a chave Sn e a chave Sn+1 
um ponteiro apontando para a página filha, que contém valores num intervalo (Sn, 
Sn+1) e, portanto, contém o sucessor de Sn. 
 
 
 d) O(log (n)) 
 
7 - a) Começa-se pela chave 5 e soma-se 3 sucessivamente, logo {5,8,11,14,17…} 
5+3i, i>=0; 
 
 b) 5, 17, 47… 
 
 c) 1, 4, 7, 10, 13… e assim soma-se 3 sucessivamente. 1+3i; 
 
 d) 1, 7, 13, 19… e assim soma-se 6 sucessivamente. 1+6i; 
 
8)
 
 
9)
 
 
 
10) 
a)Nas árvores b* a operação de split só ocorre quando duas páginas irmãs estão 
completamente cheias, nas árvores b a operação de split ocorre quando há uma página 
completamente cheia. 
b)A grande vantagem é o melhor aproveitamento de espaço do arquivo, já que cada página 
apresenta no ​mínimo 2/3 do número máximo de chaves que esta pode armazenar. 
c)Deve-se tomar um cuidado especial com o nó raiz e para ele usar one-to-two spliting 
(algoritmos mais complexos) 
d)Como a árvore b* tem no mínimo ⅔ das chaves, ela vai ter uma altura mínima menor que a da 
árvore B.