Implementação da Árvore AVL
O objetivo do trabalho é a implementação das rotinas de manipulação de uma árvore AVL.
O trabalho deve ter as definições de uma árvore AVL que armazene números inteiros e as funções de busca, inserção e remoção.
Uma aplicação deverá ser implementada para usar as funções de manipulação da árvore. Esta aplicação será um programa que recebe instruções textuais e as executa, gerando uma resposta. Neste programa a árvore inicialmente está vazia, a cada comando a árvore é modificada, e ao final do arquivo de entrada o programa termina.
Entrada:
A entrada deve conter comandos. Os comandos são i (inserção), b, (busca) e r, (remoção). Todos os comando tem um parâmetro, um número inteiro, que aparece separado do comando por um espaço. Os comandos aparecem um por linha.
i 1
i 2
i 3
i 4
b 5
r 4
Saída:
A cada comando executado uma saída deve ser gerada. A saída deve representar o estado da árvore após a execução do comando. Para o comando de busca, a saída deve também indicar se o número procurado está ou não na árvore, e apresentar a lista de nós consultados. O formato da descrição da árvore é “(R,E,D)”, onde R é o valor guardado no nó raíz, E e D são as sub-árvores esquerda e direita (recursivamente). A árvore vazia é representada por “()”. Um exemplo pode ser visto abaixo.
Para representar uma árvore onde a raíz é o “a”, “a” tem fihos “b” e “c”. “b” não tem filhos e “c” só tem o filho esquerdo “d”, usamos a seguinte linha:
(a,(b,(),()),(c,(d,(),()),()))
A saída, para cada comando de alteração (“i” ou “r”), será a repetição do comando em uma linha (tal como foi lido da entrada) e na linha seguinte a descrição da árvore resultante.
A saída para o comando de busca será a repetição do comando em uma linha e na linha seguinte a seqüência de nós visitados, separados por vírgulas (“,”). Caso o nó procurado tenha sido encontrado ele será o último da seqüência.
Exemplo de saída (para a entrada acima):
i 1
(1,(),())
i 2
(1,(),(2,(),()))
i 3
(2,(1,(),()),(3,(),()))
i 4
(2,(1,(),()),(3,(),(4,(),())))
b 5
2,3,4
r 4
(2,(1,(),()),(3,(),()))
Requisitos:
O nome do executável deve ser busca.
Não deve ter nenhuma opção de linha comando. O resultado deve sempre lido e escrito na saída padrão.
O que deve ser entregue:
Além dos arquivos fonte, deve acompanhar um makefile e um arquivo README explicando o que foi feito e com o nome dos autores.
Para testar:
busca < teste.in > teste_stdin.out
ou
busca teste.in > teste_arq.out
ENTREGA
Entregar os arquivos fontes e o Makefile. Este deve ser compilado facilmente nos servidores do Dinf, através de comando make.
MODO DE ENTREGA : enviar os arquivos por email para marcos.ddf _at_ inf.ufpr.br (até as 24h) ou eduardo _at_ inf.ufpr.br, dependendo da turma. Não poderão haver grupos com integrantes de turmas diferentes.
O trabalho pode ser individual ou em duplas. No assunto, preencher com “Entrega trabalho 057”.