========================================================================

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 <[email protected]>.

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.

========================================================================