<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> < <VAR>b</VAR>, zero if
<VAR>a</VAR> = <VAR>b</VAR>, positive if <VAR>a</VAR> > <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>
