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

граф. (b) направленный граф. Каждой дуге приписана ее стоимость.

Для представления направленного графа (рис. 9.18), применив функторы диграф и д (для дуг), получим

        G2 = диграф( [s, t, u, v],
                                 [д( s, t, 3), д( t, v, 1), д( t, u, 5), д( u, t, 2),
                                  д( v, u, 2) ] )

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

Еще один способ представления графа - связать с каждой вершиной список смежных с ней вершин. В этом случае граф превращается в список пар, каждая из которых состоит из вершины- плюс ее список смежности. Наши графы (рис. 9.18), например, можно представить как

        G1 = [ a->[b1, b->[a, c, d], c->[b, d], d->[b, c] ]

        G2 = [s->[t/3], t->[u/5, v/l], u->[t/2], v->[u/2]]

Здесь символы '->' и '/' - инфиксные операторы.

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

Для того, чтобы найти ациклический путь Р между А и Z в графе G, необходимо:

Если А = Z , то положить Р = [А], иначе найти ациклический путь Р1 из произвольной вершины Y в Z, а затем найти путь из А в Y, не содержащий вершин из Р1.

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

        путь1( А, Р1, G, Р)

Аргументы в соответствии с рис. 9.19 имеют следующий смысл: А - некоторая вершина,

обычное изображение дерева. (b) то же дерево,

Давайте определим процедуру

        отобр( Т)

так, чтобы она отображала дерево в форме, показанной на рис. 9.16. Принцип работы этой процедуры:

Для того, чтобы отобразить непустое дерево Т, необходимо:

(1)        отобразить правое поддерево дерева Т с отступом вправо на расстояние Н;

(2)        отпечатать корень дерева Т;

(3)        отобразить левое поддерево дерева Т с отступом вправо на расстояние Н.

Величина отступа Н, которую можно выбирать по желанию, - это дополнительный параметр при отображении деревьев. Введем процедуру

        отобр2( Т, Н)

печатающую дерево Т с отступом на Н пробелов от левого края листа. Связь между процедурами отобр и отобр2 такова:

        отобр( Т) :- отобр2( Т, 0).

На рис. 9.17 показана программа целиком. В этой программе предусмотрен сдвиг на 2 позиции для каждого уровня дерева. Описанный принцип отображения можно легко приспособить для деревьев других типов.

        отобр( Т) :-
                отобр2( Т, 0).

        отобр2( nil, _ ).

        отобр2( дер( L, X, R), Отступ) :-
                Отступ2 is Отступ + 2,
                отобр2( R, Отступ2),
                tab( Отступ), write( X), nl,
                отобр( L, Отступ2).

Более эффективная реализация процедуры быстрсорт

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

        быстрсорт( L, S) :-
                быстрсорт2( L, S-[ ] ).

Быстрая сортировка.

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

        УпорМеньш имеет вид A1-Z1
        УпорБольш имеет вид A2-Z2

Тогда конкатенации списков

        УпорМеньш и [ Х | УпорБольш]

будет соответствовать конкатенация пар

        A1-Z1    и     [ Х | A2]-Z2

В результате мы получим

        А1-Z2,     причем    Z1 = [ Х | А2]

Пустой список представляется парой Z-Z. Систематически вводя изменения в программу рис. 9.2, мы получим более эффективный способ реализации процедуры быстрсорт, показанный на рис. 9.3 под именем

        быстрсорт( Спис, УпорСпис) :-
                быстрсорт2( Спис, УпорСпис-[ ] ).

        быстрсорт2( [ ], Z-Z).

        быстрсорт2( [X | Хвост], A1-Z2) :-
                разбиение( X, Хвост, Меньш, Больш),
                быстрсорт2( Меньш, А1-[Х | A2] ),
                быстрсорт2( Больш, A2-Z2).

Двоичное дерево.

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

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

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

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

        внутри( X, Т)

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

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

Двоичные справочники: добавление и удаление элемента

Если мы имеем дело с динамически изменяемым множеством элементов данных, то нам может понадобиться внести в него новый элемент или удалить из него один из старых. В связи с этим набор основных операций, выполняемых над множеством S, таков:

        внутри( X, S)                        % Х  содержится в  S

        добавить( S, X, S1)              % Добавить  Х  к  S,  результат -  S1

        удалить( S, X, S1)                % Удалить  Х  из  S,  результат -  S1

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

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

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

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

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

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

Для того, чтобы найти элемент Х в справочнике Д, необходимо: если Х - это корень справочника Д, то считать, что Х уже найден, иначе если Х меньше, чем корень, то искать Х в левом поддереве, иначе искать Х в правом поддереве; если справочник Д пуст, то поиск терпит неудачу. 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).

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

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

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

