1TDELETE(P)                 POSIX Programmer's Manual                TDELETE(P)
2
3
4

NAME

6       tdelete, tfind, tsearch, twalk - manage a binary search tree
7

SYNOPSIS

9       #include <search.h>
10
11       void *tdelete(const void *restrict key, void **restrict rootp,
12              int(*compar)(const void *, const void *));
13       void *tfind(const void *key, void *const *rootp,
14              int(*compar)(const void *, const void *));
15       void *tsearch(const void *key, void **rootp,
16              int (*compar)(const void *, const void *));
17       void twalk(const void *root,
18              void (*action)(const void *, VISIT, int));
19
20

DESCRIPTION

22       The  tdelete(),  tfind(),  tsearch(),  and twalk() functions manipulate
23       binary search trees. Comparisons are made with a user-supplied routine,
24       the  address of which is passed as the compar argument. This routine is
25       called with two arguments, which are the pointers to the elements being
26       compared.   The application shall ensure that the user-supplied routine
27       returns an integer less than, equal to, or greater than 0, according to
28       whether  the first argument is to be considered less than, equal to, or
29       greater than the second argument. The comparison function need not com‐
30       pare  every byte, so arbitrary data may be contained in the elements in
31       addition to the values being compared.
32
33       The tsearch() function shall build and access the tree. The  key  argu‐
34       ment is a pointer to an element to be accessed or stored. If there is a
35       node in the tree whose element is equal to the value pointed to by key,
36       a  pointer  to  this found node shall be returned. Otherwise, the value
37       pointed to by key shall be inserted (that is, a new node is created and
38       the  value  of  key is copied to this node), and a pointer to this node
39       returned. Only pointers are copied, so  the  application  shall  ensure
40       that  the calling routine stores the data. The rootp argument points to
41       a variable that points to the root node of the  tree.  A  null  pointer
42       value  for  the  variable pointed to by rootp denotes an empty tree; in
43       this case, the variable shall be set to point to the node  which  shall
44       be at the root of the new tree.
45
46       Like  tsearch(), tfind() shall search for a node in the tree, returning
47       a pointer to it if found. However, if it is not  found,  tfind()  shall
48       return  a  null  pointer. The arguments for tfind() are the same as for
49       tsearch().
50
51       The tdelete() function shall delete a node from a binary  search  tree.
52       The  arguments  are the same as for tsearch().  The variable pointed to
53       by rootp shall be changed if the deleted node was the root of the tree.
54       The  tdelete()  function  shall  return  a pointer to the parent of the
55       deleted node, or a null pointer if the node is not found.
56
57       The twalk() function shall traverse a  binary  search  tree.  The  root
58       argument  is  a  pointer  to the root node of the tree to be traversed.
59       (Any node in a tree may be used as the  root  for  a  walk  below  that
60       node.)  The  argument  action is the name of a routine to be invoked at
61       each node. This routine is, in turn, called with three  arguments.  The
62       first  argument  shall  be  the  address of the node being visited. The
63       structure pointed to by this argument is unspecified and shall  not  be
64       modified  by  the  application,  but  it  shall  be  possible to cast a
65       pointer-to-node into a pointer-to-pointer-to-element to access the ele‐
66       ment  stored  in the node. The second argument shall be a value from an
67       enumeration data type:
68
69
70              typedef enum { preorder, postorder, endorder, leaf } VISIT;
71
72       (defined in <search.h>), depending on whether this is the  first,  sec‐
73       ond,  or  third  time  that  the node is visited (during a depth-first,
74       left-to-right traversal of the tree), or whether the node  is  a  leaf.
75       The third argument shall be the level of the node in the tree, with the
76       root being level 0.
77
78       If the calling function alters the pointer to the root, the  result  is
79       undefined.
80

RETURN VALUE

82       If the node is found, both tsearch() and tfind() shall return a pointer
83       to it. If not, tfind() shall return a null pointer, and tsearch() shall
84       return a pointer to the inserted item.
85
86       A  null  pointer  shall be returned by tsearch() if there is not enough
87       space available to create a new node.
88
89       A null pointer shall be returned by tdelete(), tfind(),  and  tsearch()
90       if rootp is a null pointer on entry.
91
92       The  tdelete()  function  shall  return  a pointer to the parent of the
93       deleted node, or a null pointer if the node is not found.
94
95       The twalk() function shall not return a value.
96

