HP C/iX Library Reference Manual (30026-90004)

362 Chapter5
HP C/iX Library Function Descriptions
tdelete
tdelete
Deletes a specified node from a binary search tree.
Syntax
#include <search.h>
void *tdelete (void * key , void ** rootp , int (* compar )());
Parameters
key A pointer to an item to be searched for and deleted.
rootp A pointer to the variable at the root of the tree.
compar A pointer to a comparison function supplied by the user.
Return Values
x A pointer to the parent node of the deleted entry.
NULL Entry not found or
rootp is NULL on entry.
Description
The tdelete function searches a binary search tree for the specified entry and deletes it if
found. The tree is composed only of pointers. The values reference by these pointers are
stored separately from the tree by the calling program.
The tdelete, tfind, tsearch, and twalk functions manage binary search trees
generalized from Knuth Algorithms T and D (6.2.2 ) described in The Art of Computer
Programming, Vol3 (Sorting and Searching) by Donald Ervin Knuth (Reading,
Mass.:Addison-Wesley, 1973).
If there is an item in the tree equal to *
key (the value pointed to by key ), the pointer to the
item is removed from the tree and the descendants of that node are resorted. If no
matching item is found in the tree, a null pointer is returned.
If the deleted node is the root of the tree, the variable pointed to by
rootp is changed. A
null value for the variable pointed to by
rootp indicates an empty tree.
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. Similarly, although declared as type pointer-to-character,
the value returned should be cast into type pointer-to-element.
All comparisons are done with the function
compar , which must be supplied by the
programmer. This function is called with two arguments, the pointers to the elements
being compared. The comparison function does not need to compare every byte, so
arbitrary data can be contained in the elements in addition to the values being compared.
The comparison function should return an integer either less than, equal to, or greater
than zero, according to whether the first argument is to be considered less than, equal to,
or greater than the second argument.