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

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

        внутри( X, S)

                       % Х  содержится в  S

        добавить( S, X, S1)

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

        удалить( S, X, S1)

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

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

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

line();

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

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

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

                доблист( Лев, X, Лев1)).

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

                доблист( Прав, X, Прав1).

line();

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