[clean-list] [ANNOUNCE] new library release: AVL trees by Fabien Todescato

Peter Achten peter88@cs.kun.nl
Tue, 11 Dec 2001 16:14:01 +0100


On behalf of Fabien Todescato:

You will find enclosed in the following mail an improved version of the
AVL tree package currently offered on the Clean download pages.

Thanks to the kind and stimulating mail from Erik, I have spent some
more time improving the documentation of the package by adding comments
in the .icl and .dcl files both detailing the usage of the functions
and giving hints at the implementation. I have also included another
example demonstrating the asymptotic time complexity of sets implemented
as lists vs sets implemented as avl trees, that I hope will illustrate
the benefits the package may bring to user's programs.

Also, I have changed the unit test and used the Mersenne Twister random
sequence generator. Having throrougly rerun the unit tests I have
discovered in the treeErase function a few - provably - unreachable
cases that I have commented out.

When time allows, I plan to provide a document outlining the theory of
AVL trees and explaining the current implementation. Also, I would be
EXTREMELY interested in using the Sparkle theorem prover for Clean in
order to build a formal correctness proof of the avl tree operations
implementation.

Voilą, thank you for your attention, and many thanks to the Clean Team
for their remarkable work.

Fabien TODESCATO