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

in( X, t( Left, Root, Right) L X, t( Left, Root, Right}
)

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

-

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

)

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

-

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

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


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

?- in( 5, , ±г. ( 3, D), lH {a,
D - t ( t( Dl, 3, D2) , 5, " D3,

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.