Remoção de uma chave em uma árvore B

Seja s a chave a ser removida.
Inicialmente. fazemos a busca da chave s na árvore B.
Se s não for encontrada, nada a fazer ( pois nesse caso a remoção seria inválida)
Se s for encontrada numa folha, remova-a
Se s for encontrada numa página não-folha, remova-a e coloque no seu lugar a chave x imediatamente maior que s ( x sempre se encontra numa folha ).
A remoção se restringe portanto sempre a uma página folha.

Sa a página-folha P onde foi realizada a remoção ficou com menos do que d chaves, é preciso fazer concatenação ou redistribuição.

Vejamos em que casos aplicamos concatenação ou redistribuição.

Concatenação - Mas a raiz não tem de ter no mínimo 2 filhos.

Redistribuição;

Toda remoção restringe-se no caso de P folha.

	Created by Jorge Borges almost 6 years ago

Árvores B - Conceituação e manipulação