diff options
Diffstat (limited to 'avl-1.4.0/avl.texinfo')
-rw-r--r-- | avl-1.4.0/avl.texinfo | 679 |
1 files changed, 679 insertions, 0 deletions
diff --git a/avl-1.4.0/avl.texinfo b/avl-1.4.0/avl.texinfo new file mode 100644 index 0000000..9d06324 --- /dev/null +++ b/avl-1.4.0/avl.texinfo @@ -0,0 +1,679 @@ +\input texinfo @c -*-texinfo-*- +@c %**start of header +@setfilename avl.info +@settitle libavl manual +@setchapternewpage on +@c %**end of header + +@syncodeindex vr cp +@syncodeindex fn cp +@syncodeindex tp cp + +@ifinfo +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. + +@ignore +Permission is granted to process this file through TeX and print the +results, provided the printed document carries a copying permission +notice identical to this one except for the removal of this paragraph +(this paragraph not being relevant to the printed manual). + +@end ignore +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. +@end ifinfo + +@titlepage +@title libavl +@subtitle A library for manipulation of balanced binary trees +@author Ben Pfaff + +@page +@vskip 0pt plus 1filll +Copyright @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. +@end titlepage + +@node Top, Introduction to balanced binary trees, (dir), (dir) + +@ifinfo +This document describes libavl, a library for manipulation of balanced +binary trees. + +This document applies to libavl version 1.4.0. +@end ifinfo + +@menu +* Introduction to balanced binary trees:: +* Introduction to threaded trees:: +* Types:: +* Functions:: +* Tree Creation:: +* Insertion:: +* Searching:: +* Iteration:: +* Conversion:: +* Author:: +* Index:: +@end menu + +@node Introduction to balanced binary trees, Introduction to threaded trees, Top, Top +@chapter Introduction to balanced binary trees + +@cindex hash table +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. + +@cindex binary tree +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. + +@cindex red-black tree +@cindex AVL tree +@cindex rebalancing +In turn, this problem can be solved by @dfn{rebalancing} the tree after +each insertion or deletion. In rebalancing, nodes are rearranged via +transformations called @dfn{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 @dfn{AVL trees} and @dfn{red-black +trees}. libavl implements both types: + +@itemize @bullet +@item +@cindex Landis, E. M. +@cindex Adel'son-Velskii, G. M. +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 @dfn{balance factor}) is not greater than 1. + +@item +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. +@end itemize + +The table below presents a comparison among unbalanced binary trees, AVL +trees, and red-black trees. In the table, @var{n} is the number of +nodes in the tree and @var{h} is the tree's height before the +operation. @dfn{lg} is the base-2 logarithm function. + +@multitable @columnfractions .05 .30 .35 .30 + +@need 333 +@item @w{Operation} +@item +@tab Binary Tree +@tab AVL Tree +@tab Red-Black Tree + +@need 333 +@item @w{Time per insertion or deletion} +@item +@tab O(@var{h}) +@tab O(lg @var{n}) +@tab O(lg @var{n}) + +@need 333 +@item @w{Time for insertion of @var{k} nodes having sequential values} +@item +@tab O(@math{@var{k}^2}) +@tab O(@var{n} lg @var{n}) +@tab O(@var{n} lg @var{n}) + +@need 333 +@item @w{Time for insertion of @var{k} nodes having random values} +@item +@tab O(@var{n} lg @var{n}) +@tab O(@var{n} lg @var{n}) +@tab O(@var{n} lg @var{n}) + +@need 333 +@item @w{Maximum number of rotations per insertion} +@item +@tab 0 +@tab 1 +@tab lg @var{n} + +@need 333 +@item @w{Maximum number of rotations per deletion} +@item +@tab 0 +@tab lg @var{n} +@tab lg @var{n} + +@need 333 +@item @w{Maximum @var{h} as a function of @var{n}} +@item +@tab @var{n} +@tab 1.44 lg (@var{n} + 2) - .328 +@tab 2 lg (@var{n} + 1) + +@need 333 +@item @w{Minimum @var{n} as a function of @var{h}} +@item +@tab @var{h} +@tab 2^((@var{h} + .328) / 1.44) - 2 +@tab 2^(@var{h} / 2) - 1 +@end multitable + +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. + +@node Introduction to threaded trees, Types, Introduction to balanced binary trees, Top +@chapter Introduction to threaded trees + +@dfn{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@footnote{In tree traversal, @dfn{inorder} refers +to visiting the nodes in their sorted order from smallest to largest.} +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: + +@itemize @bullet +@item +Faster traversal and less memory usage during traversal, since no stack +need be maintained. + +@item +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. +@end itemize + +Some disadvantages of threaded trees are: + +@itemize @bullet +@item +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. + +@item +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. +@end itemize + +A @dfn{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. + +@node Types, Functions, Introduction to threaded trees, Top +@chapter Types + +The following types are defined and used by libavl: + +@deftp {Data Type} avl_tree +@deftpx {Data Type} avlt_tree +@deftpx {Data Type} avltr_tree +@deftpx {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. +@end deftp + +@deftp {Data Type} avl_node +@deftpx {Data Type} avlt_node +@deftpx {Data Type} avltr_node +@deftpx {Data Type} rb_node +These are the data types used to represent individual nodes in a tree. +Similar cautions apply as with @code{avl_tree} structures. +@end deftp + +@deftp {Data Type} avl_traverser +@deftpx {Data Type} avlt_traverser +@deftpx {Data Type} avltr_traverser +@deftpx {Data Type} rb_traverser +These are the data types used by the @code{avl_traverse} family of +functions to iterate across the tree. Again, these are opaque +structures. +@end deftp + +@deftp {Data Type} avl_comparison_func +Every tree must have an ordering defined by a function of this type. It +must have the following signature: + +@smallexample +int @var{compare} (const void *@var{a}, const void *@var{b}, void *@var{param}) +@end smallexample + +The return value is expected to be like that returned by @code{strcmp} +in the standard C library: negative if @var{a} < @var{b}, zero if +@var{a} = @var{b}, positive if @var{a} > @var{b}. @var{param} is an +arbitrary value defined by the user when the tree was created. +@end deftp + +@deftp {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: + +@smallexample +void @var{operate} (void *@var{data}, void *@var{param}) +@end smallexample + +@var{data} is the data item and @var{param} is an arbitrary user-defined +value set when the tree was created. +@end deftp + +@deftp {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: + +@smallexample +void *@var{copy} (void *@var{data}, void *@var{param}) +@end smallexample + +The function should return a new copy of @var{data}. @var{param} is an +arbitrary user-defined value set when the tree was created. +@end deftp + +@defmac 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. +@end defmac + +@defmac 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. +@end defmac + +@node Functions, Tree Creation, Types, Top +@chapter Functions + +@cindex unthreaded +@cindex threads +@cindex right threads +libavl is four libraries in one: + +@itemize @bullet +@item +An unthreaded AVL tree library. + +@item +A threaded AVL tree library. + +@item +A right-threaded AVL tree library. + +@item +A red-black tree library. +@end itemize + +Identifiers in these libraries are prefixed by @code{avl_}, +@code{avlt_}, @code{avltr_}, and @code{rb_}, with corresponding header +files @file{avl.h}, @file{avlt.h}, @file{avltr.h}, and @file{rb.h}, +respectively. The functions that they declare are defined in the +@file{.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.@footnote{In general, you +should build the sort of tree that you need to use, but occasionally it +is useful to convert between tree types.} + +@node Tree Creation, Insertion, Functions, Top +@chapter Tree Creation + +These functions deal with creation and destruction of AVL trees. + +@deftypefun {avl_tree *} avl_create (avl_comparison_func @var{compare}, void *@var{param}) +@deftypefunx {avlt_tree *} avlt_create (avlt_comparison_func @var{compare}, void *@var{param}) +@deftypefunx {avltr_tree *} avltr_create (avltr_comparison_func @var{compare}, void *@var{param}) +@deftypefunx {rb_tree *} rb_create (avl_comparison_func @var{compare}, void *@var{param}) +Create a new, empty tree with comparison function @var{compare}. +Arbitrary user data @var{param} is saved so that it can be passed to +user callback functions. +@end deftypefun + +@deftypefun {void} avl_destroy (avl_tree *@var{tree}, avl_node_func @var{free}) +@deftypefunx {void} avlt_destroy (avlt_tree *@var{tree}, avl_node_func @var{free}) +@deftypefunx {void} avltr_destroy (avltr_tree *@var{tree}, avl_node_func @var{free}) +@deftypefunx {void} rb_destroy (rb_tree *@var{tree}, avl_node_func @var{free}) +Destroys @var{tree}, releasing all of its storage. If @var{free} is +non-null, then it is called for every node in postorder before that node +is freed. +@end deftypefun + +@deftypefun {void} avl_free (avl_tree *@var{tree}) +@deftypefunx {void} avlt_free (avlt_tree *@var{tree}) +@deftypefunx {void} avltr_free (avltr_tree *@var{tree}) +@deftypefunx {void} rb_free (rb_tree *@var{tree}) +Destroys @var{tree}, releasing all of its storage. The data in each +node is freed with a call to the standard C library function +@code{free}. +@end deftypefun + +@deftypefun {avl_tree *} avl_copy (const avl_tree *@var{tree}, avl_copy_func @var{copy}) +@deftypefunx {avlt_tree *} avl_copy (const avlt_tree *@var{tree}, avl_copy_func @var{copy}) +@deftypefunx {avltr_tree *} avl_copy (const avltr_tree *@var{tree}, avl_copy_func @var{copy}) +@deftypefunx {rb_tree *} rb_copy (const rb_tree *@var{tree}, avl_copy_func @var{copy}) +Copies the contents of @var{tree} into a new tree, and returns the new +tree. If @var{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. +@end deftypefun + +@deftypefun int avl_count (const avl_tree *@var{tree}) +@deftypefunx int avlt_count (const avlt_tree *@var{tree}) +@deftypefunx int avltr_count (const avltr_tree *@var{tree}) +@deftypefunx int rb_count (const rb_tree *@var{tree}) +Returns the number of nodes in @var{tree}. +@end deftypefun + +@deftypefun {void *} xmalloc (size_t @var{size}) +This is not a function defined by libavl. Instead, it is a function +that the user program can define. It must allocate @var{size} bytes +using @code{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 @code{xmalloc} function defined for use by libavl, the +source files (@file{avl.c}, @file{avlt.c}, @file{avltr.c}, @file{rb.c}) +must be compiled with @code{HAVE_XMALLOC} defined. Otherwise, the +library will use its internal static @code{xmalloc}, which handles +out-of-memory errors by printing a message @samp{virtual memory +exhausted} to stderr and terminating the program with exit code +@code{EXIT_FAILURE}. +@end deftypefun + +@node Insertion, Searching, Tree Creation, Top +@chapter Insertion and Deletion + +These function insert nodes, delete nodes, and search for nodes in +trees. + +@deftypefun {void **} avl_probe (avl_tree *@var{tree}, void *@var{data}) +@deftypefunx {void **} avlt_probe (avlt_tree *@var{tree}, void *@var{data}) +@deftypefunx {void **} avltr_probe (avltr_tree *@var{tree}, void *@var{data}) +@deftypefunx {void **} rb_probe (rb_tree *@var{tree}, void *@var{data}) +These are the workhorse functions for tree insertion. They search +@var{tree} for a node with data matching @var{data}. If found, a +pointer to the matching data is returned. Otherwise, a new node is +created for @var{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@footnote{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.}. + +It is usually easier to use one of the @code{avl_insert} or +@code{avl_replace} functions instead of @code{avl_probe} directly. + +@strong{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. +@end deftypefun + +@deftypefun {void *} avl_insert (avl_tree *@var{tree}, void *@var{data}) +@deftypefunx {void *} avlt_insert (avlt_tree *@var{tree}, void *@var{data}) +@deftypefunx {void *} avltr_insert (avltr_tree *@var{tree}, void *@var{data}) +@deftypefunx {void *} rb_insert (rb_tree *@var{tree}, void *@var{data}) +If a node with data matching @var{data} exists in @var{tree}, returns +the matching data item. Otherwise, inserts @var{data} into @var{tree} +and returns a null pointer. +@end deftypefun + +@deftypefun void avl_force_insert (avl_tree *@var{tree}, void *@var{data}) +@deftypefunx void avlt_force_insert (avlt_tree *@var{tree}, void *@var{data}) +@deftypefunx void avltr_force_insert (avltr_tree *@var{tree}, void *@var{data}) +@deftypefunx void rb_force_insert (rb_tree *@var{tree}, void *@var{data}) +Inserts @var{data} into @var{tree}. If a node with data matching +@var{data} exists in @var{tree}, 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} must also be included. If macro +@code{NDEBUG} is defined when a libavl header is included, these +functions are short-circuited to a direct call to @code{avl_insert}, +and no check is performed. +@end deftypefun + +@deftypefun {void *} avl_replace (avl_tree *@var{tree}, void *@var{data}) +@deftypefunx {void *} avlt_replace (avlt_tree *@var{tree}, void *@var{data}) +@deftypefunx {void *} avltr_replace (avltr_tree *@var{tree}, void *@var{data}) +@deftypefunx {void *} rb_replace (rb_tree *@var{tree}, void *@var{data}) +If a node with data matching @var{data}, such that the comparison +function returns 0, exists in @var{tree}, replaces the node's data with +@var{data} and returns the node's former contents. Otherwise, inserts +@var{data} into @var{tree} and returns a null pointer. +@end deftypefun + +@deftypefun {void *} avl_delete (avl_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void *} avlt_delete (avlt_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void *} avltr_delete (avltr_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void *} rb_delete (rb_tree *@var{tree}, const void *@var{data}) +Searches @var{tree} for a node with data matching @var{data}. If found, +the node is deleted and its data is returned. Otherwise, returns a null +pointer. +@end deftypefun + +@deftypefun {void *} avl_force_delete (avl_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void *} avlt_force_delete (avlt_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void *} avltr_force_delete (avltr_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void *} rb_force_delete (rb_tree *@var{tree}, const void *@var{data}) +Deletes a node with data matching @var{data} from @var{tree}. If no +matching node is found, aborts the program with an assertion violation. +If macro @code{NDEBUG} is declared when a libavl header is included, +these functions are short-circuited to a direct call to +@code{avl_delete}, and no check is performed. +@end deftypefun + +@node Searching, Iteration, Insertion, Top +@chapter Searching + +These function search a tree for an item without making an insertion or +a deletion. + +@deftypefun {void *} avl_find (avl_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void **} avlt_find (avlt_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void **} avltr_find (avltr_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void *} rb_find (rb_tree *@var{tree}, const void *@var{data}) +Searches @var{tree} for a node with data matching @var{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. +@end deftypefun + +@deftypefun {void *} avl_find_close (avl_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void **} avlt_find_close (avlt_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void **} avltr_find_close (avltr_tree *@var{tree}, const void *@var{data}) +@deftypefunx {void *} rb_find_close (rb_tree *@var{tree}, const void *@var{data}) +Searches @var{tree} for a node with data matching @var{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 @var{data}; either the node +closest in value to @var{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. +@end deftypefun + +@node Iteration, Conversion, Searching, Top +@chapter Iteration + +These functions allow the caller to iterate across the items in a tree. + +@deftypefun void avl_walk (const avl_tree *@var{tree}, avl_node_func @var{operate}, void *@var{param}) +@deftypefunx void avlt_walk (const avlt_tree *@var{tree}, avl_node_func @var{operate}, void *@var{param}) +@deftypefunx void avltr_walk (const avltr_tree *@var{tree}, avl_node_func @var{operate}, void *@var{param}) +@deftypefunx void rb_walk (const rb_tree *@var{tree}, avl_node_func @var{operate}, void *@var{param}) +Walks through all the nodes in @var{tree}, and calls function +@var{operate} for each node in inorder. @var{param} overrides the value +passed to @code{avl_create} (and family) for this operation only. +@var{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. +@end deftypefun + +@deftypefun {void *} avl_traverse (const avl_tree *@var{tree}, avl_traverser *@var{trav}) +@deftypefunx {void *} avlt_traverse (const avlt_tree *@var{tree}, avlt_traverser *@var{trav}) +@deftypefunx {void *} avltr_traverse (const avltr_tree *@var{tree}, avltr_traverser *@var{trav}) +@deftypefunx {void *} rb_traverse (const rb_tree *@var{tree}, rb_traverser *@var{trav}) +Returns each of @var{tree}'s nodes' data values in sequence, then a null +pointer to indicate the last item. @var{trav} must be initialized +before the first call, either in a declaration like that below, or using +one of the functions below. + +@smallexample +avl_traverser trav = AVL_TRAVERSER_INIT; +@end smallexample + +Each @code{avl_traverser} (and family) is a separate, independent +iterator. + +For threaded and right-threaded trees, @code{avlt_next} or +@code{avltr_next}, respectively, are faster and more memory-efficient +than @code{avlt_traverse} or @code{avltr_traverse}. +@end deftypefun + +@deftypefun {void *} avl_init_traverser (avl_traverser *@var{trav}) +@deftypefunx {void *} avlt_init_traverser (avlt_traverser *@var{trav}) +@deftypefunx {void *} avltr_init_traverser (avltr_traverser *@var{trav}) +@deftypefunx {void *} rb_init_traverser (rb_traverser *@var{trav}) +Initializes the specified tree traverser structure. After this function +is called, the next call to the corresponding @code{*_traverse} function +will return the smallest value in the appropriate tree. +@end deftypefun + +@deftypefun {void **} avlt_next (const avlt_tree *@var{tree}, void **@var{data}) +@deftypefunx {void **} avltr_next (const avltr_tree *@var{tree}, void **@var{data}) +@var{data} must be a null pointer or a pointer to a data item in AVL +tree @var{tree}. Returns a pointer to the next data item after +@var{data} in @var{tree} in inorder (this is the first item if +@var{data} is a null pointer), or a null pointer if @var{data} was the +last item in @var{tree}. +@end deftypefun + +@deftypefun {void **} avltr_prev (const avltr_tree *@var{tree}, void **@var{data}) +@var{data} must be a null pointer or a pointer to a data item in AVL +tree @var{tree}. Returns a pointer to the previous data item before +@var{data} in @var{tree} in inorder (this is the last, or greatest +valued, item if @var{data} is a null pointer), or a null pointer if +@var{data} was the first item in @var{tree}. +@end deftypefun + +@node Conversion, Author, Iteration, Top +@chapter Conversion + +@deftypefun {avlt_tree *} avlt_thread (avl_tree *@var{tree}) +@deftypefunx {avltr_tree *} avltr_thread (avl_tree *@var{tree}) +Adds symmetric threads or right threads, respectively, to unthreaded AVL +tree @var{tree} and returns a pointer to @var{tree} 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}; +unthreaded functions may not be used. +@end deftypefun + +@deftypefun {avl_tree *} avlt_unthread (avlt_tree *@var{tree}) +@deftypefunx {avl_tree *} avltr_unthread (avltr_tree *@var{tree}) +Cuts all threads in threaded or right-threaded, respectively, AVL tree +@var{tree} and returns a pointer to @var{tree} cast to @code{avl_tree +*}. After one of these functions is called, unthreaded functions must +be used with @var{tree}; threaded or right-threaded functions may not be +used. +@end deftypefun + +@node Author, Index, Conversion, Top +@chapter Author + +@cindex Pfaff, Benjamin Levy +@cindex author +@cindex Knuth, Donald Ervin +@cindex @cite{Art of Computer Programming} +libavl was written by Ben Pfaff @email{blp@@gnu.org}. + +libavl's generic tree algorithms and AVL algorithms are based on those +found in Donald Knuth's venerable @cite{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., +@cite{Introduction to Algorithms}, 2nd ed., from MIT Press. + +@node Index, , Author, Top +@unnumbered Index + +@printindex cp + +@contents +@bye |