Lista 1 LISP (turma A)

Instruções:

• coloque apenas as funções pedidas (mais as funções auxiliares) no arquivo "ra123456.lsp" se seu RA é 123456. Não coloque no arquivo os seus testes.
• coloque o seguinte encantamento no inicio do arquivo (substitua "123456" pelo seu RA) Note the o "123456" é um string, entre aspas. (setf pacote (or (find-package "123456") (make-package "123456"))) (in-package "123456") (export '(avl-insert avl-remove))
• me mande um email com o titulo "MC336 lista 1" e com o arquivo como attachment Isso é importante. Precisa ser ATTACHMENT - verifique que seu emailer não inclue no corpo da mensagem attachments em texto.

Definições:

Uma forma de implementar árvores binárias usando listas é representa-las como (sub-arvore-esquerda dado sub-arvore-direita)

Uma folha é representada por (NIL dado NIL)

A árvore abaixo

Este arquivo contém uma implementação em Lisp das operações de insere e remove elementos de uma árvore de busca binária, inclusive as duas operações de rotação de uma árvore. A função tprint imprime (porcamente) a árvore deitada para debuging.

Problemas

Assume que uma arvore AVL é implemenada como (nl left middle nr right) onde left e right são as subarvores a esquerda e a direita, nl e nr são as profundidades das duas sub-arvores e middle o dado armazenado no nó.

Implemente as funçoes avl-insert e avl-delete que inserem e removem um elemento de uma arvore AVL.

Extensões

Só para pensar e exercitar.

• Numa árvore avl como implementamos fica (mais) fácil implementar um impressor de árvores que imprime-a de pé. Assim a árvore (2 (1 (0 NIL -3 0 NIL) 1 1 (0 NIL 2 0 NIL)) 3 1 (0 NIL 4 0 NIL)) poderia ser impressa como 3 | +------+------+ | | 1 4 | +--+--+ | | -3 2 Implemente tal impressor.

  O que faz avl útil para isso é que você tem a profundidade da árvore a esquerda, que permite calcular quanto espaço deixar antes de imprimir a raiz, e o tamanho das barras +----+

• A árvore AVL que implementamos só armazena números, porque no código usamos o > para decidir que lado vamos na descida da árvore. Implemente as funções avl-insere e avl-delete que recebem além da arvore e do dado, uma função que compara elementos.

  A função retorna -1 se seu primeiro argumento é menor que o segundo, 0 se são iguais e +1 se o primeiro é maior que o segundo. Com essa função é possível fazer a árvore armazenar strings, ou qualquer outra coisa (desde que alguém escreva a função de comparação)