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:
Plain binary trees:
Threaded binary trees:
Right-threaded binary trees:
Binary trees with parent pointers:
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 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.
Version 2.0.3 of libavl was released on August 26, 2007. This version changed libavl's license from GPLv2 to a mix of LGPLv3, GPLv3, and GFDL. It also (again) made libavl compatible with recent versions of Texinfo and fixed a number of other minor problems.
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:
Preformatted book:
Source distribution as a gzip'd tar archive.
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.
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 https://ftp.gnu.org/pub/gnu/avl.
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.
libdict. This library implements AVL and red-black trees and several other kinds of dictionary data structures. 2-clause BSD-style license.
avlmap. A library in C by Phil Howard that provides convenient implementations for several variable types and voluminous documentation in HTML format. Very large code; e.g., one included header file is 68 kilobytes. GNU Lesser General Public License.
glib. GTK+ includes a library named glib, which has an unoptimized recursive C implementation. GNU Lesser General Public License.
cprops. AVL trees, red-black tree, splay trees, and more, in a recursive implementation designed for multithreaded applications. GNU Lesser General Public License.
Python avllib. Iterative C implementation including all the usual routines. Although I haven't tested it, it looks very well-written. Includes Python bindings as well as some unusual but useful features (Knuth's RANK field, for instance). BSD license without advertising clause.
avllib. Brad Appleton's C and C++ implementations. Distributed under an unusual, mostly free license.
libredblack. Damian Ivereigh's implementation of red-black tree algorithms from Cormen, Leiserson, Rivest. Includes documentation and examples. GNU Lesser General Public License.
avl. Daniel Nagy's lightweight recursive implementation intended for embedded use. Implements only insertion, deletion, and search. GNU General Public License.
ubiqx. Chris Hertel's data structures library, which includes ordinary binary trees and AVL and splay trees using an object-oriented design in C. GNU Lesser General Public License.
bbst-showdown. David McManamon's Java implementation of AVL, red-black, and WAVL trees. GNU General Public License, version 2.
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: