tsearch, tdelete, tfind or twalk Subroutine

Purpose

Manages binary search trees.

Library

Standard C Library (libc.a)

Syntax

#include <search.h>

void *tsearch (Key, RootPointer, ComparisonPointer)
const void *Key;
void **RootPointer;
int (*ComparisonPointer) (const void *Element1, const void *Element2);

void *tdelete (Key, RootPointer, ComparisonPointer)
const void *Key;
void **RootPointer;
int (*ComparisonPointer) (const void *Element1, const void *Element2);

void *tfind (Key, RootPointer, ComparisonPointer)
const void *Key;
void *const *RootPointer;
int (*ComparisonPointer) (const void *Element1, const void *Element2);

void twalk (Root, Action)
const void *Root;
void (*Action) (const void *Node, VISIT Type, int Level);

Description

The tsearch, tdelete, tfind and twalk subroutines manipulate binary search trees. Comparisons are made with the user-supplied routine specified by the ComparisonPointer parameter. This routine is called with two parameters, the pointers to the elements being compared.

The tsearch subroutine performs a binary tree search, returning 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. Only pointers are copied, so the calling routine must store the data. The RootPointer parameter points to a variable that points to the root of the tree. If the RootPointer parameter is the null value, the variable is set to point to the root of a new tree. If the RootPointer parameter is the null value on entry, then a null pointer is returned.

The tdelete subroutine deletes the data specified by the Key parameter. The RootPointer and ComparisonPointer parameters perform the same function as they do for the tsearch subroutine. The variable pointed to by the RootPointer parameter is 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 RootPointer parameter is null on entry, then a null pointer is returned.

The tfind subroutine searches the binary search tree. Like the tsearch subroutine, the tfind subroutine searches for a node in the tree, returning a pointer to it if found. However, if it is not found, the tfind subroutine will return a null pointer. The parameters for the tfind subroutine are the same as for the tsearch subroutine.

The twalk subroutine steps through the binary search tree whose root is pointed to by the RootPointer 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 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.

Although declared as type pointer-to-void, 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.

Parameters

Return Values

The comparison function compares its parameters and returns a value as follows:

• If the first parameter is less than the second parameter, the ComparisonPointer parameter returns a value less than 0.
• If the first parameter is equal to the second parameter, the ComparisonPointer parameter returns a value of 0.
• If the first parameter is greater than the second parameter, the ComparisonPointer parameter returns 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 node is found, the tsearch and tfind subroutines return a pointer to it. If the node is not found, the tsearch subroutine returns a pointer to the inserted item and the tfind subroutine returns a null pointer. If there is not enough space to create a new node, the tsearch subroutine returns a null pointer.

If the RootPointer parameter is a null pointer on entry, a null pointer is returned by the tsearch and tdelete subroutines.

The tdelete subroutine returns a pointer to the parent of the deleted node. If the node is not found, a null pointer is returned.

Implementation Specifics

These subroutines are part of Base Operating System (BOS) Runtime.

Related Information

The bsearch subroutine, hsearch subroutine, lsearch subroutine.

Searching and Sorting Example Program, Subroutines Overview in AIX Version 4.3 General Programming Concepts: Writing and Debugging Programs.