Листинг 9.3. Процедура поиска элемента X в бинарном словаре

% in(X, Tree;: элемент X находится в Бинарном словаре Tree in(X, t(_, X J).

-

% Корень больше,;-: X

проводить поиск в левом поддереве

-

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

Проводить поиск в правом поддереве

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

D4)).

Переменные Dl, D2, D3 и С i являются четырьмя неопределенными поддеревьями. Они могут представлять собой что угодно, но дерево D все равно будет содержать ла­данные элементы 3, 5 и 8. Структура сформированного словаря зависит от порядка целей в вопросе {рис. 9.5).

Рис. 9.5. Пример того, что структура бинарного словаря зависит от па рядка целей в вопросе: а) дерево D. формируемое при выполнении последо-аатслыюстщелей iaf 5, D), in f 3, D), in(8, 0); б) дерево, форми­руемое при обработке вопроса in (3, D), in (5, D), in< 8, D)

Теперь уместно привести комментарии по поводу того, какова эффективность по­иска в словарях. Вообще говоря, поиск элемента в словаре осуществляется более эф­фективно, чем поиск в списке. Как оценить степень повышения этой эффективности? Предположим, что л — количество элементов в наборе данных. Если множество представлено списком, то ожидаемое время поиска должно быть пропорционально

Часть I. Язык Prolog

его длине п. В среднем приходится выполнять просмотр списка до некоторого места, находящегося примерно в середине этого списка, А если множество представлено в виде бинарного словаря, то время поиска примерно пропорционально высоте дерева. Высотой дерева называется длина самого длинного пути между корнем и листом де­рева. Но высота зависит от формы дерева.

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