TSEARCH(3,L) AIX Technical Reference TSEARCH(3,L)
-------------------------------------------------------------------------------
tsearch, tdelete, twalk
PURPOSE
Manages binary search trees.
LIBRARY
Standard C Library (libc.a)
SYNTAX
#include <search.h>
char *tsearch (key, rootp, compar)
char *key;
char **rootp;
int (*compar) ( );
char *tdelete (key, rootp, compar)
char *key;
char **rootp;
int (*compar) ( );
void twalk (root, action)
char *root;
void (*action) ( );
DESCRIPTION
The tsearch subroutine performs a binary tree search. The algorithm is
generalized from Donald E. Knuth's The Art of Computer Programming, Volume 3,
6.2.2, Algorithm T.(*) It returns a pointer into a tree indicating where the
data specified by the key parameter can be found. If the data specified by the
key parameter is not found, the data is added to the tree in the correct place.
If there is not enough space available to create a new node, a NULL pointer is
returned. The rootp parameter points to a variable that points to the root of
the tree. If the variable to which rootp points is NULL, the variable is set
to point to the root of a new tree.
The compar parameter is a pointer to the comparison function, which is called
with two parameters that point to the elements being compared. The comparison
function must compare its parameters and return a value as follows:
---------------
(*) Reading, Massachusetts: Addison-Wesley, 1981.
Processed November 7, 1990 TSEARCH(3,L) 1
TSEARCH(3,L) AIX Technical Reference TSEARCH(3,L)
o If the first parameter is less than the second parameter, compar must
return a value less than 0.
o If the first parameter is equal to the second parameter, compar must return
0.
o If the first parameter is greater than the second parameter, compar must
return a value greater than 0.
The comparison function need not compare every byte, so arbitrary data can be
contained in the elements in addition to the values being compared.
If the rootp parameter is NULL on entry, then a NULL pointer is returned.
The tdelete subroutine deletes the data specified by the key parameter. It is
generalized from Knuth (6.2.2) Algorithm D. The rootp and compar parameters
perform the same function as they do for the tsearch subroutine. The variable
pointed to by the rootp parameter will be changed if the deleted node is the
root of the binary tree. The tdelete subroutine returns a pointer to the
parent node of the deleted node. If the data is not found, a NULL pointer is
returned. If the rootp parameter is NULL on entry, then a NULL pointer is
returned.
The twalk subroutine steps through the binary search tree whose root is pointed
to by the root parameter. (Any node in a tree can be used as the root to step
through the tree below that node.) The action parameter is the name of a
routine to be invoked at each node. The routine specified by the action
parameter is called with three parameters. The first parameter is the address
of the node currently being pointed to. The second parameter is a value from
an enumeration data type
typedef enum {preorder, postorder, endorder, leaf} VISIT;
(This data type is defined in the search.h header file). The actual value of
the second parameter depends on whether this is the first, second, or third
time that the node has been visited during a depth-first, left-to-right
traversal of the tree, or whether the node is a leaf. A leaf is a node that is
not the parent of another node. The third parameter is the level of the node
in the tree, with the root node being level zero.
The pointers to the key and the root of the tree should be of type
pointer-to-element and cast to type pointer-to-character. Although declared as
type pointer-to-character, the value returned should be cast into type
pointer-to-element. The twalk is a recursive function. A significant amount
of user stack space must be allocated to use twalk on large tree structures.
RELATED INFORMATION
In this book: "bsearch," "hsearch, hcreate, hdestroy," and "lsearch, lfind."
Processed November 7, 1990 TSEARCH(3,L) 2