Графы

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

        связь( а, b).
        связь( b, с).
        . . .

        дуга( s, t, 3).
        дуга( t, v, 1).
        дуга( u, t, 2).
        . . .

Другой способ - весь граф представлять как один объект. В этом случае графу соответствует пара множеств - множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро - парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра - функтор р. Тогда (ненаправленный) граф рис. 9.18 примет вид:

        G1 = граф( [a, b, c, d],
                            [р( а, b), р( b, d), р( b, с), p( c, d)] )

Литература

В этой главе мы занимались такими важными темами, как сортировка и работа со структурами данных для представления множеств. Общее описание структур данных, а также алгоритмов, запрограммированных в данной главе, можно найти, например, в Aho, Hopcroft and Ullman (1974, 1983) или Baase (1978). В литературе рассматривается также поведение этих алгоритмов, особенно их временная сложность. Хороший и краткий обзор соответствующих алгоритмов и результатов их математического анализа можно найти в Gonnet (1984).

Прологовская программа для внесения нового элемента на произвольный уровень дерева (раздел 9.3) была впервые показана автору М. Ван Эмденом (при личном общении).

Aho А. V., Hopcroft J. Е. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. - М-: Мир, 1979.]

Aho А. V., Hopcroft J. Е. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.

Baase S. (1978). Computer Algorithms. Addison-Wesley.

Gonnet G. H. (1984). Handbook of Algorithms and Data Structures. Addison-Wesley.

%  Построение остовного дерева графа
%
%  Деревья и графы представлены списками
%  своих ребер, например:
%            Граф = [а-b, b-с, b-d, c-d]

        остдерево( Граф, Дер) :-                            % Дер - остовное дерево Граф'а
                принадлежит( Ребро, Граф),
                расширить( [Ребро], Дер, Граф).

        расширить( Дер1, Дер, Граф) :-
                добребро( Дер1, Дер2, Граф),
                расширить( Дер2, Дер, Граф).

        расширить( Дер, Дер, Граф) :-
                not добребро( Дер, _, Граф).
                                        % Добавление любого ребра приводит к циклу

        добребро( Дер, [А-В | Дер], Граф) :-
                смеж( А, В, Граф),                            % А и В - смежные вершины
                вершина( А, Дер).                             % А содержится в Дер
                не вершина( В, Дер).                        % А-В не порождает цикла

        смеж( А, В, Граф) :-
                принадлежит ( А-В, Граф);
                принадлежит ( В-А, Граф).

        вершина( А, Граф) :-                                 % А содержится в графе, если
                смеж( А, _, Граф).                              % А смежна какой-нибудь вершине

Pис. 9. 22.  Построение остовного дерева: алгоритмический подход.
Предполагается, что Граф - связный граф.

связный граф; Дер1 и Дер - два подмножества G, являющиеся деревьями. Дер - остовное дерево графа G, полученное добавлением некоторого (может быть пустого) множества ребер из G к Дер1. Можно сказать, что "Дер1 расширено до Дер".

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

(1)        Т является остовным деревом графа G, если Т - это подмножество графа G и Т - дерево и Т "накрывает" G, т.е. каждая вершина из G содержится также в Т.

(2)        Множество ребер Т есть дерево, если Т - связный граф и Т не содержит циклов.

Эти определения можно сформулировать на Прологе (с использованием нашей программы путь из предыдущего раздела) так, как показано на рис. 9.23. Следует, однако, заметить, что эта программа в таком ее виде не представляет практического интереса из-за своей неэффективности.

