Árvore b+ hash
3498 palavras
14 páginas
Indexação e HashingResolução de exercícios
Camila Maione Danilo Soares Carneiro
Exercício 12.3
Exercício 12.3
Construa uma árvore B+ para o seguinte conjunto de valores de chave:
(2, 3, 5, 7, 11, 17, 19, 23, 29, 31)
Suponha que a árvore esteja inicialmente vazia e os valores sejam acrescentados em ordem crescente. Construa arvores B+ para os casos em que o número de ponteiros que caberão em um nó é o seguinte: a) Quatro b) Seis c) Oito
Exercício 12.3
N=4 Máximo de valores por nó = 3 Nó-folha: Mínimo de valores por nó = 2 Nó não-folha: Mínimo de filhos = 2 Máximo de filhos = 4
K1 p1 K2 p2 p3
K3 p4 2 3 5 7 11 17 19 23 29 31
Exercício 12.3
2
3 5 7 11 17 19 23 29 31 2
Exercício 12.3
5 7 11 17 19 23 29 31 2 3
Exercício 12.3
7 11 17 19 23 29 31
Exercício 12.3
2
3
5
11 17 19 23 29 31
Exercício 12.3
7 2 3 5
Não é possível inserir o valor 7 no nó, pois este se encontra cheio. Logo, é preciso dividir o nó.
11 17 19 23 29 31
Exercício 12.3
7 2 3 5
T=
2
3
5
7
2 5
3 7
p1 até Kn/2 p(n/2) + 1 até Kn
11 17 19 23 29 31
Exercício 12.3
5
2
3
5
7
Nova raiz criada. O valor 5 é propagado para a nova raiz.
17 19 23 29 31 5
Exercício 12.3
11 2 3 5 7
17 19 23 29 31 5
Exercício 12.3
2
3
5
7
11
19 23 29 31 5
Exercício 12.3
17 2 3 5 7 11
Não é possível inserir o valor 17 no nó, pois este se encontra cheio. Logo, é preciso dividir o nó.
19 23 29 31 5
Exercício 12.3
2
3
5
7
11
T=
5
7
11 17
5 11
7 17
p1 até Kn/2 p(n/2) + 1 até Kn
19 23 29 31 5 11
Exercício 12.3
2
3
5
7
11
17
O valor 11 é propagado para o próximo nível (raiz).
23 29 31
Exercício 12.3
5 11 19 2 3 5 7 11 17
23 29 31
Exercício 12.3
5 11
2
3
5
7
11
17 19
29 31
Exercício 12.3
5 11 23 2 3 5 7 11 17 19
29 31
Exercício 12.3
5 11