INF1010 - Árvores Rubro-Negras

entrega até sabado, 20/4, às 23h

Neste laboratório, vamos tratar da implementação da inserção em árvores rubro-negras. Consulte os slides disponíveis sobre o assunto para ver a descrição de como cada caso deve ser tratado. Utilize essa árvore rubro-negra online para visualizar as correções sugeridas pelos slides.

Pegue o arquivo mapa.c que tem um esboço da implementação, com árvores rubro-negras, de nossa velha interface mapa.h.

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

1. 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.
2. Complete a implementação das funções corrigeDir e corrigeEsq. Lembre-se que em alguns casos será necessária uma rotação dupla, exatamente como a que aprendemos para a árvore AVL!

   obs: Teste seu programa aos poucos! Trate um determinado caso e tente verificar se o programa funciona para aquele caso! (Por favor entregue o arquivo mapa.c, o arquivo teste.c caso o modifique, e copie e cole para a área de texto os resultados que vc obteve com o arquivo de teste entregue.)