уд( дер( Лев, Кор, Прав), X, дер( Лев, Кор, Прав1) ) :-

больше( X, Кор),

уд( Прав, X, Прав1).

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

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

удмин( Лев, Y, Лев1).

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

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

добавить Х на место корня дерева (так, что Х станет новым корнем) или

если корень больше, чем X, то внести Х в левое поддерево, иначе - в правое поддерево.

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

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

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

Рис. 9. 14. Внесение Х в двоичный справочник в качестве корня.

Ответ мы получим, если учтем следующие ограничения на L1, L2:

L1 и L2 - двоичные справочники;

множество всех вершин, содержащихся как в L1, так и в L2, совпадает с множеством вершин справочника L;

все вершины из L1 меньше, чем X; все вершены из L2 больше, чем X.

Отношение, которое способно наложить все эти ограничения на L1, L2, - это как раз и есть наше отношение добкор. Действительно, если бы мы вводили Х в L на место корня, то поддеревьями результирующего дерева как раз и оказались бы L1 и L2. В терминах Пролога L1 и L2 должны быть такими, чтобы достигалась цель

добкор( L, X, дер( L1, X, L2) ).

Те же самые ограничения применимы к R1, R2:

добкор( R, X, дер( R1, X, R2) ).

добавить( Д, X, Д1) :- % Добавить Х на место корня

добкор( Д, X, Д1).

добавить( дер( L, Y, R), X, дер( L1, Y, R) ) :-

больше( Y, X), % Ввести Х в левое поддерево

добавить( L, X, L1).

добавить( дер( L, Y, R), X, дер( L, Y, R1) ) :-

больше( X, Y), % Ввести Х в правое поддерево

добавить( R, X, R1).

добкор( nil, X, дер( nil, X, nil) ). % Ввести Х в пустое дерево

добкор( дер( L, Y, R), Х, дер( L1, Х, дер( L2, Y, R) )) :-

больше( Y, X),

добкор( L, X, дер( L1, X, L2) ).

добкор( дep( L, Y, R), X, дep( дep( L, Y, R1), X, R2) ) :-

больше( X, Y),

добкор( R, X, дер( R1, X, R2) ).

Рис. 9. 15. Внесение элемента на произвольный уровень двоичного справочника.

На рис. 9.15 показана программа для "недетерминированного" добавления элемента в двоичный справочник.

Эта процедура обладает тем замечательным свойством, что в нее не заложено никаких ограничений на уровень дерева, в который вносится новый элемент. В связи с этим операцию добавить можно использовать "в обратном направлении" для удаления элемента из справочника. Например, приведенная ниже последовательность целей строит справочник Д, содержащий элементы 3, 5, 1, 6, а затем удаляет из него элемент 5, после чего получается справочник ДД:

добавить( nil, 3, Д1), добавить( Д1, 5, Д2),

добавить( Д2, 1, Д3), добавить( Д3, 6, Д),

добавить( ДД, 5, Д).

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

9. 4. Отображение деревьев

Так же, как и любые объекты данных в Прологе, двоичное дерево Т может быть непосредственно выведено на печать при помощи встроенной процедуры write. Однако цель