в двоичный справочник Д, необходимо

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

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

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

line();

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

line();

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

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

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

line();

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

добкор( Д, 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) ).

line();

        добавить( Д, X, Д1) :-

                        % Добавить Х на место корня

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