Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Поиск по сбалансированному деревуБинарное дерево называется сбалансированным, если высота левого поддерева каждого узла отличается от высоты правого не более чем на ±1 (рис. 2.20). Сбалансированные бинарные деревья занимают промежуточное положение между оптимальными бинарными деревьями (все внешние узлы которых расположены на двух смежных уровнях) и произвольными бинарными деревьями. Рис. 2.20. Пример сбалансированного дерева Рассмотрим следующую структуру узлов сбалансированного бинарного дерева (табл. 2.2). Таблица 2.2. Структура узлов сбалансированного дерева В табл. 2.2 В — показатель сбалансированности узла, т. е. разность высот правого и левого поддерева (В = +1; 0; -1). При восстановлении баланса дерева по высоте учитывается показатель В (рис. 2.21).
Рис.2.21. Деревья с показателями сбалансированности узлов Символы на рис. 2.21 +1, Ø, -1 указывают, что левое поддерево выше правого, поддеревья равны по высоте, правое поддерево выше левого. 2.2.6. Поиск по бору Особую группу методов поиска образует представление ключей в виде последовательности цифр и букв. Рассмотрим, например, имеющиеся во многих словарях буквенные высечки. Тогда по первой букве данного слова можно отыскать страницы, содержащие все слова, начинающиеся с этой буквы. Развивая идею побуквенных высечек, получим схему поиска, основанную на индексации в структуре бора (термин использует часть слова выборка). Бор представляет собой т-арное дерево. Каждый узел уровня h представляет множество всех ключей, начинающихся с определенной последовательности из h литер. Узел определяет m-путевое разветвление в зависимости от (h + 1)-й литеры. Бор представляет собой таблицу следующего вида (табл. 2.3). Таблица 2.3. Структура бора Пробел (_) — обязательный символ таблицы. В первом узле записывается первая буква или цифра ключа. Во втором узле к ней добавляется еще один символ и т. д. Если слово, начинающееся с определенной буквы (цифры), единственное, то оно сразу записывается в первом узле. Пример.Дано множество {А, АА, АВ, ABC, ABCD, ABCA, ABCC, BOR, С, СС, ССС, CCCD, СССВ, СССА}. От исходного множества перейдем к построению бора. Исходный алфавит = {А, В, С, D}. BOR — единственное слово на букву В и оно побуквенно не разбивается. Узлы бора представляют собой векторы, каждая компонента которых представляет собой либо ключ, либо ссылку (возможно пустую) — табл. 2.4. Таблица 2.4. Пример поска по бору
Узел 1 — корень, и первую букву следует искать здесь. Если первой оказалась, например, буква В, то из таблицы видно, что ей соответствует слово ВOR. Если же первая буква А, то первый узел передает управление к узлу 2, где аналогичным образом отыскивается вторая буква. Узел 2 указывает, что вторыми буквами будут _, А, В и т. д. Поиск хешированием В основе поиска лежит переход от исходного множества к множеству хеш-функций h(k). Хеш-функция имеет следующий вид: h(k) = kmod(m), где k — ключ; т — целое число; mod — целочисленный остаток от деления. Например, пусть дано множество {9, 1, 4, 10, 8, 5}. Определим для него хеш-функцию h(k) = kmod(m): • пусть т = 1, тогда h(k) = {0, 0, 0, 0, 0, 0}; • пусть т = 20, тогда h(k) = {9, 1, 4, 10, 8, 5}; • пусть т равно половине максимального ключа, тогда т = = [10/2] = 5 h(k) = {4,1, 4, 0, 3, 0}. Хеш-функция указывает адрес, по которому следует отыскивать ключ. Для разных ключей хеш-функция может принимать одинаковые значения, такая ситуация называется коллизией. Таким образом, поиск хешированием заключается в устранении коллизий методом цепочек (рис. 2.22). Рис. 2.22. Устранение коллизий методом цепочек Пример.Дано множество {7, 13, 6, 3, 9, 4, 8, 5}. Найти ключ К=27. Хеш-функция равна h(k} = Kmod(m); т = [13/2] = 6 (так как 13 — максимальный ключ). h(k) = {1, 1, 0, 3, 3, 4, 2, 5}. Для устранения коллизий построим табл. 2.5. Попарным сравнением множества хеш-функций и множества исходных ключей заполняем таблицу. Напоминаем, что хеш-функция указывает адрес, по которому следует отыскивать ключ. Таблица 2.5. Разрешение коллизий Например, если отыскивается ключ К= 27, тогда h(k) = 27mod6 = 3 — это значит, что ключ К= 27 может быть только в 3-й строке. Так как его там нет, то данный ключ отсутствует в исходном множестве. Контрольные вопросы 1. Что понимается под поиском? 2. Каковы особенности поиска: последовательного, бинарного, интерполяционного, Фибоначчиевого? 3. Каковы особенности поиска: по бинарному дереву, по бору, хешированием? 4. В чем состоит методика анализа сложности алгоритмов поиска?
|
|
Последнее изменение этой страницы: 2016-07-23 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |