Рис. 14.1. Двоичное дерево
Чистые двоичные деревья отличаются тем, что каждая вершина содержит не более двух порожденных вершин. (Деревья с более чем двумя вершинами полезны, но не существенны для нашего обсуждения.) Порожденные вершины называются в этом случае левой и правой соответственно.
Деревья двоичного поиска отличаются еще и тем, что значения, хранящиеся в левой порожденной вершине, всегда меньше значения в родительской вершине, а значения, хранящиеся в правой порожденной вершине, всегда больше значения в родительской вершине. Это предполагает, что внутри дерева нет повторяющихся значений. Этот факт также объясняет, почему деревья не эффективны при работе с предварительно отсортированными данными: в зависимости от порядка сортировки, каждый новый элемент данных сохраняется либо только слева, либо только справа от находящегося впереди него элемента, образуя простой линейный список.
К двоичным деревьям применяют следующие операции:
Ввод
Добавление к дереву нового элемента.
Поиск
Нахождение элемента в дереве.
Удаление
Удаление элемента из дерева.
Прохождение (traversal)
Осуществление какой-либо операции с каждым хранящимся в дереве элементом. Прохождение дерева называют также обходом дерева (tree walk). Есть разнообразные способы «посещения» хранящихся в дереве элементов. Обсуждаемые здесь функции реализуют лишь один из таких способов. Мы дополнительно расскажем об этом позже.
14.4.2. Функции управления деревьями
Только что описанные операции соответствуют следующим функциям:
#include <search.h> /* XSI */
void *tsearch(const void *key, void **rootp,
int (*compare)(const void*, const void*));
void *tfind(const void *key, const void **rootp,
int (*compare)(const void*, const void*));
void *tdelete(const void *key, void **rootp,
int (*compare)(const void*, const void*));
typedef enum { preorder, postorder, endorder, leaf } VISIT;
void twalk(const void *root,
void (*action)(const void *nodep, const VISIT which,
const int depth));
void tdestroy(void *root, void (*free_node)(void *nodep)); /* GLIBC*/
Эти функции были впервые определены для System V, а теперь формально стандартизованы POSIX. Они следуют структуре других, которые мы видели в разделе 6.2 «Функции сортировки и поиска»: использование указателей
void*
для указания на произвольные типы данных и предоставляемые пользователем функции сравнения для определения порядка. Как и для
qsort()
и
bsearch()
, функции сравнения должны возвращать отрицательное/нулевое/положительное значение, когда
key
сравнивается со значением в вершине дерева.
14.4.3. Ввод элемента в дерево:
tsearch()
Эти процедуры выделяют память для вершин дерева. Для их использования с несколькими деревьями нужно предоставить им указатель на переменную
void*
, в которую они заносят адрес корневой вершины. При создании нового дерева инициализируйте этот указатель в
NULL
:
void *root = NULL; /* Корень нового дерева */
void *val; /* Указатель на возвращенные данные */
extern int my_compare(const void*, const void*); /* Функция сравнения */
extern char key[], key2[]; /* Значения для ввода в дерево */
val = tsearch(key, &root, my_compare);
/* Ввести в дерево первый элемент */
/* ...заполнить key2 другим значением. НЕ изменять корень... */
val = tsearch(key2, &root, my_compare);
/* Ввести в дерево последующий элемент */
Как показано, в переменной
root
должен быть
NULL
лишь в первый раз, после чего нужно оставить ее как есть. При каждом последующем вызове
tsearch()
использует ее для управления деревом.
Когда разыскиваемый
key
найден, как
tsearch()
, так и
tfind()
возвращают указатель на содержащую его вершину. Поведение функций различно, когда
key
не найден:
tfind()
возвращает
NULL
, a
tsearch()
вводит в дерево новое значение и возвращает указатель на него. Функции
tsearch()
и
tfind()
возвращают указатели на внутренние вершины дерева. Они могут использоваться в последующих вызовах в качестве значения root для работы с поддеревьями. Как мы вскоре увидим, значение key может быть указателем на произвольную структуру; он не ограничен символьной строкой, как можно было бы предположить из предыдущего примера.
Эти процедуры сохраняют лишь указатели на данные, использующиеся в качестве ключей. Соответственно это ваше дело управлять памятью для хранения значений данных, обычно с помощью
malloc()
.
ЗАМЕЧАНИЕ. Поскольку функции деревьев хранят указатели, тщательно позаботьтесь о том, чтобы не использовать
realloc()
для значений, которые были использованы в качестве ключей!
realloc()
может переместить данные, вернув новый указатель, но процедуры деревьев все равно сохранят висящие (dangling) указатели на старые данные.
14.4.4. Поиск по дереву и использование возвращенного указателя:
tfind()
и tsearch()
Функции
tfind()
и
tsearch()
осуществляют поиск в двоичном дереве по данному ключу. Они принимают тот же самый набор аргументов: ключ для поиска
key
. указатель на корень дерева,
rootp
; и
compare
, указатель на функцию сравнения. Обе функции возвращают указатель на вершину, которая соответствует
key
.
Как именно использовать указатель, возвращенный
tfind()
и
tsearch()
? Во всяком случае, на что именно он указывает? Ответ заключается в том, что он указывает на вершину в дереве. Это
внутренний тип; вы не можете увидеть, как он определен. Однако, POSIX гарантирует, что этот указатель может быть приведен к
указателю на указатель на что бы то ни было, что вы используете в качестве ключа. Вот обрывочный код для демонстрации, а затем мы покажем, как это работает:
