Арнольд Роббинс - Linux программирование в примерах
В области компьютерных наук были придуманы многочисленные динамические структуры данных, структуры, которые увеличивают и уменьшают свой размер по требованию и которые являются более гибкими, чем простые массивы, даже массивы, создаваемые и изменяемые динамически с помощью malloc() и realloc(). Массивы при добавлении или удалении новых элементов требуется также повторно сортировать.
Одной из таких структур является дерево двоичного поиска, которое мы для краткости будем называть просто «двоичным деревом» («binary tree»). Двоичное дерево хранит элементы в сортированном порядке, вводя их в дерево в нужном месте при их появлении. Поиск по двоичному дереву также осуществляется быстро, время поиска примерно такое же, как при двоичном поиске в массиве. В отличие от массивов, двоичные деревья не нужно каждый раз повторно сортировать с самого начала при добавлении к ним элементов.
У двоичных деревьев есть один недостаток. В случае, когда вводимые данные уже отсортированы, время поиска в двоичном дереве сводится ко времени линейного поиска. Техническая сторона этого вопроса должна иметь дело с тем, как двоичные деревья управляются внутренне, что вскоре будет описано.
Теперь не избежать некоторой формальной терминологии, относящейся к структурам данных. На рис. 14.1 показано двоичное дерево. В информатике деревья изображаются, начиная сверху и расширяясь вниз. Чем ниже спускаетесь вы по дереву, тем больше его глубина. Каждый объект внутри дерева обозначается как вершина (node). На вершине дерева находится корень дерева с глубиной 0. Внизу находятся концевые вершины различной глубины. Концевые вершины отличают по тому, что у них нет ответвляющихся поддеревьев (subtrees), тогда как у внутренних вершин есть по крайней мере одно поддерево. Вершины с поддеревьями иногда называют родительскими (parent), они содержат порожденные вершины (children).
Рис. 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 гарантирует, что этот указатель может быть приведен к указателю на указатель на что бы то ни было, что вы используете в качестве ключа. Вот обрывочный код для демонстрации, а затем мы покажем, как это работает:
struct employee { /* Из главы 6 */
char lastname[30];
char firstname[30];
long emp_id;
time_t start_date;
};
/* emp_name_id_compare --- сравнение по имени, затем no ID */
int emp_name_id_compare(const void *e1p, const void *e2p) {
/* ...также из главы 6, полностью представлено позже... */
}
struct employee key = { ... };
void *vp, *root;
struct employee *e;
/* ...заполнение данными... */
vp = tfind(&key, root, emp_name_id_compare);
if (vp != NULL) { /* it's there, use it */
e = *((struct employee**)vp); /* Получить хранящиеся в дереве данные */
/* использование данных в *е ... */
}
Как можно указатель на вершину использовать как указатель на указатель данных? Рассмотрим, как была бы реализована вершина двоичного дерева. В каждой вершине хранится по крайней мере указатель на элемент данных пользователя и указатели на потенциальные порожденные вершины справа и слева. Поэтому она должна выглядеть примерно так.
