Usando árvores binárias de busca, vamos completar um módulo com as interface dadas em mapa.h e arvore.h. (A primeira é a interface to tipo abstrato mapa, e a segunda uma interface para a estrutura de dados árvore.) Um esboço dessa implementação está em mapa.c.
Repare que trocamos os dados indicados em sala de aula (onde cada nó da árvore "apontava" para um bloco de dados) por um simples inteiro. O objetivo aqui é só simplificar o tratamento desses dados em nosso exercício. A operação busca agora retorna um int. Para indicar que o item não foi encontrado, estamos retornando o valor INT_MIN (para definir essa constante, precisamos incluir o arquivo limits.h.
Use o arquivo teste.c como base para seus testes. Você deve passar o tamanho do mapa com argumento na linha de comando. Este programa teste cria 2 mapas. No primeiro a inserção é feita em ordem crescente dos elementos e no segundo eu usei uma função preenche que procura inserir de forma balanceada. Antes de implementar, desenhe no papel o que você prevê como árvore resultante para os dois mapas, usando o tamanho 5 e fazendo o chinês da função preenche.
Implemente a função de inserção. Use o programa teste com diferentes tamanhos para ver se a busca consegue encontrar todos os elementos que deveria (alguns não devem ser encontrados! veja quais!).
Implemente a função mostra, da interface arvore.h. Essa função deve varrer a árvore e mostrar como ela está implementada, usando a notação de parênteses para sub-árvores. Como exemplo, para outromapa com tamanho 5, a função mostra deve mostrar a cadeia (2 (0 ()(1 ()()))(3 ()(4 ()()))).
(para quem acabar tudo) Depois de se certificar que suas operações estão funcionando corretamente, vamos medir o tempo de criar árvores com essas duas estruturas. Use a função clock (use man clock na linha de comando linux, mas também procure no google...). Utilize essa função para medir o tempo de construção de cada uma das árvores para diferentes valores de TAM. Force a busca de valores próximos das folhas, procurando valores como (TAM-1) e (TAM+1). ATENÇÃO: Não coloque chamadas a printf ou outras fçs de entrada e saída "dentro" do trecho cujo tempo de execução estiver medindo. Para ver resultados interessantes, use valores bem variados de TAM, como 1000, 10000, 20000, ... Execute seus testes algumas vezes (por exemplo, 3) para cenário, para evitar variações do ambientes.
Mapa* remove (Mapa* m, int chave);
Para fazer a remoção, crie primeiro uma função auxiliar que retorna
um ponteiro para o menor elemento em uma árvore.
Use essa função auxiliar quando o nó que se deseja remover
tiver dois filhos.
(Nesse caso, vc pode usar a função auxiliar para encontrar o nó de menor
chave na subárvore à direita, trocar a chave e o dado do nó a ser
removido com o do nó localizado, e depois mandar remover o nó com valor
indesejado da subárvore à direita.)
Faça upload dos seus arquivos mapa.c e teste.c no ead. Lembre-se de fazer a entrega mesmo que não tenha chegado ao final do exercício.