Useful add-on libraries

author: Eric Norum <WENorum@lbl.gov> 1999-10-06 15:40:21 +0000
committer: Eric Norum <WENorum@lbl.gov> 1999-10-06 15:40:21 +0000
commit: 683490f5a623424ef5bafc7dd920fb0a6bfc1a5f (patch)
tree: 9cc9a025ed9151457614044a2a354687261ee778 /avl-1.4.0
parent: Useful add-on libraries (diff)
download: rtems-addon-packages-683490f5a623424ef5bafc7dd920fb0a6bfc1a5f.tar.bz2
2 files changed, 1682 insertions, 0 deletions
diff --git a/avl-1.4.0/avl.html b/avl-1.4.0/avl.html
new file mode 100644
index 0000000..ef3e51e
--- /dev/null
+++ b/avl-1.4.0/avl.html
@@ -0,0 +1,1046 @@
+<HTML>
+<HEAD>
+<!-- This HTML file has been created by texi2html 1.54
+     from ./avl.texinfo on 6 October 1999 -->
+
+<TITLE>libavl manual</TITLE>
+
+</HEAD>
+<BODY>
+<H1>libavl</H1>
+<H2>A library for manipulation of balanced binary trees</H2>
+<ADDRESS>Ben Pfaff</ADDRESS>
+<P>
+<P><HR><P>
+<H1>Table of Contents</H1>
+<UL>
+<LI><A NAME="TOC1" HREF="avl.html#SEC1">Introduction to balanced binary trees</A>
+<LI><A NAME="TOC2" HREF="avl.html#SEC2">Introduction to threaded trees</A>
+<LI><A NAME="TOC3" HREF="avl.html#SEC3">Types</A>
+<LI><A NAME="TOC4" HREF="avl.html#SEC4">Functions</A>
+<LI><A NAME="TOC5" HREF="avl.html#SEC5">Tree Creation</A>
+<LI><A NAME="TOC6" HREF="avl.html#SEC6">Insertion and Deletion</A>
+<LI><A NAME="TOC7" HREF="avl.html#SEC7">Searching</A>
+<LI><A NAME="TOC8" HREF="avl.html#SEC8">Iteration</A>
+<LI><A NAME="TOC9" HREF="avl.html#SEC9">Conversion</A>
+<LI><A NAME="TOC10" HREF="avl.html#SEC10">Author</A>
+<LI><A NAME="TOC11" HREF="avl.html#SEC11">Index</A>
+</UL>
+<P><HR><P>
+
+
+<H1><A NAME="SEC1" HREF="avl.html#TOC1">Introduction to balanced binary trees</A></H1>
+
+<P>
+<A NAME="IDX1"></A>
+Consider some techniques that can be used to find a particular item in a
+data set.  Typical methods include sequential searching, digital
+searching, hash tables, and binary searching.
+
+</P>
+<P>
+Sequential searching is simple, but slow (O(n)).  Digital searching
+requires that the entire data set be known in advance, and memory
+efficient implementations are slow.
+
+</P>
+<P>
+Hash tables are fast (O(1)) for static data sets, but they can be
+wasteful of memory.  It can be difficult to choose an effective hash
+function.  Some hash tables variants also make deletion an expensive
+operation.
+
+</P>
+<P>
+<A NAME="IDX2"></A>
+Binary search techniques work almost as quickly (O(log(n)) on an ordered
+table, or on a binary tree.  Binary trees also allow easy iteration over
+the data in the tree in sorted order.  With hash tables it is necessary
+to sort the data before iterating, and after sorting the data is no
+longer in hash form.
+
+</P>
+<P>
+Binary trees are efficient for insertion, deletion, and searching, if
+data are inserted in random order.  But, if data are inserted in order
+using a naive algorithm, binary search degenerates to sequential search.
+
+</P>
+<P>
+<A NAME="IDX3"></A>
+<A NAME="IDX4"></A>
+<A NAME="IDX5"></A>
+In turn, this problem can be solved by <STRONG>rebalancing</STRONG> the tree after
+each insertion or deletion.  In rebalancing, nodes are rearranged via
+transformations called <STRONG>rotations</STRONG> using an algorithm that tends to
+minimize the tree's height.
+
+</P>
+<P>
+There are several schemes for rebalancing binary trees.  The two most
+common types of balanced tree are <STRONG>AVL trees</STRONG> and <STRONG>red-black
+trees</STRONG>.  libavl implements both types:
+
+</P>
+
+<UL>
+<LI>
+
+<A NAME="IDX6"></A>
+<A NAME="IDX7"></A>
+AVL trees, invented by Russian mathematicians G. M. Adel'son-Velskii and
+E. M. Landis, ensure that, for each node, the difference in height
+between its subtrees (the <STRONG>balance factor</STRONG>) is not greater than 1.
+
+<LI>
+
+Red-black trees, invented by R. Bayer and studied at length by
+L. J. Guibas and R. Sedgewick, assign each node of a tree a color (red
+or black), and specify a set of rules governing how red and black nodes
+may be arranged.
+</UL>
+
+<P>
+The table below presents a comparison among unbalanced binary trees, AVL
+trees, and red-black trees.  In the table, <VAR>n</VAR> is the number of
+nodes in the tree and <VAR>h</VAR> is the tree's height before the
+operation.  <STRONG>lg</STRONG> is the base-2 logarithm function.
+
+</P>
+<TABLE>
+
+<TR>Operation
+<BR>
+<TR>
+<TD> Binary Tree
+<TD> AVL Tree
+<TD> Red-Black Tree
+
+<BR>
+<TR>Time per insertion or deletion
+<BR>
+<TR>
+<TD> O(<VAR>h</VAR>)
+<TD> O(lg <VAR>n</VAR>)
+<TD> O(lg <VAR>n</VAR>)
+
+<BR>
+<TR>Time for insertion of <VAR>k</VAR> nodes having sequential values
+<BR>
+<TR>
+<TD> O(<VAR>k</VAR>^2)
+<TD> O(<VAR>n</VAR> lg <VAR>n</VAR>)
+<TD> O(<VAR>n</VAR> lg <VAR>n</VAR>)
+
+<BR>
+<TR>Time for insertion of <VAR>k</VAR> nodes having random values
+<BR>
+<TR>
+<TD> O(<VAR>n</VAR> lg <VAR>n</VAR>)
+<TD> O(<VAR>n</VAR> lg <VAR>n</VAR>)
+<TD> O(<VAR>n</VAR> lg <VAR>n</VAR>)
+
+<BR>
+<TR>Maximum number of rotations per insertion
+<BR>
+<TR>
+<TD> 0
+<TD> 1
+<TD> lg <VAR>n</VAR>
+
+<BR>
+<TR>Maximum number of rotations per deletion
+<BR>
+<TR>
+<TD> 0
+<TD> lg <VAR>n</VAR>
+<TD> lg <VAR>n</VAR>
+
+<BR>
+<TR>Maximum <VAR>h</VAR> as a function of <VAR>n</VAR>
+<BR>
+<TR>
+<TD> <VAR>n</VAR>
+<TD> 1.44 lg (<VAR>n</VAR> + 2) - .328
+<TD> 2 lg (<VAR>n</VAR> + 1)
+
+<BR>
+<TR>Minimum <VAR>n</VAR> as a function of <VAR>h</VAR>
+<BR>
+<TR>
+<TD> <VAR>h</VAR>
+<TD> 2^((<VAR>h</VAR> + .328) / 1.44) - 2
+<TD> 2^(<VAR>h</VAR> / 2) - 1
+</TABLE>
+
+There are alternatives to AVL trees that share some of their properties.
+For instance, skip lists, 2-3 trees, and splay trees all allow O(log(n))
+insertion and deletion.  The main disadvantage of these methods is that
+their operations are not as well documented in the literature.
+
+
+
+<H1><A NAME="SEC2" HREF="avl.html#TOC2">Introduction to threaded trees</A></H1>
+
+<P>
+<STRONG>Threading</STRONG> is a clever method that simplifies binary tree
+traversal.  
+
+</P>
+<P>
+Nodes in a unthreaded binary tree that have zero or one subnodes have
+two or one null subnode pointers, respectively.  In a threaded binary
+tree, a left child pointer that would otherwise be null is used to point
+to the node's inorder<A NAME="DOCF1" HREF="avl.html#FOOT1">(1)</A>
+predecessor, and in a null right child pointer points to its inorder
+successor.
+
+</P>
+<P>
+In a threaded tree, it is always possible to find the next node and the
+previous node of a node, given only a pointer to the node in question.
+In an unthreaded tree, it's also necessary to have a list of the nodes
+between the node in question and root of the tree.
+
+</P>
+<P>
+Advantages of a threaded tree compared to an unthreaded one include:
+
+</P>
+
+<UL>
+<LI>
+
+Faster traversal and less memory usage during traversal, since no stack
+need be maintained.
+
+<LI>
+
+Greater generality, since one can go from a node to its successor or
+predecessor given only the node, simplifying algorithms that require
+moving forward and backward in a tree.
+</UL>
+
+<P>
+Some disadvantages of threaded trees are:
+
+</P>
+
+<UL>
+<LI>
+
+Slower insertion and deletion, since threads need to be maintained.  In
+somes cases, this can be alleviated by constructing the tree as an
+unthreaded tree, then threading it with a special libavl function.
+
+<LI>
+
+In theory, threaded trees need two extra bits per node to indicate
+whether each child pointer points to an ordinary node or the node's
+successor/predecessor node.  In libavl, however, these bits are stored
+in a byte that is used for structure alignment padding in unthreaded
+binary trees, so no extra storage is used.
+</UL>
+
+<P>
+A <STRONG>right-threaded binary tree</STRONG> is similar to a threaded binary tree,
+but threads are only maintained on the right side of each node.  This
+allows for traversal to the right (toward larger values) but not to the
+left (toward smaller values).  Right-threaded trees are convenient when
+the properties of a threaded tree are desirable, but traversal in
+reverse sort order is not necessary.  Not threading the left links saves
+time in insertions and deletions.
+
+</P>
+<P>
+Left-threaded binary trees also exist, but they are not implemented by
+libavl.  The same effect can be obtained by sorting the tree in the
+opposite order.
+
+</P>
+
+
+<H1><A NAME="SEC3" HREF="avl.html#TOC3">Types</A></H1>
+
+<P>
+The following types are defined and used by libavl:
+
+</P>
+<P>
+<DL>
+<DT><U>Data Type:</U> <B>avl_tree</B>
+<DD><A NAME="IDX8"></A>
+<DT><U>Data Type:</U> <B>avlt_tree</B>
+<DD><A NAME="IDX9"></A>
+<DT><U>Data Type:</U> <B>avltr_tree</B>
+<DD><A NAME="IDX10"></A>
+<DT><U>Data Type:</U> <B>rb_tree</B>
+<DD><A NAME="IDX11"></A>
+These are the data types used to represent a tree.  Although they are
+defined in the libavl header files, it should never be necessary to
+access them directly.  Instead, all accesses should take place through
+libavl functions.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Data Type:</U> <B>avl_node</B>
+<DD><A NAME="IDX12"></A>
+<DT><U>Data Type:</U> <B>avlt_node</B>
+<DD><A NAME="IDX13"></A>
+<DT><U>Data Type:</U> <B>avltr_node</B>
+<DD><A NAME="IDX14"></A>
+<DT><U>Data Type:</U> <B>rb_node</B>
+<DD><A NAME="IDX15"></A>
+These are the data types used to represent individual nodes in a tree.
+Similar cautions apply as with <CODE>avl_tree</CODE> structures.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Data Type:</U> <B>avl_traverser</B>
+<DD><A NAME="IDX16"></A>
+<DT><U>Data Type:</U> <B>avlt_traverser</B>
+<DD><A NAME="IDX17"></A>
+<DT><U>Data Type:</U> <B>avltr_traverser</B>
+<DD><A NAME="IDX18"></A>
+<DT><U>Data Type:</U> <B>rb_traverser</B>
+<DD><A NAME="IDX19"></A>
+These are the data types used by the <CODE>avl_traverse</CODE> family of
+functions to iterate across the tree.  Again, these are opaque
+structures.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Data Type:</U> <B>avl_comparison_func</B>
+<DD><A NAME="IDX20"></A>
+Every tree must have an ordering defined by a function of this type.  It
+must have the following signature:
+
+</P>
+
+<PRE>
+int <VAR>compare</VAR> (const void *<VAR>a</VAR>, const void *<VAR>b</VAR>, void *<VAR>param</VAR>)
+</PRE>
+
+<P>
+The return value is expected to be like that returned by <CODE>strcmp</CODE>
+in the standard C library: negative if <VAR>a</VAR> &#60; <VAR>b</VAR>, zero if
+<VAR>a</VAR> = <VAR>b</VAR>, positive if <VAR>a</VAR> &#62; <VAR>b</VAR>.  <VAR>param</VAR> is an
+arbitrary value defined by the user when the tree was created.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Data Type:</U> <B>avl_node_func</B>
+<DD><A NAME="IDX21"></A>
+This is a class of function called to perform an operation on a data
+item.  Functions of this type have the following signature:
+
+</P>
+
+<PRE>
+void <VAR>operate</VAR> (void *<VAR>data</VAR>, void *<VAR>param</VAR>)
+</PRE>
+
+<P>
+<VAR>data</VAR> is the data item and <VAR>param</VAR> is an arbitrary user-defined
+value set when the tree was created.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Data Type:</U> <B>avl_copy_func</B>
+<DD><A NAME="IDX22"></A>
+
+</P>
+<P>
+This is a class of function called to make a new copy of a node's data.
+Functions of this type have the following signature:
+
+</P>
+
+<PRE>
+void *<VAR>copy</VAR> (void *<VAR>data</VAR>, void *<VAR>param</VAR>)
+</PRE>
+
+<P>
+The function should return a new copy of <VAR>data</VAR>.  <VAR>param</VAR> is an
+arbitrary user-defined value set when the tree was created.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Macro:</U> <B>AVL_MAX_HEIGHT</B>
+<DD><A NAME="IDX23"></A>
+This macro defines the maximum height of an AVL tree that can be handled
+by functions that maintain a stack of nodes descended.  The default
+value is 32, which allows for AVL trees with a maximum number of nodes
+between 5,704,880 and 4,294,967,295, depending on order of insertion.
+This macro may be defined by the user before including any AVL tree
+header file, in which case libavl will honor that value.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Macro:</U> <B>RB_MAX_HEIGHT</B>
+<DD><A NAME="IDX24"></A>
+This macro defines the maximum height of an AVL tree that can be handled
+by functions that maintain a stack of nodes descended.  The default
+value is 32, which allows for red-black trees with a maximum number of
+nodes of at least 65535.  This macro may be defined by the user before
+including the red-black tree header file, in which case libavl will
+honor that value.
+</DL>
+
+</P>
+
+
+<H1><A NAME="SEC4" HREF="avl.html#TOC4">Functions</A></H1>
+
+<P>
+<A NAME="IDX25"></A>
+<A NAME="IDX26"></A>
+<A NAME="IDX27"></A>
+libavl is four libraries in one:
+
+</P>
+
+<UL>
+<LI>
+
+An unthreaded AVL tree library.
+
+<LI>
+
+A threaded AVL tree library.
+
+<LI>
+
+A right-threaded AVL tree library.
+
+<LI>
+
+A red-black tree library.
+</UL>
+
+<P>
+Identifiers in these libraries are prefixed by <CODE>avl_</CODE>,
+<CODE>avlt_</CODE>, <CODE>avltr_</CODE>, and <CODE>rb_</CODE>, with corresponding header
+files <TT>`avl.h'</TT>, <TT>`avlt.h'</TT>, <TT>`avltr.h'</TT>, and <TT>`rb.h'</TT>,
+respectively.  The functions that they declare are defined in the
+<TT>`.c'</TT> files with the same names.
+
+</P>
+<P>
+Most tree functions are implemented in all three libraries, but
+threading allows more generality of operation.  So, the threaded and
+right-threaded libraries offer a few additional functions for finding
+the next or previous node from a given node.  In addition, they offer
+functions for converting trees from threaded or right-threaded
+representations to unthreaded, and vice versa.<A NAME="DOCF2" HREF="avl.html#FOOT2">(2)</A>
+
+</P>
+
+
+<H1><A NAME="SEC5" HREF="avl.html#TOC5">Tree Creation</A></H1>
+
+<P>
+These functions deal with creation and destruction of AVL trees.
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> avl_tree * <B>avl_create</B> <I>(avl_comparison_func <VAR>compare</VAR>, void *<VAR>param</VAR>)</I>
+<DD><A NAME="IDX28"></A>
+<DT><U>Function:</U> avlt_tree * <B>avlt_create</B> <I>(avlt_comparison_func <VAR>compare</VAR>, void *<VAR>param</VAR>)</I>
+<DD><A NAME="IDX29"></A>
+<DT><U>Function:</U> avltr_tree * <B>avltr_create</B> <I>(avltr_comparison_func <VAR>compare</VAR>, void *<VAR>param</VAR>)</I>
+<DD><A NAME="IDX30"></A>
+<DT><U>Function:</U> rb_tree * <B>rb_create</B> <I>(avl_comparison_func <VAR>compare</VAR>, void *<VAR>param</VAR>)</I>
+<DD><A NAME="IDX31"></A>
+Create a new, empty tree with comparison function <VAR>compare</VAR>.
+Arbitrary user data <VAR>param</VAR> is saved so that it can be passed to
+user callback functions.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void <B>avl_destroy</B> <I>(avl_tree *<VAR>tree</VAR>, avl_node_func <VAR>free</VAR>)</I>
+<DD><A NAME="IDX32"></A>
+<DT><U>Function:</U> void <B>avlt_destroy</B> <I>(avlt_tree *<VAR>tree</VAR>, avl_node_func <VAR>free</VAR>)</I>
+<DD><A NAME="IDX33"></A>
+<DT><U>Function:</U> void <B>avltr_destroy</B> <I>(avltr_tree *<VAR>tree</VAR>, avl_node_func <VAR>free</VAR>)</I>
+<DD><A NAME="IDX34"></A>
+<DT><U>Function:</U> void <B>rb_destroy</B> <I>(rb_tree *<VAR>tree</VAR>, avl_node_func <VAR>free</VAR>)</I>
+<DD><A NAME="IDX35"></A>
+Destroys <VAR>tree</VAR>, releasing all of its storage.  If <VAR>free</VAR> is
+non-null, then it is called for every node in postorder before that node
+is freed.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void <B>avl_free</B> <I>(avl_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX36"></A>
+<DT><U>Function:</U> void <B>avlt_free</B> <I>(avlt_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX37"></A>
+<DT><U>Function:</U> void <B>avltr_free</B> <I>(avltr_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX38"></A>
+<DT><U>Function:</U> void <B>rb_free</B> <I>(rb_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX39"></A>
+Destroys <VAR>tree</VAR>, releasing all of its storage.  The data in each
+node is freed with a call to the standard C library function
+<CODE>free</CODE>.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> avl_tree * <B>avl_copy</B> <I>(const avl_tree *<VAR>tree</VAR>, avl_copy_func <VAR>copy</VAR>)</I>
+<DD><A NAME="IDX40"></A>
+<DT><U>Function:</U> avlt_tree * <B>avl_copy</B> <I>(const avlt_tree *<VAR>tree</VAR>, avl_copy_func <VAR>copy</VAR>)</I>
+<DD><A NAME="IDX41"></A>
+<DT><U>Function:</U> avltr_tree * <B>avl_copy</B> <I>(const avltr_tree *<VAR>tree</VAR>, avl_copy_func <VAR>copy</VAR>)</I>
+<DD><A NAME="IDX42"></A>
+<DT><U>Function:</U> rb_tree * <B>rb_copy</B> <I>(const rb_tree *<VAR>tree</VAR>, avl_copy_func <VAR>copy</VAR>)</I>
+<DD><A NAME="IDX43"></A>
+Copies the contents of <VAR>tree</VAR> into a new tree, and returns the new
+tree.  If <VAR>copy</VAR> is non-null, then it is called to make a new copy
+of each node's data; otherwise, the node data is copied verbatim into
+the new tree.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> int <B>avl_count</B> <I>(const avl_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX44"></A>
+<DT><U>Function:</U> int <B>avlt_count</B> <I>(const avlt_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX45"></A>
+<DT><U>Function:</U> int <B>avltr_count</B> <I>(const avltr_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX46"></A>
+<DT><U>Function:</U> int <B>rb_count</B> <I>(const rb_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX47"></A>
+Returns the number of nodes in <VAR>tree</VAR>.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void * <B>xmalloc</B> <I>(size_t <VAR>size</VAR>)</I>
+<DD><A NAME="IDX48"></A>
+This is not a function defined by libavl.  Instead, it is a function
+that the user program can define.  It must allocate <VAR>size</VAR> bytes
+using <CODE>malloc</CODE> and return it.  It can handle out-of-memory errors
+however it chooses, but it may not ever return a null pointer.
+
+</P>
+<P>
+If there is an <CODE>xmalloc</CODE> function defined for use by libavl, the
+source files (<TT>`avl.c'</TT>, <TT>`avlt.c'</TT>, <TT>`avltr.c'</TT>, <TT>`rb.c'</TT>)
+must be compiled with <CODE>HAVE_XMALLOC</CODE> defined.  Otherwise, the
+library will use its internal static <CODE>xmalloc</CODE>, which handles
+out-of-memory errors by printing a message <SAMP>`virtual memory
+exhausted'</SAMP> to stderr and terminating the program with exit code
+<CODE>EXIT_FAILURE</CODE>.
+</DL>
+
+</P>
+
+
+<H1><A NAME="SEC6" HREF="avl.html#TOC6">Insertion and Deletion</A></H1>
+
+<P>
+These function insert nodes, delete nodes, and search for nodes in
+trees.
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void ** <B>avl_probe</B> <I>(avl_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX49"></A>
+<DT><U>Function:</U> void ** <B>avlt_probe</B> <I>(avlt_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX50"></A>
+<DT><U>Function:</U> void ** <B>avltr_probe</B> <I>(avltr_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX51"></A>
+<DT><U>Function:</U> void ** <B>rb_probe</B> <I>(rb_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX52"></A>
+These are the workhorse functions for tree insertion.  They search
+<VAR>tree</VAR> for a node with data matching <VAR>data</VAR>.  If found, a
+pointer to the matching data is returned.  Otherwise, a new node is
+created for <VAR>data</VAR>, and a pointer to that data is returned.  In
+either case, the pointer returned can be changed by the user, but the
+key data used by the tree's comparison must not be changed<A NAME="DOCF3" HREF="avl.html#FOOT3">(3)</A>.
+
+</P>
+<P>
+It is usually easier to use one of the <CODE>avl_insert</CODE> or
+<CODE>avl_replace</CODE> functions instead of <CODE>avl_probe</CODE> directly.
+
+</P>
+<P>
+<STRONG>Please note:</STRONG> It's not a particularly good idea to insert a null
+pointer as a data item into a tree, because several libavl functions
+return a null pointer to indicate failure.  You can sometimes avoid a
+problem by using functions that return a pointer to a pointer instead of
+a plain pointer.  Also be wary of this when casting an arithmetic type
+to a void pointer for insertion--on typical architectures, 0's become
+null pointers when this is done.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void * <B>avl_insert</B> <I>(avl_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX53"></A>
+<DT><U>Function:</U> void * <B>avlt_insert</B> <I>(avlt_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX54"></A>
+<DT><U>Function:</U> void * <B>avltr_insert</B> <I>(avltr_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX55"></A>
+<DT><U>Function:</U> void * <B>rb_insert</B> <I>(rb_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX56"></A>
+If a node with data matching <VAR>data</VAR> exists in <VAR>tree</VAR>, returns
+the matching data item.  Otherwise, inserts <VAR>data</VAR> into <VAR>tree</VAR>
+and returns a null pointer.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void <B>avl_force_insert</B> <I>(avl_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX57"></A>
+<DT><U>Function:</U> void <B>avlt_force_insert</B> <I>(avlt_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX58"></A>
+<DT><U>Function:</U> void <B>avltr_force_insert</B> <I>(avltr_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX59"></A>
+<DT><U>Function:</U> void <B>rb_force_insert</B> <I>(rb_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX60"></A>
+Inserts <VAR>data</VAR> into <VAR>tree</VAR>.  If a node with data matching
+<VAR>data</VAR> exists in <VAR>tree</VAR>, aborts the program with an assertion
+violation.  This function is implemented as a macro; if it is used, the
+standard C header <CODE>assert.h</CODE> must also be included.  If macro
+<CODE>NDEBUG</CODE> is defined when a libavl header is included, these
+functions are short-circuited to a direct call to <CODE>avl_insert</CODE>,
+and no check is performed.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void * <B>avl_replace</B> <I>(avl_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX61"></A>
+<DT><U>Function:</U> void * <B>avlt_replace</B> <I>(avlt_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX62"></A>
+<DT><U>Function:</U> void * <B>avltr_replace</B> <I>(avltr_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX63"></A>
+<DT><U>Function:</U> void * <B>rb_replace</B> <I>(rb_tree *<VAR>tree</VAR>, void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX64"></A>
+If a node with data matching <VAR>data</VAR>, such that the comparison
+function returns 0, exists in <VAR>tree</VAR>, replaces the node's data with
+<VAR>data</VAR> and returns the node's former contents.  Otherwise, inserts
+<VAR>data</VAR> into <VAR>tree</VAR> and returns a null pointer.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void * <B>avl_delete</B> <I>(avl_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX65"></A>
+<DT><U>Function:</U> void * <B>avlt_delete</B> <I>(avlt_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX66"></A>
+<DT><U>Function:</U> void * <B>avltr_delete</B> <I>(avltr_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX67"></A>
+<DT><U>Function:</U> void * <B>rb_delete</B> <I>(rb_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX68"></A>
+Searches <VAR>tree</VAR> for a node with data matching <VAR>data</VAR>.  If found,
+the node is deleted and its data is returned.  Otherwise, returns a null
+pointer.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void * <B>avl_force_delete</B> <I>(avl_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX69"></A>
+<DT><U>Function:</U> void * <B>avlt_force_delete</B> <I>(avlt_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX70"></A>
+<DT><U>Function:</U> void * <B>avltr_force_delete</B> <I>(avltr_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX71"></A>
+<DT><U>Function:</U> void * <B>rb_force_delete</B> <I>(rb_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX72"></A>
+Deletes a node with data matching <VAR>data</VAR> from <VAR>tree</VAR>.  If no
+matching node is found, aborts the program with an assertion violation.
+If macro <CODE>NDEBUG</CODE> is declared when a libavl header is included,
+these functions are short-circuited to a direct call to
+<CODE>avl_delete</CODE>, and no check is performed.
+</DL>
+
+</P>
+
+
+<H1><A NAME="SEC7" HREF="avl.html#TOC7">Searching</A></H1>
+
+<P>
+These function search a tree for an item without making an insertion or
+a deletion.
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void * <B>avl_find</B> <I>(avl_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX73"></A>
+<DT><U>Function:</U> void ** <B>avlt_find</B> <I>(avlt_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX74"></A>
+<DT><U>Function:</U> void ** <B>avltr_find</B> <I>(avltr_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX75"></A>
+<DT><U>Function:</U> void * <B>rb_find</B> <I>(rb_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX76"></A>
+Searches <VAR>tree</VAR> for a node with data matching <VAR>data</VAR>, If found,
+returns the node's data (for threaded and right-threaded trees, a
+pointer to the node's data).  Otherwise, returns a null pointer.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void * <B>avl_find_close</B> <I>(avl_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX77"></A>
+<DT><U>Function:</U> void ** <B>avlt_find_close</B> <I>(avlt_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX78"></A>
+<DT><U>Function:</U> void ** <B>avltr_find_close</B> <I>(avltr_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX79"></A>
+<DT><U>Function:</U> void * <B>rb_find_close</B> <I>(rb_tree *<VAR>tree</VAR>, const void *<VAR>data</VAR>)</I>
+<DD><A NAME="IDX80"></A>
+Searches <VAR>tree</VAR> for a node with data matching <VAR>data</VAR>.  If found,
+returns the node's data (for threaded and right-threaded trees, a
+pointer to the node's data).  If no matching item is found, then it
+finds a node whose data is "close" to <VAR>data</VAR>; either the node
+closest in value to <VAR>data</VAR>, or the node either before or after the
+node with the closest value.  Returns a null pointer if the tree does
+not contain any nodes.
+</DL>
+
+</P>
+
+
+<H1><A NAME="SEC8" HREF="avl.html#TOC8">Iteration</A></H1>
+
+<P>
+These functions allow the caller to iterate across the items in a tree.
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void <B>avl_walk</B> <I>(const avl_tree *<VAR>tree</VAR>, avl_node_func <VAR>operate</VAR>, void *<VAR>param</VAR>)</I>
+<DD><A NAME="IDX81"></A>
+<DT><U>Function:</U> void <B>avlt_walk</B> <I>(const avlt_tree *<VAR>tree</VAR>, avl_node_func <VAR>operate</VAR>, void *<VAR>param</VAR>)</I>
+<DD><A NAME="IDX82"></A>
+<DT><U>Function:</U> void <B>avltr_walk</B> <I>(const avltr_tree *<VAR>tree</VAR>, avl_node_func <VAR>operate</VAR>, void *<VAR>param</VAR>)</I>
+<DD><A NAME="IDX83"></A>
+<DT><U>Function:</U> void <B>rb_walk</B> <I>(const rb_tree *<VAR>tree</VAR>, avl_node_func <VAR>operate</VAR>, void *<VAR>param</VAR>)</I>
+<DD><A NAME="IDX84"></A>
+Walks through all the nodes in <VAR>tree</VAR>, and calls function
+<VAR>operate</VAR> for each node in inorder.  <VAR>param</VAR> overrides the value
+passed to <CODE>avl_create</CODE> (and family) for this operation only.
+<VAR>operate</VAR> must not change the key data in the nodes in a way that
+would reorder the data values or cause two values to become equal.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void * <B>avl_traverse</B> <I>(const avl_tree *<VAR>tree</VAR>, avl_traverser *<VAR>trav</VAR>)</I>
+<DD><A NAME="IDX85"></A>
+<DT><U>Function:</U> void * <B>avlt_traverse</B> <I>(const avlt_tree *<VAR>tree</VAR>, avlt_traverser *<VAR>trav</VAR>)</I>
+<DD><A NAME="IDX86"></A>
+<DT><U>Function:</U> void * <B>avltr_traverse</B> <I>(const avltr_tree *<VAR>tree</VAR>, avltr_traverser *<VAR>trav</VAR>)</I>
+<DD><A NAME="IDX87"></A>
+<DT><U>Function:</U> void * <B>rb_traverse</B> <I>(const rb_tree *<VAR>tree</VAR>, rb_traverser *<VAR>trav</VAR>)</I>
+<DD><A NAME="IDX88"></A>
+Returns each of <VAR>tree</VAR>'s nodes' data values in sequence, then a null
+pointer to indicate the last item.  <VAR>trav</VAR> must be initialized
+before the first call, either in a declaration like that below, or using
+one of the functions below.
+
+</P>
+
+<PRE>
+avl_traverser trav = AVL_TRAVERSER_INIT;
+</PRE>
+
+<P>
+Each <CODE>avl_traverser</CODE> (and family) is a separate, independent
+iterator.
+
+</P>
+<P>
+For threaded and right-threaded trees, <CODE>avlt_next</CODE> or
+<CODE>avltr_next</CODE>, respectively, are faster and more memory-efficient
+than <CODE>avlt_traverse</CODE> or <CODE>avltr_traverse</CODE>.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void * <B>avl_init_traverser</B> <I>(avl_traverser *<VAR>trav</VAR>)</I>
+<DD><A NAME="IDX89"></A>
+<DT><U>Function:</U> void * <B>avlt_init_traverser</B> <I>(avlt_traverser *<VAR>trav</VAR>)</I>
+<DD><A NAME="IDX90"></A>
+<DT><U>Function:</U> void * <B>avltr_init_traverser</B> <I>(avltr_traverser *<VAR>trav</VAR>)</I>
+<DD><A NAME="IDX91"></A>
+<DT><U>Function:</U> void * <B>rb_init_traverser</B> <I>(rb_traverser *<VAR>trav</VAR>)</I>
+<DD><A NAME="IDX92"></A>
+Initializes the specified tree traverser structure.  After this function
+is called, the next call to the corresponding <CODE>*_traverse</CODE> function
+will return the smallest value in the appropriate tree.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void ** <B>avlt_next</B> <I>(const avlt_tree *<VAR>tree</VAR>, void **<VAR>data</VAR>)</I>
+<DD><A NAME="IDX93"></A>
+<DT><U>Function:</U> void ** <B>avltr_next</B> <I>(const avltr_tree *<VAR>tree</VAR>, void **<VAR>data</VAR>)</I>
+<DD><A NAME="IDX94"></A>
+<VAR>data</VAR> must be a null pointer or a pointer to a data item in AVL
+tree <VAR>tree</VAR>.  Returns a pointer to the next data item after
+<VAR>data</VAR> in <VAR>tree</VAR> in inorder (this is the first item if
+<VAR>data</VAR> is a null pointer), or a null pointer if <VAR>data</VAR> was the
+last item in <VAR>tree</VAR>.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> void ** <B>avltr_prev</B> <I>(const avltr_tree *<VAR>tree</VAR>, void **<VAR>data</VAR>)</I>
+<DD><A NAME="IDX95"></A>
+<VAR>data</VAR> must be a null pointer or a pointer to a data item in AVL
+tree <VAR>tree</VAR>.  Returns a pointer to the previous data item before
+<VAR>data</VAR> in <VAR>tree</VAR> in inorder (this is the last, or greatest
+valued, item if <VAR>data</VAR> is a null pointer), or a null pointer if
+<VAR>data</VAR> was the first item in <VAR>tree</VAR>.
+</DL>
+
+</P>
+
+
+<H1><A NAME="SEC9" HREF="avl.html#TOC9">Conversion</A></H1>
+
+<P>
+<DL>
+<DT><U>Function:</U> avlt_tree * <B>avlt_thread</B> <I>(avl_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX96"></A>
+<DT><U>Function:</U> avltr_tree * <B>avltr_thread</B> <I>(avl_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX97"></A>
+Adds symmetric threads or right threads, respectively, to unthreaded AVL
+tree <VAR>tree</VAR> and returns a pointer to <VAR>tree</VAR> cast to the
+appropriate type.  After one of these functions is called, threaded or
+right-threaded functions, as appropriate, must be used with <VAR>tree</VAR>;
+unthreaded functions may not be used.
+</DL>
+
+</P>
+<P>
+<DL>
+<DT><U>Function:</U> avl_tree * <B>avlt_unthread</B> <I>(avlt_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX98"></A>
+<DT><U>Function:</U> avl_tree * <B>avltr_unthread</B> <I>(avltr_tree *<VAR>tree</VAR>)</I>
+<DD><A NAME="IDX99"></A>
+Cuts all threads in threaded or right-threaded, respectively, AVL tree
+<VAR>tree</VAR> and returns a pointer to <VAR>tree</VAR> cast to <CODE>avl_tree
+*</CODE>.  After one of these functions is called, unthreaded functions must
+be used with <VAR>tree</VAR>; threaded or right-threaded functions may not be
+used.
+</DL>
+
+</P>
+
+
+<H1><A NAME="SEC10" HREF="avl.html#TOC10">Author</A></H1>
+
+<P>
+<A NAME="IDX100"></A>
+<A NAME="IDX101"></A>
+<A NAME="IDX102"></A>
+<A NAME="IDX103"></A>
+libavl was written by Ben Pfaff <A HREF="mailto:blp@gnu.org"><TT>blp@gnu.org</TT></A>.
+
+</P>
+<P>
+libavl's generic tree algorithms and AVL algorithms are based on those
+found in Donald Knuth's venerable <CITE>Art of Computer Programming</CITE>
+series from Addison-Wesley, primarily Volumes 1 and 3.  libavl's
+red-black tree algorithms are based on those found in Cormen et al.,
+<CITE>Introduction to Algorithms</CITE>, 2nd ed., from MIT Press.
+
+</P>
+
+
+<H1><A NAME="SEC11" HREF="avl.html#TOC11">Index</A></H1>
+
+<P>
+<H2>a</H2>
+<DIR>
+<LI><A HREF="avl.html#IDX7">Adel'son-Velskii, G. M.</A>
+<LI><A HREF="avl.html#IDX103"><CITE>Art of Computer Programming</CITE></A>
+<LI><A HREF="avl.html#IDX101">author</A>
+<LI><A HREF="avl.html#IDX4">AVL tree</A>
+<LI><A HREF="avl.html#IDX20">avl_comparison_func</A>
+<LI><A HREF="avl.html#IDX40">avl_copy</A>, <A HREF="avl.html#IDX41">avl_copy</A>, <A HREF="avl.html#IDX42">avl_copy</A>
+<LI><A HREF="avl.html#IDX22">avl_copy_func</A>
+<LI><A HREF="avl.html#IDX44">avl_count</A>
+<LI><A HREF="avl.html#IDX28">avl_create</A>
+<LI><A HREF="avl.html#IDX65">avl_delete</A>
+<LI><A HREF="avl.html#IDX32">avl_destroy</A>
+<LI><A HREF="avl.html#IDX73">avl_find</A>
+<LI><A HREF="avl.html#IDX77">avl_find_close</A>
+<LI><A HREF="avl.html#IDX69">avl_force_delete</A>
+<LI><A HREF="avl.html#IDX57">avl_force_insert</A>
+<LI><A HREF="avl.html#IDX36">avl_free</A>
+<LI><A HREF="avl.html#IDX89">avl_init_traverser</A>
+<LI><A HREF="avl.html#IDX53">avl_insert</A>
+<LI><A HREF="avl.html#IDX23">AVL_MAX_HEIGHT</A>
+<LI><A HREF="avl.html#IDX12">avl_node</A>
+<LI><A HREF="avl.html#IDX21">avl_node_func</A>
+<LI><A HREF="avl.html#IDX49">avl_probe</A>
+<LI><A HREF="avl.html#IDX61">avl_replace</A>
+<LI><A HREF="avl.html#IDX85">avl_traverse</A>
+<LI><A HREF="avl.html#IDX16">avl_traverser</A>
+<LI><A HREF="avl.html#IDX8">avl_tree</A>
+<LI><A HREF="avl.html#IDX81">avl_walk</A>
+<LI><A HREF="avl.html#IDX45">avlt_count</A>
+<LI><A HREF="avl.html#IDX29">avlt_create</A>
+<LI><A HREF="avl.html#IDX66">avlt_delete</A>
+<LI><A HREF="avl.html#IDX33">avlt_destroy</A>
+<LI><A HREF="avl.html#IDX74">avlt_find</A>
+<LI><A HREF="avl.html#IDX78">avlt_find_close</A>
+<LI><A HREF="avl.html#IDX70">avlt_force_delete</A>
+<LI><A HREF="avl.html#IDX58">avlt_force_insert</A>
+<LI><A HREF="avl.html#IDX37">avlt_free</A>
+<LI><A HREF="avl.html#IDX90">avlt_init_traverser</A>
+<LI><A HREF="avl.html#IDX54">avlt_insert</A>
+<LI><A HREF="avl.html#IDX93">avlt_next</A>
+<LI><A HREF="avl.html#IDX13">avlt_node</A>
+<LI><A HREF="avl.html#IDX50">avlt_probe</A>
+<LI><A HREF="avl.html#IDX62">avlt_replace</A>
+<LI><A HREF="avl.html#IDX96">avlt_thread</A>
+<LI><A HREF="avl.html#IDX86">avlt_traverse</A>
+<LI><A HREF="avl.html#IDX17">avlt_traverser</A>
+<LI><A HREF="avl.html#IDX9">avlt_tree</A>
+<LI><A HREF="avl.html#IDX98">avlt_unthread</A>
+<LI><A HREF="avl.html#IDX82">avlt_walk</A>
+<LI><A HREF="avl.html#IDX46">avltr_count</A>
+<LI><A HREF="avl.html#IDX30">avltr_create</A>
+<LI><A HREF="avl.html#IDX67">avltr_delete</A>
+<LI><A HREF="avl.html#IDX34">avltr_destroy</A>
+<LI><A HREF="avl.html#IDX75">avltr_find</A>
+<LI><A HREF="avl.html#IDX79">avltr_find_close</A>
+<LI><A HREF="avl.html#IDX71">avltr_force_delete</A>
+<LI><A HREF="avl.html#IDX59">avltr_force_insert</A>
+<LI><A HREF="avl.html#IDX38">avltr_free</A>
+<LI><A HREF="avl.html#IDX91">avltr_init_traverser</A>
+<LI><A HREF="avl.html#IDX55">avltr_insert</A>
+<LI><A HREF="avl.html#IDX94">avltr_next</A>
+<LI><A HREF="avl.html#IDX14">avltr_node</A>
+<LI><A HREF="avl.html#IDX95">avltr_prev</A>
+<LI><A HREF="avl.html#IDX51">avltr_probe</A>
+<LI><A HREF="avl.html#IDX63">avltr_replace</A>
+<LI><A HREF="avl.html#IDX97">avltr_thread</A>
+<LI><A HREF="avl.html#IDX87">avltr_traverse</A>
+<LI><A HREF="avl.html#IDX18">avltr_traverser</A>
+<LI><A HREF="avl.html#IDX10">avltr_tree</A>
+<LI><A HREF="avl.html#IDX99">avltr_unthread</A>
+<LI><A HREF="avl.html#IDX83">avltr_walk</A>
+</DIR>
+<H2>b</H2>
+<DIR>
+<LI><A HREF="avl.html#IDX2">binary tree</A>
+</DIR>
+<H2>h</H2>
+<DIR>
+<LI><A HREF="avl.html#IDX1">hash table</A>
+</DIR>
+<H2>k</H2>
+<DIR>
+<LI><A HREF="avl.html#IDX102">Knuth, Donald Ervin</A>
+</DIR>
+<H2>l</H2>
+<DIR>
+<LI><A HREF="avl.html#IDX6">Landis, E. M.</A>
+</DIR>
+<H2>p</H2>
+<DIR>
+<LI><A HREF="avl.html#IDX100">Pfaff, Benjamin Levy</A>
+</DIR>
+<H2>r</H2>
+<DIR>
+<LI><A HREF="avl.html#IDX43">rb_copy</A>
+<LI><A HREF="avl.html#IDX47">rb_count</A>
+<LI><A HREF="avl.html#IDX31">rb_create</A>
+<LI><A HREF="avl.html#IDX68">rb_delete</A>
+<LI><A HREF="avl.html#IDX35">rb_destroy</A>
+<LI><A HREF="avl.html#IDX76">rb_find</A>
+<LI><A HREF="avl.html#IDX80">rb_find_close</A>
+<LI><A HREF="avl.html#IDX72">rb_force_delete</A>
+<LI><A HREF="avl.html#IDX60">rb_force_insert</A>
+<LI><A HREF="avl.html#IDX39">rb_free</A>
+<LI><A HREF="avl.html#IDX92">rb_init_traverser</A>
+<LI><A HREF="avl.html#IDX56">rb_insert</A>
+<LI><A HREF="avl.html#IDX24">RB_MAX_HEIGHT</A>
+<LI><A HREF="avl.html#IDX15">rb_node</A>
+<LI><A HREF="avl.html#IDX52">rb_probe</A>
+<LI><A HREF="avl.html#IDX64">rb_replace</A>
+<LI><A HREF="avl.html#IDX88">rb_traverse</A>
+<LI><A HREF="avl.html#IDX19">rb_traverser</A>
+<LI><A HREF="avl.html#IDX11">rb_tree</A>
+<LI><A HREF="avl.html#IDX84">rb_walk</A>
+<LI><A HREF="avl.html#IDX5">rebalancing</A>
+<LI><A HREF="avl.html#IDX3">red-black tree</A>
+<LI><A HREF="avl.html#IDX27">right threads</A>
+</DIR>
+<H2>t</H2>
+<DIR>
+<LI><A HREF="avl.html#IDX26">threads</A>
+</DIR>
+<H2>u</H2>
+<DIR>
+<LI><A HREF="avl.html#IDX25">unthreaded</A>
+</DIR>
+<H2>x</H2>
+<DIR>
+<LI><A HREF="avl.html#IDX48">xmalloc</A>
+</DIR>
+
+</P>
+<P><HR><P>
+<H1>Footnotes</H1>
+<H3><A NAME="FOOT1" HREF="avl.html#DOCF1">(1)</A></H3>
+<P>In tree traversal, <STRONG>inorder</STRONG> refers
+to visiting the nodes in their sorted order from smallest to largest.
+<H3><A NAME="FOOT2" HREF="avl.html#DOCF2">(2)</A></H3>
+<P>In general, you
+should build the sort of tree that you need to use, but occasionally it
+is useful to convert between tree types.
+<H3><A NAME="FOOT3" HREF="avl.html#DOCF3">(3)</A></H3>
+<P>It
+can be changed if this would not change the ordering of the nodes in the
+tree; i.e., if this would not cause the data in the node to be less than
+or equal to the previous node's data or greater than or equal to the
+next node's data.
+<P><HR><P>
+This document was generated on 6 October 1999 using the
+<A HREF="http://wwwcn.cern.ch/dci/texi2html/">texi2html</A>
+translator version 1.51a.</P>
+</BODY>
+</HTML>
diff --git a/avl-1.4.0/avl.text b/avl-1.4.0/avl.text
new file mode 100644
index 0000000..9804050
--- /dev/null
+++ b/avl-1.4.0/avl.text
@@ -0,0 +1,636 @@
+This file documents libavl, a library for the manipulation of balanced
+binary trees.
+
+   Copyright 1998, 1999 Free Software Foundation, Inc.
+
+   Permission is granted to make and distribute verbatim copies of this
+manual provided the copyright notice and this permission notice are
+preserved on all copies.
+
+   Permission is granted to copy and distribute modified versions of
+this manual under the conditions for verbatim copying, provided that the
+entire resulting derived work is distributed under the terms of a
+permission notice identical to this one.
+
+   Permission is granted to copy and distribute translations of this
+manual into another language, under the above conditions for modified
+versions, except that this permission notice may be stated in a
+translation approved by the Free Software Foundation.
+
+This document
+describes libavl, a library for manipulation of balanced binary trees.
+
+   This document applies to libavl version 1.4.0.
+
+Introduction to balanced binary trees
+*************************************
+
+   Consider some techniques that can be used to find a particular item
+in a data set.  Typical methods include sequential searching, digital
+searching, hash tables, and binary searching.
+
+   Sequential searching is simple, but slow (O(n)).  Digital searching
+requires that the entire data set be known in advance, and memory
+efficient implementations are slow.
+
+   Hash tables are fast (O(1)) for static data sets, but they can be
+wasteful of memory.  It can be difficult to choose an effective hash
+function.  Some hash tables variants also make deletion an expensive
+operation.
+
+   Binary search techniques work almost as quickly (O(log(n)) on an
+ordered table, or on a binary tree.  Binary trees also allow easy
+iteration over the data in the tree in sorted order.  With hash tables
+it is necessary to sort the data before iterating, and after sorting
+the data is no longer in hash form.
+
+   Binary trees are efficient for insertion, deletion, and searching, if
+data are inserted in random order.  But, if data are inserted in order
+using a naive algorithm, binary search degenerates to sequential search.
+
+   In turn, this problem can be solved by "rebalancing" the tree after
+each insertion or deletion.  In rebalancing, nodes are rearranged via
+transformations called "rotations" using an algorithm that tends to
+minimize the tree's height.
+
+   There are several schemes for rebalancing binary trees.  The two most
+common types of balanced tree are "AVL trees" and "red-black trees".
+libavl implements both types:
+
+   * AVL trees, invented by Russian mathematicians G. M.
+     Adel'son-Velskii and E. M. Landis, ensure that, for each node, the
+     difference in height between its subtrees (the "balance factor")
+     is not greater than 1.
+
+   * Red-black trees, invented by R. Bayer and studied at length by L.
+     J. Guibas and R. Sedgewick, assign each node of a tree a color (red
+     or black), and specify a set of rules governing how red and black
+     nodes may be arranged.
+
+   The table below presents a comparison among unbalanced binary trees,
+AVL trees, and red-black trees.  In the table, N is the number of nodes
+in the tree and H is the tree's height before the operation.  "lg" is
+the base-2 logarithm function.
+
+Operation                                                                        
+     Binary Tree            AVL Tree                  Red-Black Tree         
+Time�per�insertion�or�deletion                                                                        
+     O(H)                   O(lg N)                   O(lg N)                
+Time�for�insertion�of�K�nodes�having�sequential�values                                                                        
+     O(K^2)                 O(N lg N)                 O(N lg N)              
+Time�for�insertion�of�K�nodes�having�random�values                                                                        
+     O(N lg N)              O(N lg N)                 O(N lg N)              
+Maximum�number�of�rotations�per�insertion                                                                        
+     0                      1                         lg N                   
+Maximum�number�of�rotations�per�deletion                                                                        
+     0                      lg N                      lg N                   
+Maximum�H�as�a�function�of�N                                                                        
+     N                      1.44 lg (N + 2) - .328    2 lg (N + 1)           
+Minimum�N�as�a�function�of�H                                                                        
+     H                      2^((H + .328) / 1.44) - 2 2^(H / 2) - 1          
+
+   There are alternatives to AVL trees that share some of their
+properties.  For instance, skip lists, 2-3 trees, and splay trees all
+allow O(log(n)) insertion and deletion.  The main disadvantage of these
+methods is that their operations are not as well documented in the
+literature.
+
+Introduction to threaded trees
+******************************
+
+   "Threading" is a clever method that simplifies binary tree traversal.
+
+   Nodes in a unthreaded binary tree that have zero or one subnodes have
+two or one null subnode pointers, respectively.  In a threaded binary
+tree, a left child pointer that would otherwise be null is used to point
+to the node's inorder(1) predecessor, and in a null right child pointer
+points to its inorder successor.
+
+   In a threaded tree, it is always possible to find the next node and
+the previous node of a node, given only a pointer to the node in
+question.  In an unthreaded tree, it's also necessary to have a list of
+the nodes between the node in question and root of the tree.
+
+   Advantages of a threaded tree compared to an unthreaded one include:
+
+   * Faster traversal and less memory usage during traversal, since no
+     stack need be maintained.
+
+   * Greater generality, since one can go from a node to its successor
+     or predecessor given only the node, simplifying algorithms that
+     require moving forward and backward in a tree.
+
+   Some disadvantages of threaded trees are:
+
+   * Slower insertion and deletion, since threads need to be
+     maintained.  In somes cases, this can be alleviated by
+     constructing the tree as an unthreaded tree, then threading it
+     with a special libavl function.
+
+   * In theory, threaded trees need two extra bits per node to indicate
+     whether each child pointer points to an ordinary node or the node's
+     successor/predecessor node.  In libavl, however, these bits are
+     stored in a byte that is used for structure alignment padding in
+     unthreaded binary trees, so no extra storage is used.
+
+   A "right-threaded binary tree" is similar to a threaded binary tree,
+but threads are only maintained on the right side of each node.  This
+allows for traversal to the right (toward larger values) but not to the
+left (toward smaller values).  Right-threaded trees are convenient when
+the properties of a threaded tree are desirable, but traversal in
+reverse sort order is not necessary.  Not threading the left links saves
+time in insertions and deletions.
+
+   Left-threaded binary trees also exist, but they are not implemented
+by libavl.  The same effect can be obtained by sorting the tree in the
+opposite order.
+
+   ---------- Footnotes ----------
+
+   (1) In tree traversal, "inorder" refers to visiting the nodes in
+their sorted order from smallest to largest.
+
+Types
+*****
+
+   The following types are defined and used by libavl:
+
+ - Data Type: avl_tree
+ - Data Type: avlt_tree
+ - Data Type: avltr_tree
+ - Data Type: rb_tree
+     These are the data types used to represent a tree.  Although they
+     are defined in the libavl header files, it should never be
+     necessary to access them directly.  Instead, all accesses should
+     take place through libavl functions.
+
+ - Data Type: avl_node
+ - Data Type: avlt_node
+ - Data Type: avltr_node
+ - Data Type: rb_node
+     These are the data types used to represent individual nodes in a
+     tree.  Similar cautions apply as with `avl_tree' structures.
+
+ - Data Type: avl_traverser
+ - Data Type: avlt_traverser
+ - Data Type: avltr_traverser
+ - Data Type: rb_traverser
+     These are the data types used by the `avl_traverse' family of
+     functions to iterate across the tree.  Again, these are opaque
+     structures.
+
+ - Data Type: avl_comparison_func
+     Every tree must have an ordering defined by a function of this
+     type.  It must have the following signature:
+
+          int COMPARE (const void *A, const void *B, void *PARAM)
+
+     The return value is expected to be like that returned by `strcmp'
+     in the standard C library: negative if A < B, zero if A = B,
+     positive if A > B.  PARAM is an arbitrary value defined by the
+     user when the tree was created.
+
+ - Data Type: avl_node_func
+     This is a class of function called to perform an operation on a
+     data item.  Functions of this type have the following signature:
+
+          void OPERATE (void *DATA, void *PARAM)
+
+     DATA is the data item and PARAM is an arbitrary user-defined value
+     set when the tree was created.
+
+ - Data Type: avl_copy_func
+     This is a class of function called to make a new copy of a node's
+     data.  Functions of this type have the following signature:
+
+          void *COPY (void *DATA, void *PARAM)
+
+     The function should return a new copy of DATA.  PARAM is an
+     arbitrary user-defined value set when the tree was created.
+
+ - Macro: AVL_MAX_HEIGHT
+     This macro defines the maximum height of an AVL tree that can be
+     handled by functions that maintain a stack of nodes descended.
+     The default value is 32, which allows for AVL trees with a maximum
+     number of nodes between 5,704,880 and 4,294,967,295, depending on
+     order of insertion.  This macro may be defined by the user before
+     including any AVL tree header file, in which case libavl will
+     honor that value.
+
+ - Macro: RB_MAX_HEIGHT
+     This macro defines the maximum height of an AVL tree that can be
+     handled by functions that maintain a stack of nodes descended.
+     The default value is 32, which allows for red-black trees with a
+     maximum number of nodes of at least 65535.  This macro may be
+     defined by the user before including the red-black tree header
+     file, in which case libavl will honor that value.
+
+Functions
+*********
+
+   libavl is four libraries in one:
+
+   * An unthreaded AVL tree library.
+
+   * A threaded AVL tree library.
+
+   * A right-threaded AVL tree library.
+
+   * A red-black tree library.
+
+   Identifiers in these libraries are prefixed by `avl_', `avlt_',
+`avltr_', and `rb_', with corresponding header files `avl.h', `avlt.h',
+`avltr.h', and `rb.h', respectively.  The functions that they declare
+are defined in the `.c' files with the same names.
+
+   Most tree functions are implemented in all three libraries, but
+threading allows more generality of operation.  So, the threaded and
+right-threaded libraries offer a few additional functions for finding
+the next or previous node from a given node.  In addition, they offer
+functions for converting trees from threaded or right-threaded
+representations to unthreaded, and vice versa.(1)
+
+   ---------- Footnotes ----------
+
+   (1) In general, you should build the sort of tree that you need to
+use, but occasionally it is useful to convert between tree types.
+
+Tree Creation
+*************
+
+   These functions deal with creation and destruction of AVL trees.
+
+ - Function: avl_tree * avl_create (avl_comparison_func COMPARE, void
+          *PARAM)
+ - Function: avlt_tree * avlt_create (avlt_comparison_func COMPARE,
+          void *PARAM)
+ - Function: avltr_tree * avltr_create (avltr_comparison_func COMPARE,
+          void *PARAM)
+ - Function: rb_tree * rb_create (avl_comparison_func COMPARE, void
+          *PARAM)
+     Create a new, empty tree with comparison function COMPARE.
+     Arbitrary user data PARAM is saved so that it can be passed to
+     user callback functions.
+
+ - Function: void avl_destroy (avl_tree *TREE, avl_node_func FREE)
+ - Function: void avlt_destroy (avlt_tree *TREE, avl_node_func FREE)
+ - Function: void avltr_destroy (avltr_tree *TREE, avl_node_func FREE)
+ - Function: void rb_destroy (rb_tree *TREE, avl_node_func FREE)
+     Destroys TREE, releasing all of its storage.  If FREE is non-null,
+     then it is called for every node in postorder before that node is
+     freed.
+
+ - Function: void avl_free (avl_tree *TREE)
+ - Function: void avlt_free (avlt_tree *TREE)
+ - Function: void avltr_free (avltr_tree *TREE)
+ - Function: void rb_free (rb_tree *TREE)
+     Destroys TREE, releasing all of its storage.  The data in each
+     node is freed with a call to the standard C library function
+     `free'.
+
+ - Function: avl_tree * avl_copy (const avl_tree *TREE, avl_copy_func
+          COPY)
+ - Function: avlt_tree * avl_copy (const avlt_tree *TREE, avl_copy_func
+          COPY)
+ - Function: avltr_tree * avl_copy (const avltr_tree *TREE,
+          avl_copy_func COPY)
+ - Function: rb_tree * rb_copy (const rb_tree *TREE, avl_copy_func COPY)
+     Copies the contents of TREE into a new tree, and returns the new
+     tree.  If COPY is non-null, then it is called to make a new copy
+     of each node's data; otherwise, the node data is copied verbatim
+     into the new tree.
+
+ - Function: int avl_count (const avl_tree *TREE)
+ - Function: int avlt_count (const avlt_tree *TREE)
+ - Function: int avltr_count (const avltr_tree *TREE)
+ - Function: int rb_count (const rb_tree *TREE)
+     Returns the number of nodes in TREE.
+
+ - Function: void * xmalloc (size_t SIZE)
+     This is not a function defined by libavl.  Instead, it is a
+     function that the user program can define.  It must allocate SIZE
+     bytes using `malloc' and return it.  It can handle out-of-memory
+     errors however it chooses, but it may not ever return a null
+     pointer.
+
+     If there is an `xmalloc' function defined for use by libavl, the
+     source files (`avl.c', `avlt.c', `avltr.c', `rb.c') must be
+     compiled with `HAVE_XMALLOC' defined.  Otherwise, the library will
+     use its internal static `xmalloc', which handles out-of-memory
+     errors by printing a message `virtual memory exhausted' to stderr
+     and terminating the program with exit code `EXIT_FAILURE'.
+
+Insertion and Deletion
+**********************
+
+   These function insert nodes, delete nodes, and search for nodes in
+trees.
+
+ - Function: void ** avl_probe (avl_tree *TREE, void *DATA)
+ - Function: void ** avlt_probe (avlt_tree *TREE, void *DATA)
+ - Function: void ** avltr_probe (avltr_tree *TREE, void *DATA)
+ - Function: void ** rb_probe (rb_tree *TREE, void *DATA)
+     These are the workhorse functions for tree insertion.  They search
+     TREE for a node with data matching DATA.  If found, a pointer to
+     the matching data is returned.  Otherwise, a new node is created
+     for DATA, and a pointer to that data is returned.  In either case,
+     the pointer returned can be changed by the user, but the key data
+     used by the tree's comparison must not be changed(1).
+
+     It is usually easier to use one of the `avl_insert' or
+     `avl_replace' functions instead of `avl_probe' directly.
+
+     *Please note:* It's not a particularly good idea to insert a null
+     pointer as a data item into a tree, because several libavl
+     functions return a null pointer to indicate failure.  You can
+     sometimes avoid a problem by using functions that return a pointer
+     to a pointer instead of a plain pointer.  Also be wary of this
+     when casting an arithmetic type to a void pointer for
+     insertion--on typical architectures, 0's become null pointers when
+     this is done.
+
+ - Function: void * avl_insert (avl_tree *TREE, void *DATA)
+ - Function: void * avlt_insert (avlt_tree *TREE, void *DATA)
+ - Function: void * avltr_insert (avltr_tree *TREE, void *DATA)
+ - Function: void * rb_insert (rb_tree *TREE, void *DATA)
+     If a node with data matching DATA exists in TREE, returns the
+     matching data item.  Otherwise, inserts DATA into TREE and returns
+     a null pointer.
+
+ - Function: void avl_force_insert (avl_tree *TREE, void *DATA)
+ - Function: void avlt_force_insert (avlt_tree *TREE, void *DATA)
+ - Function: void avltr_force_insert (avltr_tree *TREE, void *DATA)
+ - Function: void rb_force_insert (rb_tree *TREE, void *DATA)
+     Inserts DATA into TREE.  If a node with data matching DATA exists
+     in TREE, aborts the program with an assertion violation.  This
+     function is implemented as a macro; if it is used, the standard C
+     header `assert.h' must also be included.  If macro `NDEBUG' is
+     defined when a libavl header is included, these functions are
+     short-circuited to a direct call to `avl_insert', and no check is
+     performed.
+
+ - Function: void * avl_replace (avl_tree *TREE, void *DATA)
+ - Function: void * avlt_replace (avlt_tree *TREE, void *DATA)
+ - Function: void * avltr_replace (avltr_tree *TREE, void *DATA)
+ - Function: void * rb_replace (rb_tree *TREE, void *DATA)
+     If a node with data matching DATA, such that the comparison
+     function returns 0, exists in TREE, replaces the node's data with
+     DATA and returns the node's former contents.  Otherwise, inserts
+     DATA into TREE and returns a null pointer.
+
+ - Function: void * avl_delete (avl_tree *TREE, const void *DATA)
+ - Function: void * avlt_delete (avlt_tree *TREE, const void *DATA)
+ - Function: void * avltr_delete (avltr_tree *TREE, const void *DATA)
+ - Function: void * rb_delete (rb_tree *TREE, const void *DATA)
+     Searches TREE for a node with data matching DATA.  If found, the
+     node is deleted and its data is returned.  Otherwise, returns a
+     null pointer.
+
+ - Function: void * avl_force_delete (avl_tree *TREE, const void *DATA)
+ - Function: void * avlt_force_delete (avlt_tree *TREE, const void
+          *DATA)
+ - Function: void * avltr_force_delete (avltr_tree *TREE, const void
+          *DATA)
+ - Function: void * rb_force_delete (rb_tree *TREE, const void *DATA)
+     Deletes a node with data matching DATA from TREE.  If no matching
+     node is found, aborts the program with an assertion violation.  If
+     macro `NDEBUG' is declared when a libavl header is included, these
+     functions are short-circuited to a direct call to `avl_delete',
+     and no check is performed.
+
+   ---------- Footnotes ----------
+
+   (1) It can be changed if this would not change the ordering of the
+nodes in the tree; i.e., if this would not cause the data in the node
+to be less than or equal to the previous node's data or greater than or
+equal to the next node's data.
+
+Searching
+*********
+
+   These function search a tree for an item without making an insertion
+or a deletion.
+
+ - Function: void * avl_find (avl_tree *TREE, const void *DATA)
+ - Function: void ** avlt_find (avlt_tree *TREE, const void *DATA)
+ - Function: void ** avltr_find (avltr_tree *TREE, const void *DATA)
+ - Function: void * rb_find (rb_tree *TREE, const void *DATA)
+     Searches TREE for a node with data matching DATA, If found,
+     returns the node's data (for threaded and right-threaded trees, a
+     pointer to the node's data).  Otherwise, returns a null pointer.
+
+ - Function: void * avl_find_close (avl_tree *TREE, const void *DATA)
+ - Function: void ** avlt_find_close (avlt_tree *TREE, const void *DATA)
+ - Function: void ** avltr_find_close (avltr_tree *TREE, const void
+          *DATA)
+ - Function: void * rb_find_close (rb_tree *TREE, const void *DATA)
+     Searches TREE for a node with data matching DATA.  If found,
+     returns the node's data (for threaded and right-threaded trees, a
+     pointer to the node's data).  If no matching item is found, then it
+     finds a node whose data is "close" to DATA; either the node
+     closest in value to DATA, or the node either before or after the
+     node with the closest value.  Returns a null pointer if the tree
+     does not contain any nodes.
+
+Iteration
+*********
+
+   These functions allow the caller to iterate across the items in a
+tree.
+
+ - Function: void avl_walk (const avl_tree *TREE, avl_node_func
+          OPERATE, void *PARAM)
+ - Function: void avlt_walk (const avlt_tree *TREE, avl_node_func
+          OPERATE, void *PARAM)
+ - Function: void avltr_walk (const avltr_tree *TREE, avl_node_func
+          OPERATE, void *PARAM)
+ - Function: void rb_walk (const rb_tree *TREE, avl_node_func OPERATE,
+          void *PARAM)
+     Walks through all the nodes in TREE, and calls function OPERATE
+     for each node in inorder.  PARAM overrides the value passed to
+     `avl_create' (and family) for this operation only.  OPERATE must
+     not change the key data in the nodes in a way that would reorder
+     the data values or cause two values to become equal.
+
+ - Function: void * avl_traverse (const avl_tree *TREE, avl_traverser
+          *TRAV)
+ - Function: void * avlt_traverse (const avlt_tree *TREE,
+          avlt_traverser *TRAV)
+ - Function: void * avltr_traverse (const avltr_tree *TREE,
+          avltr_traverser *TRAV)
+ - Function: void * rb_traverse (const rb_tree *TREE, rb_traverser
+          *TRAV)
+     Returns each of TREE's nodes' data values in sequence, then a null
+     pointer to indicate the last item.  TRAV must be initialized
+     before the first call, either in a declaration like that below, or
+     using one of the functions below.
+
+          avl_traverser trav = AVL_TRAVERSER_INIT;
+
+     Each `avl_traverser' (and family) is a separate, independent
+     iterator.
+
+     For threaded and right-threaded trees, `avlt_next' or
+     `avltr_next', respectively, are faster and more memory-efficient
+     than `avlt_traverse' or `avltr_traverse'.
+
+ - Function: void * avl_init_traverser (avl_traverser *TRAV)
+ - Function: void * avlt_init_traverser (avlt_traverser *TRAV)
+ - Function: void * avltr_init_traverser (avltr_traverser *TRAV)
+ - Function: void * rb_init_traverser (rb_traverser *TRAV)
+     Initializes the specified tree traverser structure.  After this
+     function is called, the next call to the corresponding
+     `*_traverse' function will return the smallest value in the
+     appropriate tree.
+
+ - Function: void ** avlt_next (const avlt_tree *TREE, void **DATA)
+ - Function: void ** avltr_next (const avltr_tree *TREE, void **DATA)
+     DATA must be a null pointer or a pointer to a data item in AVL
+     tree TREE.  Returns a pointer to the next data item after DATA in
+     TREE in inorder (this is the first item if DATA is a null
+     pointer), or a null pointer if DATA was the last item in TREE.
+
+ - Function: void ** avltr_prev (const avltr_tree *TREE, void **DATA)
+     DATA must be a null pointer or a pointer to a data item in AVL
+     tree TREE.  Returns a pointer to the previous data item before
+     DATA in TREE in inorder (this is the last, or greatest valued,
+     item if DATA is a null pointer), or a null pointer if DATA was the
+     first item in TREE.
+
+Conversion
+**********
+
+ - Function: avlt_tree * avlt_thread (avl_tree *TREE)
+ - Function: avltr_tree * avltr_thread (avl_tree *TREE)
+     Adds symmetric threads or right threads, respectively, to
+     unthreaded AVL tree TREE and returns a pointer to TREE cast to the
+     appropriate type.  After one of these functions is called,
+     threaded or right-threaded functions, as appropriate, must be used
+     with TREE; unthreaded functions may not be used.
+
+ - Function: avl_tree * avlt_unthread (avlt_tree *TREE)
+ - Function: avl_tree * avltr_unthread (avltr_tree *TREE)
+     Cuts all threads in threaded or right-threaded, respectively, AVL
+     tree TREE and returns a pointer to TREE cast to `avl_tree *'.
+     After one of these functions is called, unthreaded functions must
+     be used with TREE; threaded or right-threaded functions may not be
+     used.
+
+Author
+******
+
+   libavl was written by Ben Pfaff <blp@gnu.org>.
+
+   libavl's generic tree algorithms and AVL algorithms are based on
+those found in Donald Knuth's venerable `Art of Computer Programming'
+series from Addison-Wesley, primarily Volumes 1 and 3.  libavl's
+red-black tree algorithms are based on those found in Cormen et al.,
+`Introduction to Algorithms', 2nd ed., from MIT Press.
+
+Index
+*****
+
+* Menu:
+
+* `Art of Computer Programming':         Author.
+* Adel'son-Velskii, G. M.:               Introduction to balanced binary trees.
+* author:                                Author.
+* AVL tree:                              Introduction to balanced binary trees.
+* avl_comparison_func:                   Types.
+* avl_copy:                              Tree Creation.
+* avl_copy_func:                         Types.
+* avl_count:                             Tree Creation.
+* avl_create:                            Tree Creation.
+* avl_delete:                            Insertion.
+* avl_destroy:                           Tree Creation.
+* avl_find:                              Searching.
+* avl_find_close:                        Searching.
+* avl_force_delete:                      Insertion.
+* avl_force_insert:                      Insertion.
+* avl_free:                              Tree Creation.
+* avl_init_traverser:                    Iteration.
+* avl_insert:                            Insertion.
+* AVL_MAX_HEIGHT:                        Types.
+* avl_node:                              Types.
+* avl_node_func:                         Types.
+* avl_probe:                             Insertion.
+* avl_replace:                           Insertion.
+* avl_traverse:                          Iteration.
+* avl_traverser:                         Types.
+* avl_tree:                              Types.
+* avl_walk:                              Iteration.
+* avlt_count:                            Tree Creation.
+* avlt_create:                           Tree Creation.
+* avlt_delete:                           Insertion.
+* avlt_destroy:                          Tree Creation.
+* avlt_find:                             Searching.
+* avlt_find_close:                       Searching.
+* avlt_force_delete:                     Insertion.
+* avlt_force_insert:                     Insertion.
+* avlt_free:                             Tree Creation.
+* avlt_init_traverser:                   Iteration.
+* avlt_insert:                           Insertion.
+* avlt_next:                             Iteration.
+* avlt_node:                             Types.
+* avlt_probe:                            Insertion.
+* avlt_replace:                          Insertion.
+* avlt_thread:                           Conversion.
+* avlt_traverse:                         Iteration.
+* avlt_traverser:                        Types.
+* avlt_tree:                             Types.
+* avlt_unthread:                         Conversion.
+* avlt_walk:                             Iteration.
+* avltr_count:                           Tree Creation.
+* avltr_create:                          Tree Creation.
+* avltr_delete:                          Insertion.
+* avltr_destroy:                         Tree Creation.
+* avltr_find:                            Searching.
+* avltr_find_close:                      Searching.
+* avltr_force_delete:                    Insertion.
+* avltr_force_insert:                    Insertion.
+* avltr_free:                            Tree Creation.
+* avltr_init_traverser:                  Iteration.
+* avltr_insert:                          Insertion.
+* avltr_next:                            Iteration.
+* avltr_node:                            Types.
+* avltr_prev:                            Iteration.
+* avltr_probe:                           Insertion.
+* avltr_replace:                         Insertion.
+* avltr_thread:                          Conversion.
+* avltr_traverse:                        Iteration.
+* avltr_traverser:                       Types.
+* avltr_tree:                            Types.
+* avltr_unthread:                        Conversion.
+* avltr_walk:                            Iteration.
+* binary tree:                           Introduction to balanced binary trees.
+* hash table:                            Introduction to balanced binary trees.
+* Knuth, Donald Ervin:                   Author.
+* Landis, E. M.:                         Introduction to balanced binary trees.
+* Pfaff, Benjamin Levy:                  Author.
+* rb_copy:                               Tree Creation.
+* rb_count:                              Tree Creation.
+* rb_create:                             Tree Creation.
+* rb_delete:                             Insertion.
+* rb_destroy:                            Tree Creation.
+* rb_find:                               Searching.
+* rb_find_close:                         Searching.
+* rb_force_delete:                       Insertion.
+* rb_force_insert:                       Insertion.
+* rb_free:                               Tree Creation.
+* rb_init_traverser:                     Iteration.
+* rb_insert:                             Insertion.
+* RB_MAX_HEIGHT:                         Types.
+* rb_node:                               Types.
+* rb_probe:                              Insertion.
+* rb_replace:                            Insertion.
+* rb_traverse:                           Iteration.
+* rb_traverser:                          Types.
+* rb_tree:                               Types.
+* rb_walk:                               Iteration.
+* rebalancing:                           Introduction to balanced binary trees.
+* red-black tree:                        Introduction to balanced binary trees.
+* right threads:                         Functions.
+* threads:                               Functions.
+* unthreaded:                            Functions.
+* xmalloc:                               Tree Creation.
+
author	Eric Norum <WENorum@lbl.gov>	1999-10-06 15:40:21 +0000
committer	Eric Norum <WENorum@lbl.gov>	1999-10-06 15:40:21 +0000
commit	683490f5a623424ef5bafc7dd920fb0a6bfc1a5f (patch)
tree	9cc9a025ed9151457614044a2a354687261ee778 /avl-1.4.0
parent	Useful add-on libraries (diff)
download	rtems-addon-packages-683490f5a623424ef5bafc7dd920fb0a6bfc1a5f.tar.bz2