======================================================================== WHAT IS AVLTREE? AVLTree is a small implementation of AVL trees for the C programming language. It is distributed under the Library GNU Public License (see the file LICENSE for details). This library does the basic stuff. It allows for inserts, searches, and deletes in O(log n) time. It also allows the tree to be used as a linked indexable list (search/insert functions cannot be used in that case). If you find a bug, you should mail Wessel Dankers <wsl@nl.linux.org>, who produced this version of the library and therefore is to blame. The original author is Michael H. Buselli <cosine@cosine.org>, who can be reached at the following address: Michael H. Buselli 4334 N. Hazel St. #515 Chicago, IL 60613-1456 ======================================================================== COMPILING THE LIBRARY There is a Makefile included in the distribution. ======================================================================== USING THE LIBRARIES There are no real usage documents yet. Look at avl.h (you need to include these headers in your programs to use the library) to see what functions and structures are available. As a small example: #define BUFSIZE 8192 int main(void) { char *buf[BUFSIZE]; AVLTree *tree; AVLTree *node; tree = avl_alloc_tree((avl_compare_t)strcmp, (avl_freeitem_t)free); while(fgets(buf, BUFSIZE, stdin)) avl_insert(tree, strdup(buf)); for(node = tree->head; node; node = node->next) printf("%s", node->item); avl_free_tree(tree, free); } A real implementation would check the return values of avl_alloc_tree, avl_insert and strdup of course. ======================================================================== HISTORY Version 0.1.0 (alpha): This is the initial alpha version of AVLTree. It's already fully functional for many applications, including the one that I developed it for. I've only tested it on my Linux 2.0.35/glibc2 system, so I have no idea what it will do anywhere else so far. Let me know if you have good results or bad if you try a platform that I don't mention above. This version is considered alpha because it does not yet contain all of the features that I plan for version 1.0.0. It should not contain any bugs as it is. Version 0.2.0 2000-11-28 Wessel Dankers <wsl@nl.linux.org> Modifications to support fast traversal and accessing by index. The tree is generalized to allow arbitrary comparison functions. Fixed bug: when deleting, in some cases rebalancing would not occur Version 0.3.0 2001-01-07 Wessel Dankers <wsl@nl.linux.org> Tree can now be balanced on count or depth (but depth works better). Fixed bug: balancing on count now is done correctly. Version 0.3.1 2001-07-17 Wessel Dankers <wsl@nl.linux.org> Node initialization is moved to make matters a bit more robust Version 0.3.4 2002-06-11 Wessel Dankers <wsl@fruit.eu.org> Fixed a bug in the node counting. Version 0.3.5 2002-11-15 Wessel Dankers <wsl@fruit.eu.org> Added avl_node_fixup() and avl_clear_tree(). Removed obsolete files from source tree. ========================================================================