GNU libavl

Binary search trees provide O(lg n) performance on average for important operations such as item insertion, deletion, and search operations. Balanced trees provide O(lg n) even in the worst case.

GNU libavl is the most complete, well-documented collection of binary search tree and balanced tree library routines anywhere. It supports these kinds of trees:

Visit the online HTML version of libavl.

libavl's name is a historical accident: it originally implemented only AVL trees. Its name may change to something more appropriate in the future, such as “libsearch”. You should also expect this page to migrate to www.gnu.org sometime in the indefinite future.

Version 2.0

Version 2.0 of libavl was released on January 6, 2002. It is a complete rewrite of earlier versions implemented in a “literate programming” fashion, such that in addition to being a useful library, it is also a book describing in full the algorithms behind the library.

Version 2.0.1 of libavl was released on August 24, 2002. It fixes some typos in the text and introduces an HTML output format. No bugs in the libavl code were fixed, because none were reported. Unlike 2.0, this version is compatible with recent releases of Texinfo. dvipdfm is now used for producing the PDF version.

Version 2.0.2 of libavl was released on December 28, 2004. It fixes a bug in tavl_delete() reported by Petr Silhavy a long time ago. This is the same fix posted here earlier. This version (again) works with recent versions of Texinfo, fixes a few typos in the text, and slightly enhances the HTML output format.

You can download the preformatted book or a source distribution that will allow you to use the library in your own programs. You can also use the source distribution to format the book yourself:

For an overview of the ideas behind libavl 2.0, see the poster presentation made on April 6, 2001, at Michigan State University. This presentation is also available in the original PostScript.

Older Versions

Version 1.4.0 is the predecessor to 2.0. It implemented only the following types of trees:

Version 1.4.0 is no longer being actively developed, but any reported bugs that affect its behavior will be fixed. Source code for libavl 1.4.0 can be obtained from ftp://ftp.gnu.org/pub/gnu/avl.

Other AVL resources

Several AVL tree libraries are available on the net. The following is a list of the ones that I consider to be well-written and generally useful in other code. Let me know of any others and I'll add them to the list after checking them out.

The following are also AVL libraries, but not suited for the above list because they are incomplete or difficult to use in other code. At one time I also listed non-free libraries here, but I no longer do so due to the current profusion of free ones:

Translations

This webpage has been translated to Belorussian.


Last updated 23 Mar 2014 11:49. Copyright © 2014 Ben Pfaff.
May be freely redistributed, but copyright notice must be retained.