дерева, а не только на уровень листьев. Правила таковы:
уд( дер( 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).
Рис. 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).
