INF1010 - Árvores 2-3

entrega: até SEXTA, dia 27/9, às 23h

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 2-3, de nossa velha interface mapa.h.

Obs: Nessa implementação, vamos abstrair 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.

1. (6 pontos) Termine a implementação da inserção, completando os trechos indicados.

   obs: O campo pai será importante para retirada.

2. (1 ponto) Copie e cole a saída do teste final realizado na área de texto da tarefa, mostrando que seguiu todos os casos possíveis.
3. (3 pontos) Implemente a função de busca. Retorne apenas a indicação se encontrou (1) ou não (0) o elemento procurado.

   Altere o programa de teste para realizar testes da função de busca. Lembre-se de testar chaves em níveis diferentes, e chaves inexistentes.

Entregue os arquivos mapa.c e teste.c, e na área de texto da tarefa indique se você completou e testou todas as funções (se não, quais você implementou). Não esqueça de também copiar e colar a saída do teste final, pedida no item 2.