|
NAMEtsearch , tfind ,
tdelete , twalk —
manipulate binary search trees
SYNOPSIS#include <search.h>
void *
posix_tnode *
posix_tnode *
void
DESCRIPTIONThetdelete (), tfind (),
tsearch (), and twalk ()
functions manage binary search trees. This implementation uses a balanced AVL
tree, which due to its strong theoretical limit on the height of the tree has
the advantage of calling the comparison function relatively infrequently.
The comparison function passed in by the user has the same style of return values as strcmp(3). The The The The RETURN VALUESThetsearch () function returns NULL if allocation of a
new node fails (usually due to a lack of free memory).
The The EXAMPLESThis example usestsearch () to search for four strings
in root . Because the strings are not already present,
they are added. tsearch () is called twice on the
fourth string to demonstrate that a string is not added when it is already
present. tfind () is used to find the single instance
of the fourth string, and tdelete () removes it.
Finally, twalk () is used to return and display the
resulting binary search tree.
#include <stdio.h> #include <search.h> #include <string.h> int comp(const void *a, const void *b) { return strcmp(a, b); } void printwalk(const posix_tnode * node, VISIT v, int __unused0) { if (v == postorder || v == leaf) { printf("node: %s\n", *(char **)node); } } int main(void) { posix_tnode *root = NULL; char one[] = "blah1"; char two[] = "blah-2"; char three[] = "blah-3"; char four[] = "blah-4"; tsearch(one, &root, comp); tsearch(two, &root, comp); tsearch(three, &root, comp); tsearch(four, &root, comp); tsearch(four, &root, comp); printf("four: %s\n", *(char **)tfind(four, &root, comp)); tdelete(four, &root, comp); twalk(root, printwalk); return 0; } SEE ALSObsearch(3), hsearch(3), lsearch(3)STANDARDSThese functions conform to IEEE Std 1003.1-2008 (“POSIX.1”).The posix_tnode type is not part of IEEE Std 1003.1-2008 (“POSIX.1”), but is expected to be standardized by future versions of the standard. It is defined as void for source-level compatibility. Using posix_tnode makes distinguishing between nodes and keys easier.
Visit the GSP FreeBSD Man Page Interface. |