tsearch(), tfind(), tdelete(), twalk()

Управление двоичными деревьями поиска

Прототип:

#include <search.h>
        
void * tdelete( const void * restrict key, void ** restrict rootp, int (*compar)( const void *, const void * ) );
        
void * tfind( const void *key, const void * const *rootp, int (*compar)( const void *, const void * ) );
        
void * tsearch( const void *key, void **rootp, int (*compar)( const void *, const void * ) );
        
void twalk( const void *root, void (*action)( const void *, VISIT, int ) );

Аргументы:

key

Ключ, идентифицирующий данные.

rootp

root

Корень дерева.

compar

Функция сравнения, принимающая указатели на два элемента дерева. Она должна возвращать отрицательное, положительное или нулевое значение, если первый элемент меньше, больше или равен второму.

action

Пользовательская функция, вызываемая функцией twalk() для каждого узла при обходе дерева.

Библиотека:

libc

Описание:

Функции tdelete(), tfind(), tsearch(), twalk() управляют двоичными деревьями поиска на основе алгоритмов T и D из монографии под авторством Д.Кнута (6.2.2). Функция сравнения compar, передаваемая пользователем, имеет стиль возвращаемого значения аналогичный strcmp().

Функция tfind() ищет данные, соответствующие параметру key, в двоичном дереве с корнем в rootp, возвращая указатель на данные, если они найдены и NULL, если данные не найдены.

Функция tsearch() идентична tfind() за исключением того, что, если совпадений не найдено, key добавляется в дерево и указатель на него возвращается.

Функция tdelete() удаляет узел из указанного двоичного дерева поиска и возвращает указатель на родителя удаленного узла. Функция принимает те же аргументы, что и tfind() и tsearch(). Если удаляемый узел является корнем двоичного дерева поиска, rootp будет скорректирован.

Функция twalk() обходит двоичное дерево поиска с корнем в root и вызывает функцию action для каждого узла. Функция action вызывается с тремя параметрами: указатель на текущий узел, значение из перечисления VISIT и уровень узла (где нулевой уровень является корнем дерева).

Перечисление VISIT определяется следующим образом:

typedef enum { preorder, postorder, endorder, leaf } VISIT;

Возвращаемое значение:

Функция tsearch() возвращает NULL, если выделение нового узла не удалось (обычно из-за нехватки свободной памяти).

Функции find(), tsearch(), tdelete() возвращают NULL, если rootp имеет значение NULL или данные не могут быть найдены.

Функция twalk() не возвращает значения.

Примеры:

Вставка случайных чисел в бинарное дерево, в котором повторяющиеся числа удаляются.

#include <search.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
    
void    *root = NULL;
    
void * xmalloc( unsigned n )
{
    void    *p = malloc( n );
        
    if ( p )
        return p;
    fprintf( stderr, "insufficient memory\n" );
        
    exit( EXIT_FAILURE );
}
    
int compare( const void *pa, const void *pb )
{
    if ( *(int *) pa < *(int *) pb )
        return (-1);
    if ( *(int *) pa > *(int *) pb )
        return (1);
    return (0);
}
    
void action( const void *nodep, const VISIT which, const int depth )
{
    int     *datap;
    
    switch ( which )
    {
        case preorder:
            break;
            
        case postorder:
            datap = *(int **)nodep;
            printf("%6d\n", *datap);
            break;
            
        case endorder:
            break;
            
        case leaf:
            datap = *(int **)nodep;
            printf( "%6d\n", *datap );
            break;
    }
}
    
int main( void )
{
    int     i, *ptr;
    void    *val;
        
    srand( time( NULL ) );
    for ( i = 0; i < 12; i++ )
    {
        ptr = (int *)xmalloc( sizeof( int ) );
        *ptr = rand() & 0xff;
            
        val = tsearch( (void *)ptr, &root, compare );
        if ( val == NULL )
            exit( EXIT_FAILURE );
        else
            if ( (*(int **)val) != ptr )
                free( ptr );
    }
        
    twalk( root, action );
        
    exit( EXIT_SUCCESS );
}

Классификация:

POSIX 1003.1 X/Open Systems Interfaces Extension

Безопасность использования

Точка остановки потока

Нет

Обработчик прерываний

Нет

Обработчик сигналов

Да

В потоке

Да

Предостережения:

Стандарт IEEE Std 1003.1-2001 ("POSIX.1") не указывает какое значение должно быть возвращено при удалении корневого узла. Поскольку реализации различаются, то при использовании tdelete() не нужно полагаться на какое-либо конкретное поведение.

Тематические ссылки:

bsearch(), hsearch(), lsearch()

Предыдущий раздел: Описание API системной библиотеки