Читать книгу 📗 "Linux программирование в примерах - Роббинс Арнольд"

Рис. 14.1. Двоичное дерево

Чистые двоичные деревья отличаются тем, что каждая вершина содержит не более двух порожденных вершин. (Деревья с более чем двумя вершинами полезны, но не существенны для нашего обсуждения.) Порожденные вершины называются в этом случае левой и правой соответственно.

Деревья двоичного поиска отличаются еще и тем, что значения, хранящиеся в левой порожденной вершине, всегда меньше значения в родительской вершине, а значения, хранящиеся в правой порожденной вершине, всегда больше значения в родительской вершине. Это предполагает, что внутри дерева нет повторяющихся значений. Этот факт также объясняет, почему деревья не эффективны при работе с предварительно отсортированными данными: в зависимости от порядка сортировки, каждый новый элемент данных сохраняется либо только слева, либо только справа от находящегося впереди него элемента, образуя простой линейный список.

К двоичным деревьям применяют следующие операции:

Ввод

Добавление к дереву нового элемента.

Поиск

Нахождение элемента в дереве.

Удаление

Удаление элемента из дерева.

Прохождение (traversal)

Осуществление какой-либо операции с каждым хранящимся в дереве элементом. Прохождение дерева называют также обходом дерева (tree walk). Есть разнообразные способы «посещения» хранящихся в дереве элементов. Обсуждаемые здесь функции реализуют лишь один из таких способов. Мы дополнительно расскажем об этом позже.

14.4.2. Функции управления деревьями

Только что описанные операции соответствуют следующим функциям:

Эти функции были впервые определены для System V, а теперь формально стандартизованы POSIX. Они следуют структуре других, которые мы видели в разделе 6.2 «Функции сортировки и поиска»: использование указателей

для указания на произвольные типы данных и предоставляемые пользователем функции сравнения для определения порядка. Как и для и , функции сравнения должны возвращать отрицательное/нулевое/положительное значение, когда сравнивается со значением в вершине дерева.

14.4.3. Ввод элемента в дерево:

Эти процедуры выделяют память для вершин дерева. Для их использования с несколькими деревьями нужно предоставить им указатель на переменную

, в которую они заносят адрес корневой вершины. При создании нового дерева инициализируйте этот указатель в :

Как показано, в переменной

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

Когда разыскиваемый

найден, как , так и возвращают указатель на содержащую его вершину. Поведение функций различно, когда не найден: возвращает , a вводит в дерево новое значение и возвращает указатель на него. Функции и возвращают указатели на внутренние вершины дерева. Они могут использоваться в последующих вызовах в качестве значения root для работы с поддеревьями. Как мы вскоре увидим, значение key может быть указателем на произвольную структуру; он не ограничен символьной строкой, как можно было бы предположить из предыдущего примера.

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

.

14.4.4. Поиск по дереву и использование возвращенного указателя:

и

Функции

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

Как именно использовать указатель, возвращенный

и ? Во всяком случае, на что именно он указывает? Ответ заключается в том, что он указывает на вершину в дереве. Это внутренний тип; вы не можете увидеть, как он определен. Однако, POSIX гарантирует, что этот указатель может быть приведен к указателю на указатель на что бы то ни было, что вы используете в качестве ключа. Вот обрывочный код для демонстрации, а затем мы покажем, как это работает: