Método de Acesso Dinâmico: B-Tree - DeleçãoChaves de busca sem duplicatas

AULA 9Profa. Sandra de Amo

GBC053 – BCC2013-1

Deleção

Se ocupação não fica abaixo do mínimo, deleta, não altera ponteiros, nem nós ancestrais

Se ocupação fica abaixo do mínimo Tenta redistribuição com nó vizinho, se

possível Caso contrário junta com vizinho à direita

ou à esquerda (caso for o último nó).

Discussão

Redistribuição é vantajosa no caso de deleção:

Deixa mais espaço nos nós para futuras inserções (há muito mais inserções do que deleções na prática)

Redistribuição entre nós em um nível só é propagada para nós no nível acima.

Exemplo: Deleção

2* 3* 14*16* 19* 20*22* 24* 27* 29* 33*34* 39*38*

Removendo 19*

7* 8*5*

5 13 24 30

17

Deleção: Redistribuição nas folhas Com nó direito

Removendo 20*

5 13 24 30

17

2* 3* 14*16* 20* 22* 24* 27* 29* 33*34* 39*38*7* 8*5*

Deleção: Redistribuição nas folhas Com nó direito

Removendo 20*

5 13 27 30

17

2* 3* 14*16* 24* 27* 29* 33*34* 39*38*7* 8*5*

24

22*

Resumo:

Deleção da chave X na folha P P tem d elementos (ocupação mínima) Vizinho à direita VD tem d+1 elementos e pai(VD) = pai(P)

Remove X de P Obtém página P’ com d-1 elementos Transfere primeiro elemento Y de VD para última posição de P Seja Z = segundo elemento de VD Seja Pai = pai(VD) = pai(P)

Pti = ponteiro de Pai apontando para VD

Ki = chave em Pai antes de Pti

Substitui Ki por Z

Deleção: Redistribuição nas folhas Com nó esquerdo

Removendo 33*

5 13 30

17

2* 3* 14*16* 22* 24* 27* 29* 33*7* 8*5*

24

35*

Deleção: Redistribuição nas folhas Com nó esquerdo

Removendo 33*

5 13 30

17

2* 3* 14*16* 22* 24* 27*7* 8*5*

24

35*29*

29

Resumo:

Deleção da chave X na folha P P tem d elementos (ocupação mínima) Vizinho à direita VD tem d elementos ou pai(VD) ≠ pai(P) ou VD

não existe Vizinho à esquerda VE tem d+1 elementos e pai(VE) = pai(P)

Remove X de P Obtém página P’ com d-1 elementos Transfere último elemento Y de VE para primeira posição de P Seja Pai = pai(VE) = pai(P)

Pti = ponteiro de Pai apontando para P

Ki = chave em Pai antes de Pti

Substitui Ki por Y

Discussão

Distribuição nas folhas vizinhas não acarreta mudança - redução de ocupação dos nós pais

Portanto: Nós pais não ficam abaixo da ocupação mínima Não precisam ser juntados nem redistribuídos entre

seus vizinhos Não há redução da altura da árvore Modificações não se propagam para nós acima do nó-

pai

Deleção: Juntando FolhasCom nó à direita

2* 3* 14* 15* 22* 33*34* 39*38*

Removendo 24*

7* 8*5*

5 13 30

17

24*

27

27*29*22* 27* 29*

Não dá para redistribuir os vizinhosTamanho do vizinho direito = dVizinho à esquerda tem pai diferente

JUNTA COM O VIZINHO DA DIREITA

16*

40

Deleção: Juntando FolhasCom nó à direita

33*34* 39*38*

Removendo 24*

5 13 30

17

24*

27

27*22* 27* 29*

27

Quase vazia ! Não dá para distribuircom vizinho

30

2* 3* 14* 15*7* 8*5* 16*

17 40

Junção de nós intermediários

2* 3* 14* 16* 33*34* 39*38*7* 8*5*

30

24*

27

27*22* 27* 29*

305 13 30 3027305 13 30

Removendo 24* 1717 40

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 14* 16* 49*50*

Removendo 16*

7*5*

5 13 60

45

45*46*

47

63* 65*

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 14* 16* 49*50*

Removendo 16*

7*5*

5 13 60

45

45*46*

47

63* 65*

Só pode ser a última chave deste nó

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 14* 49*50*

Removendo 16*

7*5*

5 13 60

45

45*46*

47

63* 65*

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 49*50*

Removendo 16*

7*5*

5 13 60

45

45*46*

47

63* 65*7* 14*5*

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 49*50*

Removendo 16*

7*5*

5 60

45

45*46*

47

63* 65*14*

Devem ser juntadas

Deleção: Juntando FolhasCom nó à esquerda

2* 3* 49*50*

Removendo 16*

7*5*

5

45

45*46* 63* 65*14*

47 60

Redistribuição em nós intermediários

13 1755 13 27 30

22

17 20

2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 24* 29*27* 33* 34* 38* 39*

Removendo 24* : Existe possibilidade de juntar nós intermediários

Redistribuição em nós intermediários

13 1755 13 30

22

17 20

2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 29*27* 33* 34* 38* 39*

Quase vazia

Redistribuição em nós intermediários

13 1755 13 30

22

17 20

2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 29*27* 33* 34* 38* 39*

Redistribuição em nós intermediários

13 1755 13 13 17520 3017

22

3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 29*27* 33* 34* 38* 39*

Exercícios

Escrever algoritmo Junta(Folha1,FolhaD)

Escrever algoritmo Junta(Folha1,FolhaE)

Escrever algoritmo Distribui(No1,NoD)

Escrever algoritmo Distribui(No1,NoE)

Exercicio: Remove 16*

13 1755 13 27 30

22

17 20

2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 24* 29*27* 33* 34* 38* 39*

50

Exercicio: Remove 18*

13 1755 13 27 30

22

17 20

2* 3* 5* 7* 8* 14*16* 17* 18* 20* 21* 22* 24* 29*27* 33* 34* 38* 39*

50

Exercicio: Remove 34*

13 1755 13 27 30

22

2* 3* 5* 7* 8* 14*16* 22* 24* 29*27* 33* 34*

50

Exercicio: Remove 22*

13 1755 13 27 30

22

2* 3* 5* 7* 8* 14*16* 22* 24* 29*27* 33* 34*

50

Exercicios

Construir algoritmos para: Juntar nó com nó-irmão da direita Juntar nó com nó-irmão da esquerda Distribuir nó intermediário com nó-irmão da

direita Distribuir nó intermediário com nó-irmão da

esquerda