======================================================================== WHAT IS AVLTREE? AVLTree is a small implimentation 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 provides an interface to iterate through your entire AVL tree, in order by key, in O(n) time (the calls that allow the iterating take constant amortized time). If you find any bugs, or if you have any comments or suggestions, send them to <cosine@cosine.org>. But before sending in a bug report, please check the AVLTree website http://cosine.org/project/AVLTree/ to make sure that you have the most recent version of AVLTree. I won't be too pleased to get a bug report on a version that is over a month obsolete, especially if I've already fixed the bug in a released version. ======================================================================== COMPILING AND INSTALLING You're on your own for this version here. I have provided a dumb Makefile that will make three header files, three object files, and a test program called avltest that tests zAVLTree.o. It may not work on your system as is, so please edit it as necessary. There ought to be a better Makefile to automatically build these libraries as static or dynamic libraries in the future. ======================================================================== USING THE LIBRARIES There are no real usage documents yet. After you build the header files (*.h) and the source code files (*.c), you can use them as documentation. The header files reveal most of the API that you need to use while the source code files contain comments above each function revealing how it works and what it does. Do pay close attention to how error codes are passed back to you. You can also review avltest.c as an example of how to use the gAVLTree type, which is the most complicated of the three types provided here. When I get around to making better documentation, I hope to provide man page style and html formats. There are three types of AVL trees provided in this library. The algorithms are all the same in their cores, but the front ends differ for different key types. If you wish to use integer keys then use iAVLTree. If your keys are strings then use zAVLTree, and for any other type of key you must use gAVLTree. Technically you can use integers and strings with gAVLTree, but by splitting out string and integer types I was hoping to get better performance for those types as well as provide a slightly easier to use API. The performance gain for using zAVLTree instead of gAVLTree is probably not worth keeping it in future versions. ======================================================================== PLATFORMS TESTED ON Version: Platform: Comments: 0.1.0 Linux 2.0.x/glibc 2/gcc Compiles with no warnings or errors. 0.1.3 OpenBSD 2.8 Compiles with no warnings or errors. ======================================================================== HISTORY Version 0.1.6 (alpha): Add xAVLIndex() and xAVLSeek() functions. Version 0.1.5 (alpha): Fixed compile warnings, some of which actually prevent AVLTree from compiling on some stricter systems. Version 0.1.4 (alpha): Incorporated idea from Samhain's version of this code to have xAVLCloseSearchNode() also return information on if an exact match was found to make some of the internal routines more efficient. Version 0.1.3 (alpha): Bug fix: AVLRebalanceNode was not being called when leaf nodes were deleted. Version 0.1.2 (alpha) 2001-03-04: Merged code files into generator programs to keep code for the two AVL tree types in sync. Introduced a third AVL tree type called the gAVLTree, which allows generic items to be keys. Updated parts of this README. Changed avltest to test from the gAVLTree structure instead of zAVLTree. Version 0.1.1 (alpha) 2001-03-04: Updated contact information. Added avltest.c for testing and demonstrating functions and usage. Added a dumb Makefile. 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. ========================================================================