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


         

в двоичный справочник Д, необходимо


        удмин( дер( nil, Y, Прав), Y, Прав).

        удмин( дер( Лев, Кор, Прав), Y, дер( Лев1, Кор, Прав) ) :-

                удмин( Лев, Y, Лев1).


line();

Рис. 9. 13.  Удаление элемента из двоичного справочника.

line();

Для того, чтобы добавить Х в двоичный справочник Д, необходимо одно из двух:

  • добавить Х на место корня дерева (так, что Х станет новым корнем) или


  • если корень больше, чем X, то внести Х в левое поддерево, иначе - в правое поддерево.


  • line();

    Трудным моментом здесь является введение Х на место корня. Сформулируем эту операций в виде отношения

            добкор( Д, 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) ).

    line();

            добавить( Д, X, Д1) :-

                            % Добавить Х на место корня

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