tdelete() — Binary tree delete

Standards

Standards / Extensions C or C++ Dependencies
XPG4
XPG4.2 Single UNIX Specification, Version 3
 both  

Format

#define _XOPEN_SOURCE
#include <search.h>

void *tdelete(const void *__restrict__ key, void **__restrict__ rootp,
              int (*compar)(const void *, const void *));

General description

The tdelete() function deletes a node from a binary search tree. The arguments are the same as for the tsearch() function. The variable pointed to by rootp will be changed if the deleted node was the root of the tree. tdelete() returns a pointer to the parent of the deleted node, or a NULL pointer if the node is not found. If the deleted node was the root of the tree, the function returns a pointer to the deleted node, since it had no parent. It frees the storage for this node before returning, so the contents of storage at the returned address are unreliable in this case.

Comparisons are made with a user-supplied routine, the address of which is passed as the compar argument. This routine is called with two arguments, the pointers to the elements being compared. The user-supplied routine must return an integer less than, equal to or greater than 0, according to whether the first argument is to be considered less than, equal to or greater than the second argument. The comparison functions need not compare every byte, so arbitrary data may be contained in the elements in addition to the values being compared.

Threading Behavior: see tsearch() — Binary tree search.

Special behavior for C++: Because C and C++ linkage conventions are incompatible, tdelete() cannot receive a C++ function pointer as the comparator argument. If you attempt to pass a C++ function pointer to tdelete(), the compiler will flag it as an error. You can pass a C or C++ function to tdelete() by declaring it as extern C.

Returned value

If successful, tdelete() returns a pointer to the parent of the deleted node.

If the node is not found, tdelete() returns a NULL pointer.

If rootp is a NULL pointer on entry, tdelete() returns a NULL pointer.

No errors are defined.

Related information