diff options
Diffstat (limited to 'avl-1.4.0/avl.html')
-rw-r--r-- | avl-1.4.0/avl.html | 1046 |
1 files changed, 0 insertions, 1046 deletions
diff --git a/avl-1.4.0/avl.html b/avl-1.4.0/avl.html deleted file mode 100644 index ef3e51e..0000000 --- a/avl-1.4.0/avl.html +++ /dev/null @@ -1,1046 +0,0 @@ -<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> |