Lista 1 LISP (turma A)

Instruções:

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.