Man pages на русском
TSEARCH(3C)
НАЗВАНИЕ
tsearch, tfind, tdelete, twalk - управление бинарными деревьями поиска
СИНТАКСИС
#include <search.h>
char *tsearch ((char *) key, (char **) rootp, compar) int (*compar) ( );
char *tfind ((char *) key, (char **) rootp, compar) int (*compar) ( );
char *tdelete ((char *) key, (char **) rootp, compar) int (*compar) ( );
char *twalk ((char *) root, action) void (*action) ( );
ОПИСАНИЕ
Функции tsearch, tfind, tdelete и twalk предназначены для выполнения операций над бинарными деревьями поиска. Функции реализованы на основе алгоритмов, описанных в книге Д. Кнута: Искусство программирования для ЭВМ. Т. 3. Сортировка, поиск. - М.: Мир, 1978. Раздел 6.2.2, алгоритмы T и D. Операции сравнения выполняются с помощью функции, предоставляемой пользователем. Функция сравнения вызывается с двумя аргументами - указателями на сравниваемые элементы. В соответствии с тем, какое целое число она возвращает: меньшее нуля, равное нулю или большее нуля, первый аргумент считается меньшим, равным или большим по отношению ко второму. В сравнении не обязательно должен участвовать каждый байт, поэтому элементы, в дополнение к сравниваемым величинам, могут содержать произвольные данные.
Функция tsearch используется для построения дерева и доступа к нему. Аргумент key является указателем на искомые данные (ключ). Если в дереве есть узел с данными, равными искомым, то результатом функции служит указатель на этот узел, первым полем которого является указатель на данные. В противном случае в дерево вставляется узел со ссылкой на искомые данные и возвращается указатель на него. Отметим, что копируются только указатели, поэтому вызываемая программа сама должна хранить данные. Аргумент rootp указывает на переменную, которая является указателем на корень дерева. Значение NULL переменной, на которую указывает rootp, означает пустое дерево; в этом случае переменная устанавливается равной указателю на данные, которые окажутся в корне нового дерева.
Подобно функции tsearch, функция tfind осуществляет поиск данных в дереве, возвращая в случае успеха указатель на узел. Однако в случае неудачного поиска функция tfind возвращает пустой указатель NULL. Аргументы для функции tfind такие же, как и для функции tsearch.
Функция tdelete удаляет узел из бинарного дерева поиска. Аргументы такие же, как и для функции tsearch. Переменная, на которую указывает rootp, изменяется, если удаляемый узел является корнем дерева. Функция tdelete возвращает указатель на предка удаляемого узла или пустой указатель NULL, если узел не найден.
Функция twalk осуществляет обход бинарного дерева поиска. Аргумент root указывает на корень обрабатываемого дерева. Любой узел может быть использован в качестве корня для обхода соответствующего поддерева. Аргумент action - это функция, которая вызывается для каждого узла. Она в свою очередь имеет три аргумента. Первым аргументом служит адрес текущего узла. Второй аргумент - это значение перечисляемого типа данных, определенного во включаемом файле <search.h> как
