| 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.
