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

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

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

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

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

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

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

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

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

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

уд( дер( nil, X, Прав), X, Прав).

уд( дер( Лев, X, nil), X, Лев).

уд( дер( Лев, X, Прав), X, дер( Лев,Y, Прав1) ) :-

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

уд( дер( Лев, Кор, Прав), X, дер( Лев1, Кор, Прав) ) :-

больше( Кор, X),

уд( Лев, X, Лев1).

уд( дер( Лев, Кор, Прав), X, дер( Лев, Кор, Прав1) ) :-

больше( X, Кор),

уд( Прав, X, Прав1).

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

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

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

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

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

добкор( Д, X, X1)

где X — новый элемент, вставляемый вместо корня в Д, а Д1 — новый справочник с корнем X. На рис. 9.14 показано, как соотносятся X, Д и Д1. Остается вопрос: что из себя представляют поддеревья L1 и L2 (или, соответственно, R1 и R2) на рис. 9.14?

Рис. 9.14. Внесение X в двоичный справочник в качестве корня.

Ответ мы получим, если учтем следующие ограничения на L1, L2:

• L1 и L2 — двоичные справочники;

• множество всех вершин, содержащихся как в L1, так и в L2, совпадает с множеством вершин справочника L;

• все вершины из L1 меньше, чем X; все вершены из L2 больше, чем X.

Отношение, которое способно наложить все эти ограничения на L1, L2, — это как раз и есть наше отношение добкор. Действительно, если бы мы вводили X в L на место корня, то поддеревьями результирующего дерева как раз и оказались бы L1 и L2. В терминах Пролога L1 и L2 должны быть такими, чтобы достигалась цель

добкор( L, X, дер( L1, X, L2) ).

Те же самые ограничения применимы к R1, R2:

добкор( R, X, дер( R1, X, R2) ).

На рис. 9.15 показана программа для "недетерминированного" добавления элемента в двоичный справочник.

добавить( Д, X, Д1) :- % Добавить X на место корня

добкор( Д, X, Д1).

добавить( дер( L, Y, R), X, дер( L1, Y, R) ) :-

больше( Y, X), % Ввести X в левое поддерево

добавить( L, X, L1).

добавить( дер( L, Y, R), X, дер( L, Y, R1) ) :-

больше( X, Y), % Ввести X в правое поддерево

добавить( R, X, R1).

добкор( nil, X, дер( nil, X, nil) ). % Ввести X в пустое дерево

добкор( дер( L, Y, R), X, дер( L1, X, дер( 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) ).

Рис. 9.15. Внесение элемента на произвольный уровень двоичного справочника.

Эта процедура обладает тем замечательным свойством, что в нее не заложено никаких ограничений на уровень дерева, в который вносится новый элемент. В связи с этим операцию добавить можно использовать "в обратном направлении" для удаления элемента из справочника. Например, приведенная ниже последовательность целей строит справочник Д, содержащий элементы 3, 5, 1, 6, а затем удаляет из него элемент 5, после чего получается справочник ДД:

добавить( nil, 3, Д1), добавить( Д1, 5, Д2),

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

добавить( ДД, 5, Д).

Так же, как и любые объекты данных в Прологе, двоичное дерево T может быть непосредственно выведено на печать при помощи встроенной процедуры write. Однако цель

write( T)

хотя и отпечатает всю информацию, содержащуюся в дереве, но действительная структура дерева никак при этом не будет выражена графически. Довольно утомительная работа — пытаться представить себе структуру дерева, рассматривая прологовский терм, которым она представлена. Поэтому во многих случаях желательно иметь возможность отпечатать дерево в такой форме, которая графически соответствует его структуре.

Существует относительно простой способ это сделать. Уловка состоит в том, чтобы изображать дерево растущим слева направо, а не сверху вниз, как обычно. Дерево нужно повернуть влево таким образом, чтобы корень стал его крайним слева элементом, а листья сдвинулись вправо (рис. 9.16).

Рис. 9.16. (а) Обычное изображение дерева. (b) То же дерево, отпечатанное процедурой отобр(дуги добавлены для ясности).

Давайте определим процедуру

отобр( T)

так, чтобы она отображала дерево в форме, показанной на рис. 9.16. Принцип работы этой процедуры:

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

(1) отобразить правое поддерево дерева T с отступом вправо на расстояние H;

(2) отпечатать корень дерева T;

(3) отобразить левое поддерево дерева T с отступом вправо на расстояние H.

Величина отступа H, которую можно выбирать по желанию, — это дополнительный параметр при отображении деревьев. Введем процедуру

отобр2( T, H)

печатающую дерево T с отступом на H пробелов от левого края листа. Связь между процедурами отобри отобр2такова:

отобр( T) :- отобр2( T, 0).