Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 63
Текст из файла (страница 63)
Если мы сохраняем п ключей в хеш-таблице размером т = и с использованием хеш-функции 6, выбираемой случайным образом из универсального множества хеш-функций, и устанавливаем размер каждой вторичной хеш-таблицы равным т = пз (1 = 0,1,...,т — 1), то вероятность того, что общее количество необходимой для вторичных хеш-таблиц памяти не менее 4п, меньше чем 1/2. Доказательсазао. Вновь применим неравенство Маркова (В.29), Рг(Х > 1) < < Е 1Х1/$, на этот раз к неравенству (11.7) (здесь Х = ,'1 „~ т и Ф = 4п): е[г ~] 2п 1 < < — = —. 4п 4п 2 тп-1 т >4п з=о '( Упражнения * 11.5-1. Предположим, что мы вставляем и ключей в хеш-таблицу размером т с использованием открытой адресации и равномерного хеширования.
Обозначим через р(п, т) вероятность отсутствия коллизий. Покажите, что р (и, т) < е "(" 1)/з . (Указание: см. уравнение (3.11).) Докажите, что при п, превосходящем ~/т, вероятность избежать коллизий быстро падает до нуля. Глава 11. Хеш-таблицы 313 Задачи 11-1. Наибольшее число исследований при хешировании Имеется хеш-таблица размером гп с открьпой адресацией, в которой сохраняется п ключей, причем п < гп/2. а) Покажите, что в предположении равномерного хеширования вероятность того, что для любого 1 = 1, 2,..., и для вставки г-го ключа требуется более й исследований, не превышает 2 ~. б) Покажите, что для любого з' = 1,2,...,п вероятность того, что вставка г-го ключа требует выполнения более 21яп исследований, не превышает 1/пз.
Пусть Х; — случайная величина, обозначающая количество исследований, необходимое при вставке г-го ключа. В подзадаче б) вы должны были показать, что Рг (Х; > 2 1б и) < 1/пз. Обозначим через Х максимальное количество исследований, необходимое при любой из и вставок: Х = шах1 <;<„Х;. в) Покажите, что Рг (Х > 2 1к п) < 1/и.
г) Покажите, что математическое ожидание Е [Х] длины наибольшей последовательности исследований равно О (1б и). 11-2. Длины цепочек при хешировании Имеется хеш-таблица с и ячейками и разрешением коллизий методом цепочек. Пусть в таблицу вставлено п ключей. Вероятность каждого ключа попасть в любую из ячеек одинакова для всех ключей и всех ячеек. Пусть М вЂ” максимальное количество ключей в ячейке после того, как все ключи вставлены в таблицу.
Ваша задача — доказать, что математическое ожидание Е 1М] имеет верхнюю границу О (1ки/1к1ки). а) Покажите, что вероятность Яь того, что в определенной ячейке находится ровно Й ключей, равна — 1 б) Пусть Рь — вероятность того, что М = к, т.е. вероятность того, что ячейка, содержащая наибольшее количество ключей, содержит нх ровно )с.
Покажите, что Рь < пЯь. в) Воспользуйтесь приближением Стирлинга (3.17), чтобы показать, что Яь < е"/)с". 314 Часть 111. Структуры данных г) Покажите, что существует константа с > 1, такая что Яьо < 1/пз длл 1сс = с !к и/!к !к и. Выведите отсюда, что Рь < 1/пз дла й > йо = = с!кп/1я!яп. д) Покажите, что Е !М) < Рг М > — ~ и+ Рг ~М < с1кп ) 1 с1кп ) с1кп 1б1бп~ ~( !б1бп~ 1к1кп' Выведите отсюда, что Е [М) = О (!кп/!к !кп).
11-3. Квадратичное исследование Предположим, что у нас есть ключ й, который надо найти в хеш-таблице, ячейки которой пронумерованы от 0 до т — 1, и пусть у нас есть хеш-функция и, отображающая пространство ключей в множество (О, 1,..., т — 1). Схема поиска выглядит следующим образом. !. Вычисляем значение з' — Ь (й) и присваиваем 3 — О. 2. Исследуем ячейку г на соответствие искомому ключу !с. Если ключ найден, или если ячейка пуста, поиск прекращается. 3. Присваиваем т' — (т'+ 1) пюс1 т и г — (г + )) шой тп, и переходим к шагу 2.
Предположим, что т является степенью 2. а) Покажите, что описанная схема представляет собой частный случай общей схемы "квадратичного исследования" с соответствующими юнстантами с~ и сз в уравнении (11.5). б) Докажите, что в худшем случае данный алгоритм просматривает все ячейки таблицы. 11-4. )с-универсальное хеширование Пусть Н = (Ц вЂ” семейство хеш-функций, в ютором каждая хешфункция Ь отображает пространство ключей У на множество (О, 1,..., тп — 1).
Мы говорим, что Н является !с-универсальным, если для каждой последовательности из Й различных ключей (гО), х1з),..., х1ь)) н случайным образом выбранной из Н хеш-функции Ь последовательность (и (хО)) Ь. (х1з)),..., й (х1"))) принимает все тп" последовательностей длины й из элементов множества (0,1,...,т — 1) с равной вероятностью.
а) Покажите, что если множество Н является 2-универсальным, то оно универсально. Глава 11. Хеш-таблицы 315 б) Пусть (7 — множество наборов из п значений, выбранных из Ер, и пусть В = Ер, где р — простое число. Определим хеш-функцию 6~ ь . (7 — + В с х = (хо, хм..., х„1) из (7 в качестве аргумента для любого набора а = (ао, аы..., а„1) значений из Ер и для любого ЬЕ Ер как и-1 Ь~,ь(х) = ~~) аух +Ь шар, у=о и пусть Н = (6, ь). Покажите, что множество Н является 2-универсальным.
в) Два друга договорились о "секретной" хеш-функции Ь, ь из 2-универсального множества хеш-функций Н. Один из них шлет сообщение тп б У другому через 1пзегпеь Он подписывает это сообщение, пересылая одновременно с ним дескриптор 1 = Ь., ь (т), а его друг проверяет, удовлетворяет ли полученная им пара т, г условию 1 = = Ь ь (гп).
Злоумышленник перехватывает сообщение (пг,1) и пытается обмануть получателя, подсунув ему собственное сообщение (т', Р). Покажите, что вероятность того, что злоумышленник сможет успешно совершить подмену, не превышает 1/р, независимо от того, какими вычислительными мощностями он обладает. Заключительные замечания Алгоритмы хеширования прекрасно изложены в книгах Кнута (Кпш)з) (185] и Гоннета (Ооппе1) [12б]. Согласно Кнуту, хеш-таблицы и метод цепочек были изобретены Луном (Н.
Р. 1.п)ш) в 1953 году. Примерно тогда же Амдал (О. М. АшдаЫ) предложил идею открытой адресации. Универсальные множества хеш-функций были предложены Картером (Сапег) и Вегманом (%ейшап) в 1979 году 152]. Схему идеального хеширования для статических множеств, представленную в разделе 11.5, разработали Фредман (Ргедшап), Комлес (Кош!бз) и Семереди (Яхепзегегй) (96]. Расширение этого метода для динамических множеств предложено Дицфельбингером (ВйегтГе1Ь1пйег) и др. (73].
ГЛАВА 12 Бинарные деревья поиска Деревья поиска представляют собой структуры данных, которые поддерживают многие операции с динамическими множествами, включая поиск элемента, минимального и максимального значения, предшествующего и последующего элемента, вставку и удаление. Таким образом, дерево поиска может использоваться и как словарь, и как очередь с приоритетами. Основные операции в бинарном дереве поиска выполняются за время, пропорциональное его высоте. Для полного бинарного дерева с п узлами эти операции выполняются за время 6 (1йп) в наихудшем случае. Как будет показано в разделе 12.4, математическое ожидание высоты построенного случайным образом бинарного дерева равно О (1бп), так что все основные операции над динамическим множеством в таком дереве выполняются в среднем за время 9 (!~п).
На практике мы не всегда можем гарантировать случайность построения бинарного дерева поиска, однако имеются версии деревьев, в которых гарантируется хорошее время работы в наихудшем случае. В главе 13 будет представлена одна из таких версий, а именно — красно-черные деревья, высота которых О (1бп).
В главе 18 вы познакомитесь с В-деревьями, которые особенно хорошо подходят для баз данных, хранящихся во вторичной памяти с произвольным доступом (на дисках). После знакомст. з с основными свойствами деревьев поиска, в последующих разделах главы буде г показано, как осуществляется обход дерева поиска для вывода его элементов в отсортированном порядке, как выполняется поиск минимального н максимального элементов, а также предшествующего данному элементу и следующего за ним, как вставлять элементы в дерево поиска и удалять их оттуда. Основные математические свойства деревьев описаны в приложении Б. Глава 12. Бинарные деревья поиска 317 12.1 Что такое бинарное дерево поиска Как следует из названия, бинарное дерево поиска в первую очередь является бинарным деревом, как показано на рис.
12.! . Такое дерево может быть представлено при помощи связанной структуры данных, в которой каждый узел является обьектом. В дополнение к полям ключа кеу и сопутствующих данных, каждый узел содержит поля 1е~Г, гздМ и р, которые указывают на левый и правый дочерние узлы и на родительский узел соответственно. Если дочерний или родительский узел отсутствуют, соответствующее поле содержит значение )чй..
Единственный узел, указатель р которого равен )чи., — это корневой узел дерева. Ключи в бинарном дереве поиска хранятся таким образом, чтобы в любой момент удовлетворять следующему свойству бинарного дерева ноисна. Если х — узел бинарного дерева поиска, а узел у находится в левом поддереве х, то йеу [у] < кеу [х]. Если узел у находится в правом поддереве х, то Йеу[х] < Йеу[у]. Так, на рис. 12.1а ключ корня равен 5, ключи 2, 3 и 5, которые не превышают значение ключа в корне, находятся в его левом поддереве, а ключи 7 и 8, которые не меньше, чем ключ 5, — в его правом поддереве. То же свойство, как легко убедиться, выполняется для каждого другого узла дерева. На рис.
12.1б показано дерево с теми же узлами и обладающее тем же свойством, однако менее эффективное в работе, поскольку его высота равна 4, в отличие от дерева на рис. 12.!а, высота которого равна 2. Свойство бинарного дерева поиска позволяет нам вывести все ключи, находящиеся в дереве, в отсортированном порядке с помощью простого рекурсивного алгоритма, называемого центрированным (симметричным) обходим дерева (шоп1ег 1гее ча)к). Этот алгоритм получил данное название в связи с тем, что ключ в корне поддерева выводится между значениями ключей левого поддерева а) Рис. 12.1. Бинарные деревья поиска Часть П1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