%  Построение остовного дерева
%  Графы и деревья представлены списками ребер.

        остдерево( Граф, Дер) :-
                подмнож( Граф, Дер),
                дерево( Дер),
                накрывает( Дер, Граф).

        дерево( Дер) :-
                связи( Дер),
                not имеетцикл( Дер).

        связи( Дер) :-
                not ( вершина( А, Дер), вершина( В, Дер),
                            not путь( А, А, Дер, _ ) ).

        имеетцикл( Дер) :-
                смеж( А, В, Дер),
                путь( А, В, Дер, [А, X, Y | _ ).                     % Длина пути > 1

        накрывает( Дер, Граф) :-
                not ( вершина( А, Граф), not вершина( А, Дер) ).

        подмнож( [ ], [ ]).

        подмнож( [ Х | L], S) :-
                подмнож( L, L1),
                ( S = L1; S = [ Х | L1] ).

Поиск в графе граф ациклического пути путь из а в z.

На рис. 9.20 программа показана полностью. Здесь принадлежит - отношение принадлежности элемента списку. Отношение

        смеж( X, Y, G)

означает, что в графе G существует дуга, ведущая из Х в Y. Определение этого отношения зависит от способа представления графа. Если G представлен как пара множеств (вершин и ребер)

        G = граф( Верш, Реб)

то

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

        гамильтон( Граф, Путь) :-
                путь( _, _, Граф, Путь),
                всевершины( Путь, Граф).

        всевершины( Путь, Граф) :-
                not (вершина( В, Граф),
                        not принадлежит( В, Путь) ).

Здесь вершина( В, Граф) означает: В - вершина графа Граф.

Каждому пути можно приписать его стоимость. Стоимость пути равна сумме стоимостей входящих в него дуг. Если дугам не приписаны стоимости, то тогда, вместо стоимости, говорят о длине пути.

Для того, чтобы наши отношения путь и путь1 могли работать со стоимостями, их нужно модифицировать, введя дополнительный аргумент для каждого пути:

        путь( А, Z, G, Р, С)
        путь1( A, P1, C1, G, Р, С)

Здесь С - стоимость пути Р, a C1 - стоимость пути Р1. В отношении смеж также появится дополнительный аргумент, стоимость дуги. На рис. 9.21 показана программа поиска пути, которая строит путь и вычисляет его стоимость.

        путь( А, Z, Граф, Путь, Ст) :-
                путь1( A, [Z], 0, Граф, Путь, Ст).

        путь1( А, [А | Путь1], Ст1, Граф, [А | Путь1], Ст).

        путь1( А, [Y | Путь1], Ст1, Граф, Путь, Ст) :-
                смеж( X, Y, СтXY, Граф),
                not принадлежит( X, Путь1),
                Ст2 is Ст1 + СтXY,
                путь1( А, [ X, Y | Путь1], Ст2, Граф, Путь, Ст).

Построение остовного дерева: "декларативный подход".

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

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

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

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

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

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

        внутри( X, nil)

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

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

        внутри( X, Т)

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

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

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

        внутри( а, Т)

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

        внутри( d, Т)

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

        внутри( е, Т)

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

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

Представление множеств двоичными деревьями

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

        принадлежит X, [X | L] ).

        принадлежит X, [ Y | L] ) :-
                принадлежит( X, L).

Для того, чтобы найти Х в списке L, эта процедура последовательно просматривает список элемент за элементом, пока ей не встретится либо элемент X, либо конец списка. Для длинных списков такой способ крайне неэффективен.

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

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

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

        а( b, с( d) )

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

Представление списков. Сортировка

        ничего_не_делать

в качестве символа, обозначающего пустой список, и атом

        затем

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

        :- ор( 500, xfy, затем).

Список

        [ войти, сесть, поужинать]

можно было бы тогда записать как

        войти затем сесть затем поужинать
        затем ничего_не_делать

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

        принадлежит ( X, L)
        конк( L1, L2, L3)
        удалить( X, L1, L2)

запрограммированные нами в специальной прологовской нотации, легко поддаются перепрограммированию в различные системы обозначений, выбранные пользователем. Например, отношение конк транслируется на язык "затем - ничего_не_делать" следующим образом. Определение, которое мы использовали до сих пор, имеет вид

        конк( [ ], L, L).

        конк( [X | L1], L2, [X | L3] ) :-
                конк( L1, L2, L3).

В новой системе обозначений оно превращается в

        конк( ничего_не_делать, L, L).

        конк( Х затем L1, L2, Х затем L3) :-
                конк(L1, L2, L3).

