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
4
/ \
2 7
/ \ \
1 3 9
seria representada como
(((NIL 1 NIL) 2 (NIL 3 NIL)) 4 (NIL 7 (NIL 9 NIL)))
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)