INF1010 - Exercícios: Árvores Binárias de Busca e AVL

Parte 1: usando a implementação de mapa por árvores binárias de busca genéricas

Use os arquivos arvore.h, mapa.h e mapa-abb.c para fazer essa parte dos exercícios. (Ou use a sua implementação de árvores binárias de busca.)

1. Implemente uma função que determine se duas árvores binárias de busca são iguais (em chaves e estrutura).

   int iguais (Mapa *m1, Mapa *m2);
   

2. Implemente função chavek que retorna a k-ésima menor chave do mapa. Se a árvore contiver menos do que k chaves, a função deve retornar -1.

   int chavek (Mapa* m, int k);
   

3. Em nossa implementação da função retira, induzi vocês a chamarem novamente a função de retirada para eliminar o sucessor da subárvore à direita. Essa é a forma implementada no arquivo mapa-abb.c. Essa forma de resolver o problema é simples mas não eficiente, já que teremos dois percursos da subárvore à direita. Altere o programa para manter registro do "pai" do sucessor do nó a ser retirado, de maneira a conseguir retirá-lo diretamente sem nova chamada recursiva. O arquivo de testes insercaoretiradainterativa.c facilita os testes da retirada com ávores construídas passo a passo por vocês.

Parte 2: usando a implementação de mapa por árvores binárias de busca genéricas

Para essa parte vc usará a implementação de árvores avl em mapa-avl.c. (Ou use a sua implementação de árvores avl.)

1. Escreva uma função não recursiva para calcular a altura de uma árvore avl.
2. Estenda sua representação, criando em cada nó um campo chamado tamesq que contém o número de nós na subárvore à esquerda do nó. Altere suas funções de inserção e de ajuste para que gerenciem esse campo mantendo-o correto.
3. Reimplemente a função chavek usando o campo tamesq para economizar chamadas.