Этот пример показывает, как легко наши определения отношений над списками обобщаются на весь класс структур этого типа. Решение о том, какой именно способ записи списков будет использоваться в той или иной программе, следует принимать в соответствии с тем смыслом, который мы придаем списку в каждом конкретном случае. Если, например, список - это просто множество элементов, то наиболее удобна обычная прологовская нотация, поскольку в ней непосредственно выражается то, что программист имел в виду. С другой стороны, некоторые типы выражений также можно трактовать как своего рода списки. Например, для конъюнктов в исчислении высказываний подошло бы следующее спископодобное представление: истина соответствует пустому списку, & - оператор для соединения головы с хвостом, определяемый, например, как
           
            :- ор( 300, xfy, &)

Конъюнкция членов а, b, и с выглядела бы тогда как

            а & b & с & истина

Все приведенные примеры базируются, по существу, на одной и той же структуре, представляющей список. Однако в гл. 8 мы рассмотрели существенно другой способ, влияющий на эффективность вычислений. Уловка состояла в том, что список представлялся в виде пары списков, являясь их "разностью". Было показано, что такое представление приводит к очень эффективной реализации отношения конкатенации.

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

В данной главе мы изучали

Сортировка списка процедурой быстрсорт.

        встав( X, [Y | УпорСпис], [Y | УпорСпис1]):-
                больше( X, Y),  !,
                встав( X, УпорСпис, УпорСпис1).

        встав( X, УпорСпис, [X | УпорСпис] ).

Для того, чтобы упорядочить непустой список  L,   необходимо:

(1)        Удалить из списка  L  какой-нибудь элемент  Х  и разбить оставшуюся часть на два списка, называемые Меньш и Больш, следующим образом: все элементы большие, чем  X,   принадлежат списку Больш, остальные - списку Меньш.

(2)        Отсортировать список Меньш, результат - список УпорМеньш.

(3)        Отсортировать список Больш, результат - список УпорБольш.

(4)        Получить результирующий упорядоченный список как конкатенацию списков УпорМеньш и [ Х | УпорБольш].

Заметим, что если исходный список пуст, то результатом сортировки также будет пустой список. Реализация быстрой сортировки на Прологе показана на рис. 9.2. Здесь в качестве элемента   X,  удаляемого из списка, всегда выбирается просто голова этого списка. Разбиение на два списка запрограммировано как отношение с четырьмя аргументами:

        разбиение( X, L, Больш, Меньш).

Временная сложность нашего алгоритма зависит от того, насколько нам повезет при разбиении сортируемого списка. Если списки всегда разбиваются на два списка примерно равной длины, то процедура сортировки имеет временную сложность порядка nlogn, где  n  - длина исходного списка. Если же, наоборот, разбиение всегда приводит к тому, что один из списков оказывается значительно больше другого, то сложность будет порядка  n2.   Анализ показывает, что, к счастью, средняя производительность быстрой сортировки ближе к лучшему случаю, чем к худшему.

Программу, показанную на рис. 9.2, можно усовершенствовать, если реализовать операцию конкатенации более эффективно. Напомним, что конкатенация

        быстрсорт( [ ], [ ] ).

        быстрсорт( [X | Хвост], УпорСпис) :-
                разбиение( X, Хвост, Меньш, Больш),
                быстрсорт( Меньш, УпорМеньш),
                быстрсорт( Больш, УпорБольш),
                конк( УпорМеньш, [X | УпорБольш], УпорСпис).

        разбиение( X, [ ], [ ], [ ] ).

        разбиение( X, [Y | Хвост], [Y | Меньш], Больш ) :-
                больше( X, Y),  !,
                разбиение( X, Хвост, Меньш, Больш).

        разбиение( X, [Y | Хвост], Меньш, [Y | Больш] ) :-
                разбиение( X, Хвост, Меньш, Больш).

        конк( [ ], L, L).

        конк( [X | L1], L2, [X | L3] ) :-
                конк( L1, L2, L3 ).

Удаление элемента из двоичного справочника.

Для того, чтобы добавить Х в двоичный справочник Д, необходимо одно из двух: добавить Х на место корня дерева (так, что Х станет новым корнем) или если корень больше, чем X, то внести Х в левое поддерево, иначе - в правое поддерево. line();

Трудным моментом здесь является введение Х на место корня. Сформулируем эту операций в виде отношения

        добкор( Д, X, X1)

