Двоичное дерево либо пусто, либо состоит из следующих трех частей:

• корень
• левое поддерево
• правое поддерево

Корень может быть чем угодно, а поддеревья должны сами быть двоичными деревьями. На рис. 9.4 показано представление множества [а, b, с, d] двоичным деревом. Элементы множества хранятся в виде вершин дерева. Пустые поддеревья на рис. 9.4 не показаны. Например, вершина b имеет два поддерева, которые оба пусты.

Существует много способов представления двоичных деревьев на Прологе. Одна из простых возможностей - сделать корень главным функтором соответствующего терма, а поддеревья - его аргументами. Тогда дерево рис. 9.4 примет вид

        а( b, с( d) )

Такое представление имеет среди прочих своих недостатков то слабое место, что для каждой вершины дерева нужен свой функтор. Это может привести к неприятностям, если вершины сами являются структурными объектами.

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

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

• Пусть атом nil представляет пустое дерево.
• В качестве функтора примем дер, так что дерево с корнем X, левым поддеревом L и правым поддеревом R будет иметь вид терма дер( L, X, R) (см. рис. 9.5).

В этом представлении дерево рис. 9.4 выглядит как

        дер( дер( nil, b, nil), a,
                    дер( дер( nil, d, nil), с, nil) ).

Теперь рассмотрим отношение принадлежности, которое будем обозначать внутри. Цель

        внутри( X, Т)

истинна, если Х есть вершина дерева Т. Отношение внутри можно определить при помощи следующих правил:

Х есть вершина дерева Т, если

• корень дерева Т совпадает с X, или
• Х - это вершина из левого поддерева, или
• Х - это вершина из правого поддерева.

Рис. 9. 5.  Представление двоичных деревьев.

Эти правила непосредственно транслируются на Пролог следующим образом:

        внутри( X, дер( -, X, -) ).

        внутри( X, дер( L, -, -) ) :-
                внутри( X, L).

        внутри( X, дер( -, -, R) ) :-
                внутри( X, R).

Очевидно, что цель

        внутри( X, nil)

терпит неудачу при любом X.

Посмотрим, как ведет себя наша процедура. Рассмотрим рис. 9.4. Цель

        внутри( X, Т)

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

        Х = а; Х = b; Х = с; X = d

Теперь рассмотрим вопрос об эффективности. Цель

        внутри( а, Т)

достигается сразу же после применения первого предложения процедуры внутри. С другой стороны, цель

        внутри( d, Т)

будет успешно достигнута только после нескольких рекурсивных обращений. Аналогично цель

        внутри( е, Т)

потерпит неудачу только после того, как будет просмотрено все дерево в результате рекурсивного применения процедуры внутри ко всем поддеревьям дерева Т.

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

Рис. 9. 6.  Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5-->8-->6.

Будем говорить, что непустое дерево дер( Лев, X, Прав) упорядочено слева направо, если

(1)        все вершины левого поддерева Лев меньше X;

(2)        все вершины правого поддерева Прав больше X;

Будем называть такое двоичное дерево двоичным справочником. Пример показан на рис. 9.6.

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

Для того, чтобы найти элемент Х в справочнике Д, необходимо:

• если Х - это корень справочника Д, то считать, что Х уже найден, иначе
• если Х меньше, чем корень, то искать Х в левом поддереве, иначе
• искать Х в правом поддереве;
• если справочник Д пуст, то поиск терпит неудачу.

Эти правила запрограммированы в виде процедуры, показанной на рис. 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).

        внутри( X, дер( _, X, _ ).

        внутри( X, дер( Лев, Корень, Прав) ) :-
                больше( Корень, X),               % Корень больше, чем Х
                внутри( X, Лев).                     % Поиск в левом поддереве

        внутри( X, дер( Лев, Корень, Прав) ) :-
                больше( X, Корень),               % Х больше, чем корень
                внутри( X, Прав).                   % Поиск в правом поддереве

Рис. 9. 7.  Поиск элемента Х в двоичном справочнике.

Рис. 9. 8.  (а)     Дерево Д, построенное как результат достижения целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).     (b)    Дерево, полученное при другом порядке целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).

Мы говорим, что дерево (приближенно) сбалансировано, если для каждой вершины дерева соответствующие два поддерева содержат примерно равное число элементов. Если дерево хорошо сбалансировано, то его глубина пропорциональна log n. В этом случае мы говорим, что дерево имеет логарифмическую сложность. Сбалансированный справочник лучше списка настолько же, насколько log n меньше n. К сожалению, это верно только для приближенно сбалансированного дерева. Если происходит разбалансировка дерева, то производительность падает. В случае полностью разбалансированных деревьев, дерево фактически превращается в список. Глубина дерева в этом случае равна n, а производительность поиска оказывается столь же низкой, как и в случае списка. В связи с этим мы всегда заинтересованы в том, чтобы справочники были сбалансированы. Методы достижения этой цели мы обсудим в гл. 10.

Упражнения

9. 9.    Определите предикаты

        двдерево( Объект)
        справочник( Объект)

распознающие, является ли Объект двоичным деревом или двоичным справочником соответственно. Используйте обозначения, введенные в данном разделе.