Листинг 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.

Рандомно подобранные статьи с сайта:

[Сбор ключевых слов с помощью AMZ.ONE] Как собрать семантическое ядро для листинга на Амазоне.


Похожие статьи:

admin