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



Рисунок 9 12 Заполнение пустого места после удаления X



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

fig9_12.gif (1831 bytes)

то можно использовать следующую идею (Рисунок 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();



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