ERRORS

98       No errors are defined.
99
100       The following sections are informative.
101

EXAMPLES

103       The following code reads in strings and stores structures containing  a
104       pointer  to  each  string  and a count of its length. It then walks the
105       tree, printing out the stored strings and their lengths in alphabetical
106       order.
107
108
109              #include <search.h>
110              #include <string.h>
111              #include <stdio.h>
112
113
114              #define STRSZ    10000
115              #define NODSZ    500
116
117
118              struct node {      /* Pointers to these are stored in the tree. */
119                  char    *string;
120                  int     length;
121              };
122
123
124              char   string_space[STRSZ];  /* Space to store strings. */
125              struct node nodes[NODSZ];    /* Nodes to store. */
126              void  *root = NULL;          /* This points to the root. */
127
128
129              int main(int argc, char *argv[])
130              {
131                  char   *strptr = string_space;
132                  struct node    *nodeptr = nodes;
133                  void   print_node(const void *, VISIT, int);
134                  int    i = 0, node_compare(const void *, const void *);
135
136
137                  while (gets(strptr) != NULL && i++ < NODSZ)  {
138                      /* Set node. */
139                      nodeptr->string = strptr;
140                      nodeptr->length = strlen(strptr);
141                      /* Put node into the tree. */
142                      (void) tsearch((void *)nodeptr, (void **)&root,
143                          node_compare);
144                      /* Adjust pointers, so we do not overwrite tree. */
145                      strptr += nodeptr->length + 1;
146                      nodeptr++;
147                  }
148                  twalk(root, print_node);
149                  return 0;
150              }
151
152
153              /*
154               *  This routine compares two nodes, based on an
155               *  alphabetical ordering of the string field.
156               */
157              int
158              node_compare(const void *node1, const void *node2)
159              {
160                  return strcmp(((const struct node *) node1)->string,
161                      ((const struct node *) node2)->string);
162              }
163
164
165              /*
166               *  This routine prints out a node, the second time
167               *  twalk encounters it or if it is a leaf.
168               */
169              void
170              print_node(const void *ptr, VISIT order, int level)
171              {
172                  const struct node *p = *(const struct node **) ptr;
173
174
175                  if (order == postorder || order == leaf)  {
176                      (void) printf("string = %s,  length = %d\n",
177                          p->string, p->length);
178                  }
179              }
180

APPLICATION USAGE

182       The  root argument to twalk() is one level of indirection less than the
183       rootp arguments to tdelete() and tsearch().
184
185       There are two nomenclatures used to refer to the order  in  which  tree
186       nodes are visited. The tsearch() function uses preorder, postorder, and
187       endorder to refer respectively to visiting a node  before  any  of  its
188       children, after its left child and before its right, and after both its
189       children.  The alternative nomenclature  uses  preorder,  inorder,  and
190       postorder  to refer to the same visits, which could result in some con‐
191       fusion over the meaning of postorder.
192

RATIONALE

194       None.
195

FUTURE DIRECTIONS

197       None.
198

SEE ALSO

200       hcreate()   ,   lsearch()   ,   the   Base   Definitions   volume    of
201       IEEE Std 1003.1-2001, <search.h>
202
204       Portions  of  this text are reprinted and reproduced in electronic form
205       from IEEE Std 1003.1, 2003 Edition, Standard for Information Technology
206       --  Portable  Operating  System  Interface (POSIX), The Open Group Base
207       Specifications Issue 6, Copyright (C) 2001-2003  by  the  Institute  of
208       Electrical  and  Electronics  Engineers, Inc and The Open Group. In the
209       event of any discrepancy between this version and the original IEEE and
210       The  Open Group Standard, the original IEEE and The Open Group Standard
211       is the referee document. The original Standard can be  obtained  online
212       at http://www.opengroup.org/unix/online.html .
213
214
215
216IEEE/The Open Group                  2003                           TDELETE(P)
Impressum