лег с тем же хеш-значением, пока не найдет своего двойника или
не дойдет до конца списка. Будем называть i-j-столкновением
столкновение t[i] с t[j]. Общее число действий примерно равно
числу всех столкновений плюс число элементов. При t[i]<>t[j] ве-
роятность i-j-столкновения равна 1/n. Осталось проследить за
столкновениями между равными элементами. Фиксируем некоторое
значение x из множества T и посмотрим на связанные с ним опера-
ции. Они идут по циклу: добавление - проверки - удаление - до-
бавление - проверки - удаление - ... Столкновения между ними
происходят между добавляемым элементом и следующими за ним про-
верками (до удаления включительно), поэтому общее их число не
превосходит числа элементов, равных x.
Теперь приведем примеры универсальных семейств. Очевидно,
для любых конечных множеств A и B семейство всех функций, отоб-
ражающих A в B, является универсальным. Однако этот пример с
практической точки зрения бесполезен: для запоминания случайной
функции из этого семейства нужен массив, число элементов в кото-
ром равно числу элементов в множестве A. (А если мы можем себе
позволить такой массив, то никакого хеширования нам не требует-
ся!)
Более практичные примеры универсальных семейств могут быть
построены с помощью несложных алгебраических конструкций. Через
Z[p] мы обозначаем множество вычетов по простому модулю p, т.е.
{0,1,...,p-1}; арифметические операции в этом множестве выполня-
ются по модулю p. Универсальное семейство образуют все линейные
функционалы на Z[p] в степени n со значениями в Z[p]. Более под-
робно, пусть a[1],...,a[n] - произвольные элементы Z[p];
рассмотрим отображение
h: |-> a[1]x{1]+...+a{n]z[n]
Мы получаем семейство из (p в степени n) отображений, параметри-
зованное наборами a[1]...a[n].
11.2.5. Доказать, что это семейство является универсальным.
Указание. Пусть x и y - различные точки пространства Z[p] в
степени n. Какова вероятность того, что случайный функционал
принимает на них одинаковые значения? Другими словами, какова
вероятность того, что он равен нулю на их разности x-y? Ответ
дается таким утверждением: пусть u - ненулевой вектор; тогда все
значения случайного функционала на нем равновероятны.
В следующей задаче множество B={0,1} рассматривается как
множество вычетов по модулю 2.
11.2.6. Семейство всех линейных отображений из (B в степени
m) в (B в степени n) является универсальным.
Родственные идеи неожиданно оказываются полезными в следу-
ющей ситуации (рассказал Д.Варсонофьев). Пусть мы хотим написать
программу, которая обнаруживала (большинство) опечаток в тексте,
но не хотим хранить список всех правильных словоформ. Предлага-
ется поступить так: выбрать некоторое N и набор функций
f[1],...,f[k], отображающих русские слова в 1..N. В массиве из N
битов положим все биты равными нулю, кроме тех, которые являются
значением какой-то функции набора на какой-то правильной слово-
форме. Теперь приближённый тест на правильность словоформы та-
ков: проверить, что значения всех функций набора на этой слово-
форме попадают на места, занятые единицами.
Глава 12. Множества и деревья.
12.1. Представление множеств с помощью деревьев.
Полное двоичное дерево. T-деревья.
Нарисуем точку. Из нее проведем две стрелки (влево вверх и
вправо вверх) в две другие точки. Из каждой из этих точек прове-
дем по две стрелки и так далее. Полученную картинку (в n-ом слое
будет (2 в степени (n - 1)) точек) называют полным двоичным де-
ревом. Нижнюю точку называют корнем. У каждой вершины есть два
сына (две вершины, в которые идут стрелки) - левый и правый. У
всякой вершины, кроме корня, есть единственный отец.
Пусть выбрано некоторое конечное множество вершин полного
двоичного дерева, содержащее вместе с каждой вершиной и всех ее
предков. Пусть на каждой вершине этого множества написано значе-
ние фиксированного типа T (то есть задано отображение множества
вершин в множество значений типа T). То, что получится, будем
называть T-деревом. Множество всех T-деревьев обозначим Tree(T).
Рекурсивное определение. Всякое непустое T-дерево разбива-
ется на три части: корень (несущий пометку из T), левое и правое
поддеревья (которые могут быть и пустыми). Это разбиение уста-
навливает взаимно однозначное соответствие между множеством не-
пустых T-деревьев и произведением T * Tree (T) * Tree (T). Обоз-
начив через empty пустое дерево, можно написать
Tree (T) = {empty} + T * Tree (T) * Tree (T).
Поддеревья. Высота.
Фиксируем некоторое T-дерево. Для каждой его вершины x оп-
ределено ее левое поддерево (левый сын вершины x и все его по-
томки), правое поддерево (правый сын вершины x и все его потом-
ки) и поддерево с корнем в x (вершина x и все ее потомки). Левое
и правое поддеревья вершины x могут быть пустыми, а поддерево с
корнем в x всегда непусто (содержит по крайней мере x). Высотой
поддерева будем считать максимальную длину цепи y[1]..y[n] его
вершин, в которой y [i+1] - сын y [i] для всех i. (Высота пусто-
го дерева равна нулю, высота дерева из одного корня - единице.)
Упорядоченные T-деревья.
Пусть на множестве значений типа T фиксирован порядок. На-
зовем T-дерево упорядоченным, если выполнено такое свойство: для
любой вершины x все пометки в ее левом поддереве меньше пометки
в x, а все пометки в ее правом поддереве больше пометки в x.
12.1.1. Доказать, что в упорядоченном дереве все пометки
различны.
Указание. Индукция по высоте дерева.
Представление множеств с помощью деревьев.
Каждое дерево будем считать представлением множества всех
пометок на его вершинах. При этом одно и то же множество может
иметь различные представления.
Благодаря упорядоченности каждый элемент легко может "найти
свое место" в дереве: придя в какую-то вершину и сравнив себя с
тем, кто там находится, элемент решает, идти ему налево или нап-
раво. Начав с корня и двигаясь по этому правилу, он либо обнару-
жит, что такой элемент уже есть, либо найдет место, в котором он
должен быть. Всюду далее мы предполагаем, что на значениях типа
T задан порядок, и рассматриваем только упорядоченные деревья.
Хранение деревьев в программе.
Можно было бы сопоставить вершины полного двоичного дерева
с числами 1, 2, 3,... (считая, что левый сын (n) = 2n, правый
сын (n) = 2n + 1) и хранить пометки в массиве val [1...]. Однако
этот способ неэкономен, поскольку тратится место на хранение
пустых вакансий в полном двоичном дереве.
Более экономен такой способ. Введем три массива
val: array [1..n] of T;
left, right: array [1..n] of 0..n;
(n - максимальное возможное число вершин дерева) и переменную
root: 0..n. Каждая вершина хранимого T-дерева будет иметь номер
- число от 1 до n. Разные вершины будут иметь разные номера. По-
метка в вершине с номером x равна val [x]. Корень имеет номер
root. Если вершина с номером i имеет сыновей, то их номера равны
left [i] и right [i]. Отсутствующим сыновьям соответствует число
0. Аналогичным образом значение root = 0 соответствует пустому
дереву.
Для хранения дерева используется лишь часть массива; для
тех i, которые свободны - т.е. не являются номерами вершин -
значения val [i] безразличны. Нам будет удобно, чтобы все сво-
бодные числа были "связаны в список": первое хранится в специ-
альное переменной free: 0..n, а следующее за i свободное число
хранится в left [i], так что свободны числа
free, left [free], left [left[free]],...
Для последнего свободного числа i значение left [i] = 0. Ра-
венство free = 0 означает, что свободных чисел больше нет. (За-
мечание. Мы использовали для связывания свободных вершин массив
left, но, конечно, с тем же успехом можно было использовать мас-
сив right.)
Вместо значения 0 (обозначающего отсутствие вершины) можно
было бы воспользоваться любым другим числом вне 1..n. Чтобы под-
черкнуть это, будем вместо 0 использовать константу null = 0.
12.1.2. Составить программу, определяющую, содержится ли
элемент t: T в упорядоченном дереве (хранимом так, как только
что описано).
Решение.
if root = null then begin
| ..не принадлежит
end else begin
| x := root;
| {инвариант: остается проверить наличие t в непустом подде-
| реве с корнем x}
| while ((t < val [x]) and (left [x] <> null)) or
| | ((t > val [x]) and (right [x] <> null)) do begin
| | if t < val [x] then begin {left [x] <> null}
| | | x := left [x];
| | end else begin {t > val [x], right [x] <> null}
| | | x := right [x];
| | end;
| end;
| {либо t = val [x], либо t отсутствует в дереве}
| ..ответ = (t = val [x])
end;
12.1.3. Упростить решение, используя следующий трюк. Расши-
рим область определения массива val, добавив ячейку с номером
null и положим val [null] = t.
Решение.
val [null] := t;
x := root;
while t <> val [x] do begin
| if t < val [x] then begin
| | x := left [x];
| end else begin
| | x := right [x];
| end;
end;
..ответ: (x <> null).
12.1.4. Составить программу добавления элемента t в мно-
жество, представленное упорядоченным деревом (если элемент t уже
есть, ничего делать не надо).
Решение. Определим процедуру get_free (var i: integer), да-
ющую свободное (не являющееся номером) число i и соответствующим
образом корректирующую список свободных чисел.
procedure get_free (var i: integer);
begin
| {free <> null}
| i := free;
| free := left [free];
end;
С ее использованием программа приобретает вид:
if root = null then begin
| get_free (root);
| left [root] := null; right [root] := null;
| val [root] := t;
end else begin
| x := root;
| {инвариант: осталось добавить t к непустому поддереву с
| корнем в x}
| while ((t < val [x]) and (left [x] <> null)) or
| | ((t > val [x]) and (right [x] <> null)) do begin
| | if t < val [x] then begin
| | | x := left [x];
| | end else begin {t > val [x]}
| | | x := right [x];
| | end;
| end;
| if t <> val [x] then begin {t нет в дереве}
| | get_free (i);
| | left [i] := null; right [i] := null;
| | val [i] := t;
| | if t < val [x] then begin
| | | left [x] := i;
| | end else begin {t > val [x]}
| | | right [x] := i;
| | end;
| end;
end;
12.1.5. Составить программу удаления элемента t из мно-
жества, представленного упорядоченным деревом (если его там нет,
ничего делать не надо).
Решение.
if root = null then begin
| {дерево пусто, ничего делать не надо}
end else begin
| x := root;
| {осталось удалить t из поддерева с корнем в x; поскольку
| это может потребовать изменений в отце x, введем
| переменные father: 1..n и direction: (l, r);
| поддерживаем такой инвариант: если x не корень, то father
| - его отец, а direction равно l или r в зависимости от
| того, левым или правым сыном является x}
| while ((t < val [x]) and (left [x] <> null)) or
| | ((t > val [x]) and (right [x] <> null)) do begin
| | if t < val [x] then begin
| | | father := x; direction := l;
| | | x := left [x];
| | end else begin {t > val [x]}
| | | father := x; direction := r;
| | | x := right [x];
| | end;
| end;
| {t = val [x] или t нет в дереве}
| if t = val [x] then begin
| | ..удаление вершины x с отцом father и направлением
| | direction
| end;
end;
Удаление вершины x происходит по-разному в разных случаях. При
этом используется процедура
procedure make_free (i: integer);
begin
| left [i] := free;
| free := i;