где Х - новый элемент, вставляемый вместо корня в Д, а Д1 - новый справочник с корнем Х. На рис. 9.14 показано, как соотносятся X, Д и Д1. Остается вопрос: что из себя представляют поддеревья L1 и L2 (или, соответственно, R1 и R2) на рис. 9.14?

Удаление x из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента x.

операции добавления листа:

        удлист( Д1, X, Д2) :-
                доблист( Д2, X, Д1).

К сожалению, если Х - это внутренняя вершина, то такой способ не работает, поскольку возникает проблема, иллюстрацией к которой служит рис. 9.11. Вершина Х имеет два поддерева Лев и Прав. После удаления вершины Х в дереве образуется "дыра", и поддеревья Лев и Прав теряют свою связь с остальной частью дерева. К вершине А оба эти поддерева присоединить невозможно, так как вершина А способна принять только одно из них.

Если одно из поддеревьев Лев и Прав пусто, то существует простое решение: подсоединить к А непустое поддерево. Если же оба поддерева непусты,

Наша процедура изображает дерево, ориентируя

Напишите процедуру слияния двух упорядоченных

Определим отношение добавить. Простейший способ: ввести новый элемент на самый нижний уровень дерева, так что он станет его листом. Место, на которое помещается новый элемент, выбрать таким образом, чтобы не нарушить упорядоченность дерева. На рис. 9.9 показано, какие изменения претерпевает дерево в процессе введения в него новых элементов. Назовем такой метод вставления элемента в множество

        доблист( Д, X, Д1)

Правила добавления элемента на уровне листьев таковы: Результат добавления элемента Х к пустому дереву есть дерево дер( nil, X, nil). Если Х совпадает с корнем дерева Д, то Д1 = Д (в множестве не допускается дублирования элементов). Если корень дерева Д больше, чем X, то Х вносится в левое поддерево дерева Д; если корень меньше, чем X, то Х вносится в правое поддерево.

Теперь рассмотрим операцию удалить. Лист дерева удалить легко, однако удалить какую-либо внутреннюю вершину - дело не простое. Удаление листа можно на самом деле определить как операцию, обратную

Введение в двоичный справочник...

        доблист( nil, X, дер( nil, X, nil) ).

        доблист( дер( Лев, Х, Прав), Х, дер( Лев, Х, Прав) ).

        доблист( дер( Лев, Кор, Прав), Х, дер( Лев1, Кор, Прав)) :-
                больше( Кор, X),
                доблист( Лев, X, Лев1)).

        доблист( дер( Лев, Кор, Прав), Х, дер( Лев, Кор, Прав1)) :-
                больше( X, Кор),
                доблист( Прав, X, Прав1).

Заполнение пустого места после удаления x.

то можно использовать следующую идею (рис. 9.12): если самую левую вершину Y поддерева Прав переместить из ее текущего положения вверх и заполнить ею пробел, оставшийся после X, то упорядоченность дерева не нарушится. Разумеется, та же идея сработает и в симметричном случае, когда перемещается самая правая вершина поддерева Лев.

На рис. 9.13 показана программа, реализующая операцию удаления элементов в соответствии с изложенными выше соображениями. Основную работу по перемещению самой левой вершины выполняет отношение

        удмин( Дер, Y, Дер1)

Здесь Y - минимальная (т.е. самая левая) вершина дерева Дер, а Дер1 - то, во что превращается дерево Дер после удаления вершины Y.

        уд( дер( nil, X, Прав), X, Прав).

        уд( дер( Лев, X, nil), X, Лев).

        уд( дер( Лев, Х, Прав), X, дер( Лев,Y, Прав1) ) :-
                удмин( Прав, Y, Прав1).

        уд( дер( Лев, Кор, Прав), X, дер( Лев1, Кор, Прав) ) :-
                больше( Кор, X),
                уд( Лев, X, Лев1).

        уд( дер( Лев, Кор, Прав), X, дер( Лев, Кор, Прав1) ) :-
                больше( X, Кор),
                уд( Прав, X, Прав1).

        удмин( дер( nil, Y, Прав), Y, Прав).

        удмин( дер( Лев, Кор, Прав), Y, дер( Лев1, Кор, Прав) ) :-
                удмин( Лев, Y, Лев1).