Algoritmo de remoção no caso 2 na árvore B
No Caso 2, o elemento a ser removido não está em uma folha, ou seja, ele está em uma página interna (nó).
Nesse cenário, é necessário preservar a estrutura ordenada da árvore, e isso é feito substituindo o elemento pelo seu predecessor ou sucessor.
Note
O predecessor de uma chave é o maior valor menor que ela dentro da árvore. Ele é encontrado na folha mais à direita do subárvore esquerda do elemento a ser removido.
Passo a Passo
1. Localizar o elemento a ser removido
Vamos remover a raiz 90.
2. Substituí-lo pelo seu predecessor
Encontre o predecessor da chave:
- Vá para a subárvore à esquerda do elemento.
- Navegue até a folha mais à direita dessa subárvore.
Substitua a chave pelo predecessor.
3. Remover o predecessor da folha
O predecessor estará em uma folha.
Após removê-lo da folha, trate o Caso 1:
- Se a folha ainda atender ao número mínimo de chaves, o processo termina.
- Caso contrário, redistribua ou faça ajustes (se necessário).
Exemplo - Ordem
Vamos remover a chave 90, que está na raiz (nó interno).
Localizar o predecessor de 90: O predecessor de 90 é o 85, que está na folha à direita da subárvore esquerda:
Substituir 90 pelo predecessor (85): A chave 90 é substituída por 85:
Remover o predecessor da folha: Agora, remova o 85 da folha onde ele estava:
Após a remoção, a folha ainda tem 2 chaves, atendendo ao mínimo (