У двоичных деревьев есть один недостаток. В случае, когда вводимые данные уже отсортированы, время поиска в двоичном дереве сводится ко времени линейного поиска. Техническая сторона этого вопроса должна иметь дело с тем, как двоичные деревья управляются внутренне, что вскоре будет описано.
Теперь не избежать некоторой формальной терминологии, относящейся к структурам данных. На рис. 14.1 показано двоичное дерево. В информатике деревья изображаются, начиная сверху и расширяясь вниз. Чем ниже спускаетесь вы по дереву, тем больше его глубина. Каждый объект внутри дерева обозначается как вершина (node). На вершине дерева находится корень дерева с глубиной 0. Внизу находятся концевые
вершины различной глубины. Концевые вершины отличают по тому, что у них нет ответвляющихся поддеревьев (subtrees), тогда как у внутренних вершин есть по крайней мере одно поддерево. Вершины с поддеревьями иногда называют родительскими (parent), они содержат порожденные вершины (children).
Рис. 14.1. Двоичное дерево
Чистые двоичные деревья отличаются тем, что каждая вершина содержит не более двух порожденных вершин. (Деревья с более чем двумя вершинами полезны, но не существенны для нашего обсуждения.) Порожденные вершины называются в этом случае левой и правой соответственно.
Деревья двоичного поиска отличаются еще и тем, что значения, хранящиеся в левой порожденной вершине, всегда меньше значения в родительской вершине, а значения, хранящиеся в правой порожденной вершине, всегда больше значения в родительской вершине. Это предполагает, что внутри дерева нет повторяющихся значений. Этот факт также объясняет, почему деревья не эффективны при работе с предварительно отсортированными данными: в зависимости от порядка сортировки, каждый новый элемент данных сохраняется либо только слева, либо только справа от находящегося впереди него элемента, образуя простой линейный список.
К двоичным деревьям применяют следующие операции:
Ввод
Добавление к дереву нового элемента.
Поиск
Нахождение элемента в дереве.
Удаление
Удаление элемента из дерева.
Прохождение (traversal)
Осуществление какой-либо операции с каждым хранящимся в дереве элементом. Прохождение дерева называют также обходом дерева (tree walk). Есть разнообразные способы «посещения» хранящихся в дереве элементов. Обсуждаемые здесь функции реализуют лишь один из таких способов. Мы дополнительно расскажем об этом позже.
14.4.2. Функции управления деревьями
Только что описанные операции соответствуют следующим функциям:
Эти функции были впервые определены для 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 гарантирует, что этот указатель может быть приведен к указателю на указатель на что бы то ни было, что вы используете в качестве ключа. Вот обрывочный код для демонстрации, а затем мы покажем, как это работает: