Algoritmo de remoção no caso 4 na árvore B
No Caso 4, a remoção de uma chave faz com que uma folha fique com menos chaves do que o mínimo permitido e nenhuma página irmã pode ceder uma chave.
Quando isso ocorre, usamos a técnica de concatenação para corrigir a estrutura da árvore.
Note
A concatenação combina:
- As chaves de duas páginas irmãs (filhas do mesmo pai).
- A chave separadora do pai que divide essas páginas.
Essa união resulta em uma única página, eliminando uma das páginas filhas e reduzindo o número de filhos do pai.
Passo a Passo
1. Remover a chave
Identifique e remova a chave, verificando se a folha resultante viola o número mínimo de chaves.
2. Verificar as páginas irmãs
Confirme que nenhuma irmã pode ceder uma chave, pois todas estão no mínimo permitido.
3. Realizar a concatenação
Combine:
- As chaves da página que ficou com poucas chaves.
- As chaves da irmã diretamente adjacente (esquerda ou direita).
- A chave separadora do pai.
A página pai perde uma chave e um ponteiro para os filhos afetados.
4. Reestruturar o pai
Se o pai ficar com poucas chaves após a concatenação, os mesmos casos de redistribuição ou concatenação podem ser aplicados recursivamente ao nível superior.