Лекции.Орг


Поиск:




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





Поделиться с друзьями:


Дата добавления: 2015-10-01; Мы поможем в написании ваших работ!; просмотров: 401 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Победа - это еще не все, все - это постоянное желание побеждать. © Винс Ломбарди
==> читать все изречения...

1210 - | 1146 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.