INF1010 - Árvores Binárias de Busca

entrega até sabado, 30/3, às 23h

Vamos retomar a implementação de mapa.h e arvore.h com árvores binárias de busca que começamos semana passada. Por favor baixe novamente esses arquivos pois há algumas mudanças neles. (Lembrando que mapa.h é a interface to tipo abstrato mapa, e a arvore.h uma interface para a estrutura de dados árvore, ambas implementadas pelo arquivo mapa.c.) Uma implementação com a função insere completa está em mapa.c (se a sua própria implementação estiver funcionando pode usá-la também.)

Os testes são sugestões. Pense em situações específicas ou outras sequencias que seriam interessantes de verificar.

1. Use o arquivo teste.c como base para seus testes. Compile o programa, execute-o, e veja que está entendendo as árvores geradas.

2. [3 pontos] 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 tammapa. Sua estrutura de medição deve ficar algo como:

     // tempo inicial
     tdec1 = ...
   
     AQUI PROCESSAMENTO CUJO TEMPO QUERO MEDIR
   
     //pega contagem de recursos final
     tdec2 = ...;
     // calcula e mostra tempo 
     printf ("tempo: %f\n", 
             ((double) (tdec2-tdec1)) /CLOCKS_PER_SEC);
   

   Force a busca de valores próximos das folhas, procurando os valores (tammapa-1) e (tammapa). MOSTRE e EXPLIQUE seus resultados. (Se fizer esta parte em casa, por favor relate em que máquina você executou os testes.) 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 tammapa, como 1000, 10000, 20000, ... Execute seus testes algumas vezes (por exemplo, 3) para cenário, para evitar variações do ambientes.
3. [5 pontos] Implemente a remoção (função retira). Uma sugestã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.
   • Use 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.)
4. [2 pontos] Escreva uma função que determine se uma árvore binária é ou não uma árvore binária de busca, isto é, se as chaves estão em ordem crescente. Suponha que as chaves são sempre não negativas, como fizemos até aqui.

   int e_abb (Mapa *m);
   

   obs 1: Provavelmente vc precisará de uma função "interna" com mais um parâmetro, deixando a e_abb como o que chamamos de "casca". Esse parâmetro pode ser de entrada e saída, por exemplo contendo a maior chave vista até agora.

   obs 2: Para conseguir testar sua função, crie uma auxiliar

   Mapa* debug_troca_chave (Mapa *m, int original, int novachave);
   

   que "corrompe" a árvore substituindo a chave original pela chave passada.

   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.