PO2024S2

Nas remoções em árvores B, há diversos casos a considerar. Em um deles, se uma folha tem uma chave removida e o número de chaves fica abaixo do mínimo permitido, pode-se proceder uma redistribuição das chaves entre outros procedimentos.

Ao optar por uma redistribuição, observa-se que a página que teve a chave removida pode receber chaves da sua folha irmã adjacente até alcançar o número mínimo de chaves permitidas em uma página.

Duas páginas P e Q são chamadas irmãs adjacentes se têm o mesmo pai W e são apontadas por 2 ponteiros adjacentes em W. Visualmente, páginas irmãs adjacentes são aqueles que estão “ao lado” um do outro na árvore e TEM o mesmo pai.

Considerando especificamente o caso da chave a ser removida estar em uma folha e o número de chaves ficar abaixo do mínimo permitido, tome k como a chave a remover e implemente conforme sugerido:

a)   uma função que retorne um ponteiro para a folha irmã adjacente da folha onde está a chave k que tenha o maior número de chaves. Se a folha com o maior número de chaves tiver somente o mínimo de chaves (ou seja, não pode perder chaves) a função deve retornar NULL. Se as duas folhas irmãs adjacentes tiverem o mesmo número de chaves (e que esse número permita a remoção), sempre use a folhar irmã da esquerda.

b)    uma função que dados a chave k a ser removida em uma folha, o ponteiro da folha, o ponteiro da folha irmã adjacente com possibilidade de perder chaves (se ela existir), remova a chave k e reorganize o que for necessário, redistribuindo as chaves restantes.

c)    Uma função com o objetivo de remover a chave k, que determine se k está numa folha e que chame as funções anteriores para concluir a remoção.

Considere:

• que esse caso de remoção nunca será feito na raiz (mesmo que ela seja uma folha), ou seja, você não precisa tratar isso nas suas funções.
• as folhas irmãs adjacentes de uma folha também são folhas

Exemplos práticos:

Considere a árvore B de ordem 5 a seguir:

Se o valor a ser removido for o 33, o nó irmão adjacente melhor candidato para perder chaves seria o [20 22 25 28], ou seja, nó irmão do nó [31 33] que tem o maior número de chaves.  Resultando na subárvore a seguir:

Se o valor a ser removido for o 90, o nó irmão adjacente melhor candidato para perder chaves seria o [93 94 95], ou seja, nó irmão do nó [90  91] que tem o maior número de chaves. Resultando na subárvore a seguir:

Se o valor a ser removido for o 60, tanto o nó [30  35] quanto o nó [88  92]  já estão no limite e não podem perder chaves, logo a função da letra a retorna NULL e a da letra b nem é chamada. Ou seja, a remoção não é feita.

Se o valor a ser removido for o 79, o nó [70  74] será o único candidato, mas já está com a quantidade mínima de chaves, logo a função da letra a retorna NULL e a da letra b nem é chamada. Ou u seja, a remoção não é feita.

ENTRADA

A primeira linha contém um valor N entre 3 e 100, representando a ordem da árvore B.

A segunda linha contém um valor K entre 1 e 105 e indica a chave que deve ser removida de uma folha.

A terceira linha contém uma sequencia de números entre 1 e 105 que finaliza em -1. Tal sequencia representa a ordem inserção na árvore B de ordem N.

SAIDA

Consiste de uma linha contendo todos números da árvore em ordem seguidos de espaço em branco e finalizada com \n após a realização da remoção da chave K (quando for possível).

EXEMPLO

Para facilitar, a árvore B inicial dos exemplos: