6.4. Поиск по бинарному дереву

6.4.1. Бинарное дерево поиска

Если массив ключей динамически изменяется за счёт удалений и вставок, то нецелесообразно тратить время на постоянное

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

Напомним, что узлы бинарного дерева — записи, которые помимо поля значения , указателяна левое поддерево и указателяна правое поддерево содержат также ключевое поле; если какое-нибудь из поддеревьев отсутствует, соответствующий указатель имеет значение(оба поддерева заведомо отсутствуют у листьев дерева, то есть у концевых узлов). Указатель на искомую запись бинарного дерева обозначим через; указатель на корень дерева обозначим через(см. п. 2.5).

Бинарное дерево является деревом поиска, если для каждого узла его левый потомок имеет меньшее значение ключа, а правый — не меньшее:

,

причём такое же неравенство распространяется от непосредственных потомков узла на все узлыиего левого и правого поддерева соответственно:

.

На рис. 41 приведено бинарное дерево поиска.

Рис. 41.

Бинарное дерево поиска обладает следующими важными свойствами:

- максимальное значение ключа находится в крайнем правом узле; переход к этому узлу из корня производится по ссылкам на правого потомка до тех пор, пока такие ссылки не пусты;

- минимальное значение ключа находится в крайнем левом узле; переход к этому узлу из корня производится по ссылкам на левого потомка до тех пор, пока такие ссылки не пусты;

- для перехода к узлу с непосредственно следующим за значением ключа нужно сначала перейти к правому потомку, а далее смещаться по ссылкам на левого потомка до тех пор, пока эти ссылки не пусты;

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

6.4.2. Поиск и вставка в дереве поиска.

Рассмотрим поиск по дереву поиска указателя на узел с заданным значением ключасо вставкой новой записи, если ключ не найден.

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

Циклическая реализация алгоритма содержит следующие этапы:

╔

Ш1. Начальные установки: .

Ш2. Сравнение:

если , то

переход к шагу Ш3;

если , то

переход к шагу Ш4;

если , то

поиск завершается.

Ш3. Переход к левому поддереву:

если , то

;

переход к Ш2;

иначе

переход к Ш5.

Ш4. Переход к правому поддереву:

если , то

;

переход к Ш2;

иначе

переход к Ш5.

Ш5. Вставка ключа в дерево при неудачном поиске:

1. из списка свободной памяти выбирается адрес

и заменяется там на следующий;

2. указателю вставляемой записи с ключом

присваивается выбранный адрес и вставляемая

запись делается концевым узлом:

;

;

;

3) устанавливается связь с узлом, до этого бывшим

концевым:

если было , то

,

иначе

.

╚

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

Среднее число сравнений при поиске в дереве с узлами имеет порядок(логарифм натуральный). Алгоритм может быть использован для сортировки ключей, и особенно эффективен при совмещении поиска и сортировки.

NB: Алгоритм вставки элемента в бинарное дерево поиска, начиная с корня для исходно пустого дерева, обеспечивает сохранение следующего условия: Все ключи, которые больше расположенного в данном узле, попадают в ходе вставок в его правое поддерево, а ключи, которые меньше — в левое.

Префиксная стратегия обхода дерева (см. п. 2.5) позволяет выводить ключи в порядке возрастания. Это даёт ещё один механизм сортировки — сортировку обходом дерева поиска.