Программирование на языке Пролог для искусственного интеллекта




Заполнение пустого места после удаления x.



  Заполнение пустого места после удаления X.



то можно использовать следующую идею (рис. 9.12): если самую левую вершину Y поддерева Прав переместить из ее текущего положения вверх и заполнить ею пробел, оставшийся после X, то упорядоченность дерева не нарушится. Разумеется, та же идея сработает и в симметричном случае, когда перемещается самая правая вершина поддерева Лев.

На рис. 9.13 показана программа, реализующая операцию удаления элементов в соответствии с изложенными выше соображениями. Основную работу по перемещению самой левой вершины выполняет отношение

        удмин( Дер, Y, Дер1)

Здесь Y - минимальная (т.е. самая левая) вершина дерева Дер, а Дер1 - то, во что превращается дерево Дер после удаления вершины Y.

Существует другой, элегантный способ реализация операции добавить и удалить. Отношение добавить можно сделать недетерминированным в том смысле, что новый элемент вводится на произвольный уровень дерева, а не только на уровень листьев. Правила таковы:

line();

        уд( дер( 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).

line();









Начало  Назад  Вперед