INF1010 - Árvores Binárias de Busca

Entrega até sabado, 31/8, à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 do tipo abstrato mapa, e 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

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

Use o arquivo teste.c como base para seus testes. Compile o programa e execute-o. O programa agora recebe um argumento: o tamanho de duas árvores a serem geradas.
Repare que, em função da ordem de inserção de nós usada para cada árvore, a primeira árvore resultará desbalanceada (na verdade, será uma árvore degenerada), e a segunda resultará balanceada.
[3 pontos] Vamos medir o tempo de busca nessas duas estruturas. Para isso, modificaremos o arquivo teste.c. Use a função clock (digite man clock na linha de comando linux, mas você também pode procurar no google...). Utilize essa função para medir o tempo de busca de elementos em cada uma das duas árvores, para diferentes valores de tamanho. Sua estrutura de medição deve ficar algo como:
```
  // tempo inicial
  tdec1 = ...

  // busca elementos na árvore

  // tempo final
  tdec2 = ...;

  // calcula e mostra tempo total
  printf ("tempo: %f segundos\n", 
          ((double) (tdec2-tdec1)) /CLOCKS_PER_SEC);
```
(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 tamanho da árvore, como 1000, 10000, 20000, ... Execute seus testes algumas vezes (por exemplo, 3) para cada cenário, para evitar ruídos de variações do ambiente. Para esses valores grandes, pode ser melhor não exibir as árvores...
Relate na área de texto da tarefa os testes executados e os tempos obtidos. Comente os resultados do seu teste.
[1,5 pontos] Definimos como altura de uma árvore o maior nível dentre todos os seus nós (o que equivale ao comprimento do caminho mais longo da raiz até uma folha).Por sua vez, definimos que:
- a raiz de uma árvore tem nível 0
- se um nó tem nível n, seus filhos tem nível n+1
Com base nessa definição, implemente a função altura da interface arvore.h. Assuma que uma árvore vazia tem altura -1
Modifique o programa de teste, incluindo testes para sua função altura (use as duas árvores que o programa cria, mas dessa vez use tamanhos pequenos...)
[1,5 pontos] Numa árvore binária balanceada, a diferença entre as alturas da sub-árvores esquerda e direita de qualquer nó é no máximo 1. Utilizando a função altura do exercício anterior, implemente a função e_balanceada da interface arvore.h. Essa função deverá retornar 0 (falso) caso a árvore não seja balanceada, e um valor diferente de 0 (verdadeiro) caso a árvore seja balanceada. (Você pode usar a função abs para obter o valor absoluto de uma expressão...)
Modifique o programa de teste, incluindo testes para sua função e_balanceada. Novamente, você pode usar as duas árvores que o programa cria. Experimente também com uma árvore onde o "desbalancemento" seja encontrado em uma sub-árvore. Por exemplo, se você inserir chaves na ordem 3,1,2,4,5,6 o desbalanceamento será encontrado na sub-árvore direita. Crie então uma terceira árvore, inserindo nós com chaves nessa ordem, e teste se sua função fornece a resposta correta para ela.
[4 pontos] Implemente a função balancear da interface arvore.h. Essa função deverá realizar as mudanças necessárias na árvore para balanceá-la, quando necessário. Lembre-se que, em uma árvore balanceada, todas as sub-árvores devem estar balanceadas!
Para implementar sua função, você pode usar quaisquer das outras funções implementadas em mapa.c, por exemplo (e não apenas) a função num_nos.
Se quiser, você também pode criar funções auxiliares que retornam um ponteiro para o menor elemento de uma árvore, e para o maior elemento de uma árvore. Usando esse ponteiro, você pode mover os dados de um nó para outro (por exemplo, para a raiz).
Modifique o programa de teste, incluindo testes para sua função balancear. Experimente, por exemplo, balancear a árvore degenerada e a árvore sugerida no exercício anterior. Você pode usar a função mostra para exibir as árvores antes e depois do balanceamento.

Entrega do Laboratório

Faça upload dos seus arquivos mapa.c e teste.c no EAD. Indique na área de texto, que funções você implementou, e se o resultado verificado para cada uma está correto ou não.

Lembre-se de fazer a entrega mesmo que não tenha chegado ao final do exercício.