INF1010 - Árvores Rubro-Negras

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 caso deve ser tratado. Utilize essa árvore rubro-negra online para testar manualmente 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:

typedef struct smapa Mapa;

Mapa* cria (void);
Mapa* insere (Mapa* m, int chave, int novodado);
int busca (Mapa *m, int chave);
void destroi (Mapa *m);

void debug_mostra_mapa (Mapa *m);

O programa teste.c tem um teste de inserção que deve funcionar com este esqueleto, apesar dos warnings. Ele funciona porque as inserções são sempre feitas à esquerda do nó mais à esquerda de toda a árvore, e este é o único caso que está sendo tratado em nosso esqueleto (chamado de caso LEFTRED, dentro da função corrigeEsq.

1. Execute o programa de teste para diferentes valores de TAM e verifique a árvore gerada.
2. 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.
3. 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!
4. Crie inserções em uma ordem que cubra todas as situações. (Por favor entregue o arquivo mapa.c, o arquivo teste.c, e copie e cole para a área de texto os resultados que vc obteve com o arquivo de teste entregue.)