Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Поиск по сбалансированному дереву

Бинарное дерево называется сбалансированным, если высота левого поддерева каждого узла отличается от высоты правого не более чем на ±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. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...