Inserção e Remoção na Árvore B

Prévia do material em texto

Inserção e Remoção na 
Árvore B
Inserção
29
8 15
1 3 4 7 10 12 13 14 18 20 25
37 45 60
30 35 40 41 42 43 70 77 8351 52
Inserção
Inserindo o número 11
29
8 15
1 3 4 7 10 12 13 14 18 20 25
37 45 60
30 35 40 41 42 43 70 77 8351 52
11
Como o 11 não cabe na página devemos dividir a página
Inserção
Inserindo o número 11
29
8 15
1 3 4 7 10 12 13 14 18 20 25
37 45 60
30 35 40 41 42 43 70 77 8351 52
11
Agora promovemos o maior número da página onde ocorre a
inserção, nesse caso é o 12
Inserção
Inserindo o número 11
29
8 15
1 3 4 7 10 11 12 18 20 25
37 45 60
30 35 40 41 42 43 70 77 8351 5213 14
Resultado
29
8 12 15
1 3 4 7 10 11 18 20 25
37 45 60
30 35 40 41 42 43 70 77 8351 5213 14
Inserção
Inserindo o número 11
Agora associamos a nova página criada com a chave promovida
29
8 12 15
1 3 4 7 10 11 18 20 25
37 45 60
30 35 40 41 42 43 70 77 8351 5213 14
Imagine essa situação onde queremos inserir o número 13
Inserção
Inserindo o número 13
8 15
1 3 4 7 10 11 12 14 18 20 25
13
Dividimos a página e inserimos a nova chave na nova página criada
8 15
1 3 4 7 10 11 18 20 2512 13 14
Nesse caso a primeira chave da nova página é quem deve ser promovida
8 12 15
1 3 4 7 10 11 18 20 2513 14
Inserção
Inserindo o número 13
Agora associamos a nova página criada com a chave promovida 
8 12 15
1 3 4 7 10 11 18 20 2513 14
Inserção
Inserindo o número 13
Remoção
29
8 15
1 3 4 7 10 12 13 14 18 20 25
37 45 60
30 35 40 41 42 70 77 8350 52
Caso 1: Se o elemento estiver em uma folha e a folha mantiver 50% de 
ocupação, basta removê-lo
Ex.: Remoção da chave 13
Remoção
Resultado
29
8 15
1 3 4 7 10 12 13 14 18 20 25
37 45 60
30 35 40 41 42 70 77 8350 52
29
8 15
1 3 4 7 10 12 14 18 20 25
37 45 60
30 35 40 41 42 70 77 8350 52
Remoção
Caso 2: Se o elemento não estiver em uma folha, trocá-lo pelo seu 
antecessor
Ex.: Remoção da chave 29
Resultado
29
8 15
1 3 4 7 10 12 13 14 18 20 25
37 45 60
30 35 40 41 42 70 77 8350 52
Antecessor
25
8 15
1 3 4 7 10 12 13 14 18 20
37 45 60
30 35 40 41 42 70 77 8350 52
Caso 2: Se o elemento não estiver em uma folha, trocá-lo pelo seu 
antecessor
Ex.: Remoção da chave 15
Remoção
Resultado
29
8 14
1 3 4 7 10 12 13 18 20 25
37 45 60
30 35 40 41 42 70 77 8350 52
29
8 15
1 3 4 7 10 12 13 14 18 20 25
37 45 60
30 35 40 41 42 70 77 8350 52
Antecessor
Caso 3: Se a folha ficar com menos de 50% de ocupação, mas a página irmã 
puder ceder uma chave
Ex.: Remoção da chave 35
Remoção
Resultado
29
8 15
1 3 4 7 10 12 13 14 18 20 25
37 45 60
30 35 40 41 42 70 77 8350 52
A ser 
cedido
29
8 15
1 3 4 7 10 12 13 14 18 20 25
40 45 60
30 37 41 42 70 77 8350 52
Caso 4: Se a folha ficar com menos de 50% de ocupação e as páginas irmãs não puderem 
ceder uma chave
Ex.: Remoção da chave 42
Remoção
29
8 15
1 3 4 7 10 12 13 14 18 20 25
40 45 60
30 37 41 42 70 77 8350 52
29
8 15
1 3 4 7 10 12 13 14 18 20 25
40 60
30 37 70 77 8341 45 50 52
Resultado
Download
https://pt.scribd.com/document/381959018/Insercao-e-
Remocao-Na-Arvore-B