Neste laboratório, você vai implementar inserção em um caso especial de árvores B que são as árvore 2-3, árvores B de ordem 3. Nesse caso, cada nó tem no mínimo uma chave e dois filhos (se não for folha) e no máximo duas chaves e três filhos.
Pegue o arquivo mapa.c que tem um esboço da implementação, com árvores rubro-negras, de nossa velha interface mapa.h.
Obs: Nessa implementação, estou abstraindo o valor mapeado pela chave. A representação do mapa contém apenas chaves e ponteiros para subárvores, e não os valores mapeados.
O programa teste.c tem um teste de inserção interativo. Para cada inserção, o programa compara o resultado da chamada a uma função cinsere, contendo a implementação correta da inserção, com o resultado da sua chamada. Para gerar o programa, vc terá que baixar os arquivos arvore.h, mapa.h, cmapa.h e cmapa.o, além do arquivo mapa.c, e escrever:
gcc -Wall cmapa.o mapa.c teste.c -o teste
Dedique-se a entender o esqueleto da inserção e o caso já implementado, comparando-o com os slides. O arquivo mapa.c já contém todas as funções auxiliares de troca de cores e de rotações necessárias.
obs: O campo pai será importante para retirada.