найден после прохода по
Рисунок 9. 6. Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5-->8-->6.
Будем говорить, что непустое дерево дер( Лев, X, Прав) упорядочено слева направо, если
(1) все вершины левого поддерева Лев меньше X;
(2) все вершины правого поддерева Прав больше X;
(3) оба поддерева упорядочены.
Будем называть такое двоичное дерево двоичным справочником. Пример показан на Рисунок 9.6.
Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в двоичном справочнике всегда достаточно просмотреть не более одного поддерева. Экономия при поиске объекта Х достигается за счет того, что, сравнив Х с корнем, мы можем сразу же отбросить одно из поддеревьев. Например, пусть мы ищем элемент 6 в дереве, изображенной на Рисунок 9.6. Мы начинаем с корня 5, сравниваем 6 с 5, получаем 6 > 5. Поскольку все элементы данных в левом поддереве должны быть меньше, чем 5, единственная область, в которой еще осталась возможность найти элемент 6, - это правое поддерево. Продолжаем поиск в правом поддереве, переходя к вершине 8, и т.д.
Общий метод поиска в двоичном справочнике состоит в следующем:
line(); Для того, чтобы найти элемент Х в справочнике Д, необходимо:
- если Х - это корень справочника Д, то считать, что Х уже найден, иначе
- если Х меньше, чем корень, то искать Х в левом поддереве, иначе
- искать Х в правом поддереве;
- если справочник Д пуст, то поиск терпит неудачу.
Эти правила запрограммированы в виде процедуры, показанной на Рисунок 9.7. Отношение больше( X, Y), означает, что Х больше, чем Y. Если элементы, хранимые в дереве, - это числа, то под "больше, чем" имеется в виду просто Х > Y.
Существует способ использовать процедуру внутри также и для построения двоичного справочника. Например, справочник Д, содержащий элементы 5, 3, 8, будет построен при помощи следующей последовательности целей:
?- внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).
Д = дер( дер( Д1, 3, Д2), 5, дер( Д3, 8, Д4) ).
Переменные Д1, Д2, Д3 и Д4 соответствуют четырем неопределенным поддеревьям. Какими бы они ни были, все равно дерево Д будет содержать заданные элементы 3, 5 и 8. Структура построенного дерева зависит от того порядка, в котором указываются цели (Рисунок 9.8).
line(); внутри( X, дер( _, X, _ ).
внутри( X, дер( Лев, Корень, Прав) ) :-
больше( Корень, X), % Корень больше, чем Х
внутри( X, Лев). % Поиск в левом поддереве
внутри( X, дер( Лев, Корень, Прав) ) :-
больше( X, Корень), % Х больше, чем корень
внутри( X, Прав). % Поиск в правом поддереве
line();
