Одна из обычных областей применения списков состоит в представлении множеств объектов. Недостатком' использования списка для представления множества является то, что при этом операция проверки принадлежности к множеству довольно неэффективна. Предикат member (X, L) для проверки того, входит ли элемент X в •состав списка L, обычно программируется следующим образом: member! X, [X | L]).
member (Хг [Y | L]):-meraber(X, L}.
Эта процедура, чтобы найти элемент X в списке L, просматривает элементы списка один за другим до тех пор, пока не будет найден элемент X или обнаружен конец списка. В случае использования больших списков такая операция становится очень неэффективной.
Для представления множеств могут использоваться различные древовидные структуры, которые обеспечивают более эффективную реализацию отношения проверки принадлежности к множеству. В данном разделе рассматриваются такие структуры, как бинарные деревья.
| Бинарное дерево либо понентов: | является | пустым, | либо | состоит | из | следующих | трех | ком- |
| • корень; | ||||||||
| • левое поддерево; | ||||||||
| • правое поддерево. |
Корнем может служить любой объект, но поддеревья должны снова представлять собой бинарные деревья. Пример такой структуры показан на рис. 9.2. Это дерево соответствует множеству {а, Ь, с, dh Элементы этого множества хранятся как узлы дерева. На рис. 9.2 пустые поддеревья не показаны; например, узел Ь имеет два поддерева, из которых оба пусты.
Предусмотрено много способов представления бинарных деревьев в виде термов Prolog. Один из простых вариантов состоит в том, чтобы корень бинарного дерева рассматривался как главный функтор терма, а поддеревья — как его параметры. В соответствии с этим пример дерева, приведенный на рис. 9.2, может быть представлен следующим образом:
а{ Ь, c(d))
корень
левов поддерево ■ I J:'.■'-. i с) привое поддерево
А
Рис. 9.2. Бинарное дерево
Глава 9. Операции со структурами данных
Но такое представление имеет множество недостатков; в частности, оно требует применения отдельного функтора для каждого узла дерева. Это может привести к затруднениям, если сами узлы представляют собой структурированные объекты.
Лучший и более широко применяемый способ представления бинарных деревьев состоит в следующем; используются специальный символ для представления пустого дерева и функтор для формирования непустого дерева из трех его компонентов (корня и двух поддеревьев). В данном разделе в качестве специального символа и функтора применяются следующие:
• атом nil используется для представления пустого дерева;
• применяется функтор t, такой, что дерево, которое имеет корень X, левое под
дерево L и правое поддерево R, представляется термом t (L, X,?, как пока
зано на рис. 9.3.
При таком способе представления дерево, показанное в качестве примера на рис. 9.2, обозначается следующим термом: tt t(nil, Ь, nil), a, t(t(nil, d, nil), c, nil))
|
| t(L.X,R) |
Рис. 9.3, Представление бинарных деревьев
Теперь рассмотрим отношение проверки принадлежности к множеству, называемое в данном разделе как in. Цель in(х, т>
является истинной, если X - узел в дереве Т. Отношение in может быть определено с помощью приведенных ниже правил. X находится в дереве Т, если:
• X является корнем Т, или
• X находится в левом поддереве Т, или
• X находится в правом поддереве Т.
Эти правила можно непосредственно перенести на язык Prolog следующим образом: in(X,tt_<X,_!). ±n(X, t (L,,!):-
in(X, L). in(X, t(_,_,R)):-
in (X, R).
Очевидно, что цель in i X, nil) не будет достигаться при любом значении X
Рассмотрим поведение процедуры in, В приведенных ниже примерах Т представляет собой дерево, приведенное на рис. 9.2. Цель in! х, т) с помощью перебора с возвратами находит все данные в множестве в таком порядке:
X = а; X = fc;X = с; X = d
Теперь рассмотрим, насколько эффективной является процедура in. Цель
198 Часть I. Язык Prolog
in (а, т)
немедленно достигается в результате выполнения первого предложения в процедуре in. С другой стороны, для достижения цели in! d, T)
потребуется несколько рекурсивных вызовов процедуры in, прежде чем будет в конечном итоге найден элемент d. Аналогичным образом, цель In! e, TJ
не достигается только после завершения поиска с помощью рекурсивных вызовов процедуры in во всех поддеревьях дерева Т.
Поэтому такая конструкция является столь же неэффективной, как и простой способ представления множества в виде списка. Но можно добиться ее значительного усовершенствования после введения отношения упорядочения между элементами данных во множестве. В таком случае появляется возможность упорядочивать данные в дереве слева направо согласно этому отношению. Непустое дерево t (Left, X, Right) называется упорядоченным слева направо, если соблюдаются следующие условия.
1. Все узлы в левом поддереве, Left, меньше X.
2. Все узлы в правом поддереве, Right, больше X.
3. Оба поддерева также являются упорядоченными.
В дальнейшем такое бинарное дерево будем называть бинарным словарем. Пример подобного дерева приведен на рис. 9.4.
|
Рис. 9.4. Пример бинарного словаря; элемент 6 достигается в результате прохождения по указанному в дереве пути 5^8->б
Преимущество упорядочения состоит в том, что для поиска любого объекта в бинарном словаре всегда достаточно провести поиск не более чем в одном поддереве. Ключом к такой экономии усилий при поиске X является то, что в результате сравнения X и корня из рассмотрения немедленно исключается, по меньшей мере, одно из поддеревьев. Например, проведем поиск элемента б в дереве, показанном на рис. 9.4. Начнем с корня 5, сравним 6 и 5 и определим, что 6 > 5. Поскольку все данные в левом поддереве должны быть меньше 5, единственная оставшаяся возможность состоит в проведении поиска элемента 6 в правом поддереве. Поэтому поиск продолжается в правом поддереве, происходит переход к узлу S и т.д.
Общий метод поиска в бинарном словаре описан ниже.
Чтобы найти элемент X в словаре D, необходимо выполнить следующие действия:
если X — корень D, то элемент X найден, в противном случае,
если X — меньше, чем корень D, то проводить поиск X в левом поддереве D, в противном случае
Глава 9. Операции со структурами данных
проводить поиск X в правом поддереве D;
если дерево D пусто, поиск оканчивается неудачей.
Эти правила запрограммированы в виде процедуры in, приведенной в листинге 9.3. Отношение gt{ X, Y] означает: X больше Y. Если элементы, хранящиеся в дереве, представляют собой числа, то это отношение принимает вид X > Y.
