diff options
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 | 1ad19cf7ed34ec3352d5e7b116de4d4745a0b901 (diff) |
Useful add-on libraries
Diffstat (limited to 'avl-1.4.0')
-rw-r--r-- | avl-1.4.0/avl.html | 1046 | ||||
-rw-r--r-- | avl-1.4.0/avl.text | 636 |
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> < <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> 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. + |