Представление множеств с помощью бинарных деревьев

Однаиз обычных областей применения списков состоит в представлении мно­жеств объектов. Недостатком' использования списка для представления множества является то, что при этом операция проверки принадлежности к множеству довольно неэффективна. Предикат 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.