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

Рис. 9.6. Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5→8→6.

Будем говорить, что непустое дерево дер( Лев, X, Прав) упорядочено слева направо, если

(1) все вершины левого поддерева Лев меньше X;

(2) все вершины правого поддерева Прав больше X;

(3) оба поддерева упорядочены.

Будем называть такое двоичное дерево двоичным справочником. Пример показан на рис. 9.6.

Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в двоичном справочнике всегда достаточно просмотреть не более одного поддерева. Экономия при поиске объекта X достигается за счет того, что, сравнив X с корнем, мы можем сразу же отбросить одно из поддеревьев. Например, пусть мы ищем элемент 6 в дереве, изображенной на рис. 9.6. Мы начинаем с корня 5, сравниваем 6 с 5, получаем 6 > 5. Поскольку все элементы данных в левом поддереве должны быть меньше, чем 5, единственная область, в которой еще осталась возможность найти элемент 6, — это правое поддерево. Продолжаем поиск в правом поддереве, переходя к вершине 8, и т.д.

Общий метод поиска в двоичном справочнике состоит в следующем:

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

• если X — это корень справочника Д, то считать, что X уже найден, иначе

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

• искать X в правом поддереве;

• если справочник Д пуст, то поиск терпит неудачу.

Эти правила запрограммированы в виде процедуры, показанной на рис. 9.7. Отношение больше( X, Y), означает, что X больше, чем Y. Если элементы, хранимые в дереве, — это числа, то под "больше, чем" имеется в виду просто X > Y.

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

?- внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).

Д = дер( дер( Д1, 3, Д2), 5, дер( Д3, 8, Д4) ).

Переменные Д1, Д2, Д3 и Д4 соответствуют четырем неопределенным поддеревьям. Какими бы они ни были, все равно дерево Д будет содержать заданные элементы 3, 5 и 8. Структура построенного дерева зависит от того порядка, в котором указываются цели (рис. 9.8).

внутри( X, дер( _, X, _ ).

внутри( X, дер( Лев, Корень, Прав) ) :-

 больше( Корень, X), % Корень больше, чем X

внутри( X, Лев).     % Поиск в левом поддереве

внутри( X, дер( Лев, Корень, Прав) ) :-

 больше( X, Корень), % X больше, чем корень

 внутри( X, Прав).   % Поиск в правом поддереве

Рис. 9.7. Поиск элемента X в двоичном справочнике.

Рис. 9.8. (а) Дерево Д, построенное как результат достижения целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д). (b) Дерево, полученное при другом порядке целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д).

Здесь уместно сделать несколько замечаний относительно эффективности поиска в справочниках. Вообще говоря, поиск элемента в справочнике эффективнее, чем поиск в списке. Но насколько? Пусть n — число элементов множества. Если множество представлено списком, то ожидаемое время поиска будет пропорционально его длине n. В среднем нам придется просмотреть примерно половину списка. Если множество представлено двоичным деревом, то время поиска будет пропорционально глубине дерева. Глубина дерева — это длина самого длинного пути между корнем и листом дерева. Однако следует помнить, что глубина дерева зависит от его формы.

Мы говорим, что дерево (приближенно) сбалансировано, если для каждой вершины дерева соответствующие два поддерева содержат примерно равное число элементов. Если дерево хорошо сбалансировано, то его глубина пропорциональна log n. В этом случае мы говорим, что дерево имеет логарифмическую сложность. Сбалансированный справочник лучше списка настолько же, насколько log n меньше n. К сожалению, это верно только для приближенно сбалансированного дерева. Если происходит разбалансировка дерева, то производительность падает. В случае полностью разбалансированных деревьев, дерево фактически превращается в список. Глубина дерева в этом случае равна n, а производительность поиска оказывается столь же низкой, как и в случае списка. В связи с этим мы всегда заинтересованы в том, чтобы справочники были сбалансированы. Методы достижения этой цели мы обсудим в гл. 10.

9.9. Определите предикаты

двдерево( Объект)

справочник( Объект)

распознающие, является ли Объект двоичным деревом или двоичным справочником соответственно. Используйте обозначения, введенные в данном разделе.

9.10. Определите процедуру

глубина( ДвДерево, Глубина)

вычисляющую глубину двоичного дерева в предположении, что глубина пустого дерева равна 0, а глубина одноэлементного дерева равна 1.

9.11. Определите отношение

линеаризация( Дерево, Список)

соответствующее "выстраиванию" всех вершин дерева в список.

9.12. Определите отношение

максэлемент( Д, Элемент)

таким образом, чтобы переменная Элемент приняла значение наибольшего из элементов, хранящихся в дереве Д.

9.13. Внесите изменения в процедуру

внутри( Элемент, ДвСправочник)

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

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

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

внутри( X, S)       % X  содержится в  S

добавить( S, X, S1) % Добавить  X  к  S,  результат -  S1

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

Рис. 9.9. Введение в двоичный справочник нового элемента на уровне листьев. Показанные деревья соответствуют следующей последовательности вставок: добавить( Д1, 6, Д2), добавить( Д2, 6, Д3), добавить( Д3, 6, Д4)

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

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

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

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

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

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

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

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

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

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

доблист( Д, X, Д1)

Правила добавления элемента на уровне листьев таковы:

• Результат добавления элемента X к пустому дереву есть дерево дер( nil, X, nil).

• Если X совпадает с корнем дерева Д, то Д1 = Д (в множестве не допускается дублирования элементов).

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

На рис. 9.10 показана соответствующая программа.

Теперь рассмотрим операцию удалить. Лист дерева удалить легко, однако удалить какую-либо внутреннюю вершину — дело не простое. Удаление листа можно на самом деле определить как операцию, обратную операции добавления листа:

удлист( Д1, X, Д2) :-

 доблист( Д2, X, Д1).

Рис. 9.11. Удаление X из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента X.

К сожалению, если X — это внутренняя вершина, то такой способ не работает, поскольку возникает проблема, иллюстрацией к которой служит рис. 9.11. Вершина X имеет два поддерева Лев и Прав. После удаления вершины X в дереве образуется "дыра", и поддеревья Лев и Прав теряют свою связь с остальной частью дерева. К вершине А оба эти поддерева присоединить невозможно, так как вершина А способна принять только одно из них.