INF1010 - Árvores Rubro-Negras

Entrega até sabado, 14/9, à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, da nossa interface mapa.h.

O programa teste.c tem um teste interativo de inserção. 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 dos arquivo mapa.c e teste.c, e escrever:

gcc -Wall cmapa.o mapa.c teste.c -o teste

1. Dedique-se a entender o esqueleto da inserção e os casos já implementados (para correções após uma inserção à esquerda, mas apenas alguns), 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 corrigeEsq, e depois corrigeDir. 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 exemplo, ao completar a corrigeEsq, seu programa já deve funcionar se você inserir chaves descrescentes...

Entregue o arquivo mapa.c, o arquivo teste.c (caso o modifique), e copie e cole para a área de texto da tarefa os resultados que vc obteve com o arquivo de teste.