добкор( Д, 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) ).
line();
Рис. 9. 15. Внесение элемента на произвольный уровень двоичного справочника.
На рис. 9.15 показана программа для "недетерминированного" добавления элемента в двоичный справочник.
Эта процедура обладает тем замечательным свойством, что в нее не заложено никаких ограничений на уровень дерева, в который вносится новый элемент. В связи с этим операцию добавить
можно использовать "в обратном направлении" для удаления элемента из справочника. Например, приведенная ниже последовательность целей строит справочник Д, содержащий элементы 3, 5, 1, 6, а затем удаляет из него элемент 5, после чего получается справочник ДД:
добавить( nil, 3, Д1), добавить( Д1, 5, Д2),
добавить( Д2, 1, Д3), добавить( Д3, 6, Д),
добавить( ДД, 5, Д).
Назад | Содержание
| Вперёд