от предыдущих. Пусть М - максимальная длина цепочек после добавления га ключей. Ваша задача - доказать, что математическое ожидание М есть О (lg тг/ lg lg га).

а. Фиксируем некоторое хеш-значение. Пусть Qk - вероятность того, ему соответствует к различных ключей. Покажите, что

б.Пусть Рк - вероятность того, что максимальная длина цепочки равна к. Покажите, что Рк nQk-

в.Выведите из формулы Стирлинга (2.11), что Qk < ек/кк.

г.Покажите, что существует такая константа с > 1, что Qk < 1/га3 при к clgra/lglgra. Заключите отсюда, что Р < 1/га2 при таких к.

д.Покажите, что математическое ожидание величины М не превосходит

и выведите отсюда, что это математическое ожидание есть 0(lg га/ lg lg га).

12-4 Пример квадратичной последовательности проб

Пусть нам надо поместить запись с ключом к в хеш-таблицу, ячейки которой пронумерованы числами 0,1,..., т - 1. У нас есть хеш-функция h, отображающая множество ключей в множество {0,1,..., т - 1}. Будем действовать так:

1.Находим г <- h(k) и полагаем j <- 0.

2.Проверяем позицию номер г. Если она свободна, заносим туда запись и на этом останавливаемся.

3.Полагаем j <- (j + 1) mod т и г <- (i+j) mod т и возвращаемся к шагу 2.

а.Покажите, что описанный алгоритм - частный случай «квадратичного метода» для подходящих значений с\ и с2.

Предположим, что т является степенью двойки.

б.Покажите, что в худшем случае будет просмотрена вся таблица.

12-5 /г-универсальное хеширование

Пусть И - семейство хеш-функций, отображающих множество возможных ключей U в {0,1,..., т - 1}. Будем говорить, что И является /г-универсальным, если для любой последовательности к различных ключей (xi,...,Xk) случайная величина (h(xi),..., h(xk)) (где h - случайный элемент %) принимает все тк своих возможных значений с равными вероятностями.

а.Покажите, что всякое 2-универсальное семейство универсально.

б.Покажите, что семейство 7i, описанное в разделе 12.3.3, не является 2-универсальным.

в.Расширим семейство И из разд. 12.3.3 и рассмотрим всевозможные функции вида

ha<b(x) = ha(x) + b mod то,

где b - некоторый вычет по модулю то. Покажите, что полученное семейство будет 2-универсальным.

Замечания

Алгоритмы хеширования прекрасно изложены у Кнута [123] и Гоннета [90]. Согласно Кнуту, хеш-таблицы и метод цепочек были изобретены Луном (Н.Р. Luhn) в 1953 году. Примерно в то же время Амдаль (G.M.Amdahl) изобрёл открытую адресацию.

Двоичные деревья поиска

Деревья поиска (search trees) позволяют выполнять следующие операции с динамическими множествами: Search (поиск), Minimum (минимум), Maximum (максимум), Predecessor (предыдущий), Successor (следующий), Insert (вставить) и Delete (удалить). Таким образом, дерево поиска может быть использовано и как словарь, и как очередь с приоритетами.

Время выполнения основных операций пропорционально высоте дерева. Если двоичное дерево «плотно заполнено» (все его уровни имеют максимально возможное число вершин), то его высота (и время выполнения операций) пропорциональны логарифму числа вершин. Напротив, если дерево представляет собой линейную цепочку из га вершин, это время вырастает до О(га). В разделе 13.4 мы увидим, что высота случайного двоичного дерева поиска есть О (lgra), так что в этом случае время выполнения основных операций есть 0(lgга).

Конечно, возникающие на практике двоичные деревья поиска могут быть далеки от случайных. Однако, приняв специальные меры по балансировке деревьев, мы можем гарантировать, что высота деревьев с га вершинами будет О (log га). В главе 14 рассмотрен один из подходов такого рода (красно-чёрные деревья). В главе 19 рассматриваются Б-деревья, которые особенно удобны для данных, хранящихся во вторичной памяти с произвольным доступом (на диске).

В этой главе мы рассмотрим основные операции с двоичными деревьями поиска и покажем, как напечатать элементы дерева в неубывающем порядке, как искать заданный элемент, как найти максимальный или минимальный элемент, как найти элемент, следующий за данным и предшествующий данному, и, наконец, как добавить или удалить элемент. Напомним, что определение дерева и основные свойства деревьев приводятся в главе 5.