А. Шень ðòïçòáííéòï÷áîéå ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ Издание седьмое, дополненное Москва

232
12. Оптимальное кодирование
12.2.3. Пусть даны 𝑘 целых положительных чисел 𝑛
1
, . . . , 𝑛
𝑘
, удовле-
творяющие неравенству Крафта { Макмиллана. Докажите, что можно
построить префиксный код для 𝑘-буквенного алфавита с длинами ко-
довых слов 𝑛
1
, . . . , 𝑛
𝑘
.
Решение. И здесь полезно использовать соответствие между слова-
ми и отрезками и представлять себе дело так: у нас есть единичный
отрезок [0, 1], и мы выделяем его части пользователям по требованию.
Если пользователь приходит с числом 𝑛
𝑖
, то это значит, что ему надо
выдать в пользование один из отрезков длиной 2
−
𝑛
𝑖
, соответствую-
щих кодовым словам длины 𝑛
𝑖
. (Тем самым годятся не любые отрезки
такой длины, а лишь «правильно расположенные».) Код должен быть
префиксным, это значит, что отрезки разных пользователей не долж-
ны перекрываться. Нам дано, что суммарная длина всех требований не
больше единицы. Как их удовлетворить? Можно отводить место сле-
ва направо, при этом рассматривать требования в порядке убывания
длин (тогда более короткие отрезки будут правильно расположены по-
сле предыдущих более длинных).
12.2.4. Покажите, что выделять кодовые слова (место на отрезке)
можно и в порядке поступления требований (как иногда говорят, в «ре-
жиме on-line»): пользователь приходит с числом 𝑛
𝑖
и уходит с правильно
расположенным отрезком длины 2
−
𝑛
𝑖
, причём если выполнено неравен-
ство Крафта { Макмиллана, то никто не уйдёт обиженным (всем хватит
места, и перераспределять его не придётся).
[Указание. Нужно поддерживать свободное пространство как объ-
единение правильно расположенных отрезков попарно различных длин,
выделяя каждому пользователю кусок из кратчайшего подходящего от-
резка и доразбивая остаток.]
12.2.5. Покажите, что неравенство Крафта { Макмиллана выполня-
ется не только для любого префиксного кода, но и вообще для любого
однозначного кода. (Именно это доказал Макмиллан; Крафт доказал
неравенство для префиксных кодов.)
Решение. Есть разные способы решить эту задачу; мы приведём
простое и красивое, хотя и несколько загадочное, решение. Пусть име-
ется однозначный код с 𝑘 кодовыми словами 𝑃
1
, . . . , 𝑃
𝑘
. Нам надо дока-
зать, что их длины 𝑛
𝑖
=
|
𝑃
𝑖
|
удовлетворяют неравенству Крафта { Мак-
миллана. Представим себе, что вместо нулей и единиц используются
символы 𝑎 и 𝑏 (какая разница, из чего составлять коды?). Запишем

12.2. Неравенство Крафта { Макмиллана
233
формально сумму всех кодовых слов как алгебраическое выражение
𝑃
1
+ 𝑃
2
+ . . . + 𝑃
𝑘
(многочлен от 𝑎 и 𝑏, в котором одночлены записаны как произведе-
ния переменных 𝑎 и 𝑏, без возведения в степень). Теперь (ещё более
странное на первый взгляд действие) возведём это выражение в сте-
пень 𝑁 (произвольное натуральное число) и раскроем скобки, сохраняя
порядок переменных (не собирая вместе одинаковые переменные) в од-
ночленах:
(𝑃
1
+ 𝑃
2
+ . . . + 𝑃
𝑘
)
𝑁
= сумма одночленов.
Например, для кода со словами 0, 10, 11 (которые теперь записываются
как 𝑎, 𝑏𝑎, 𝑏𝑏) и для 𝑁 = 2 получаем
(𝑎 + 𝑏𝑎 + 𝑏𝑏)
2
= (𝑎 + 𝑏𝑎 + 𝑏𝑏)(𝑎 + 𝑏𝑎 + 𝑏𝑏) =
= 𝑎𝑎 + 𝑎𝑏𝑎 + 𝑎𝑏𝑏 + 𝑏𝑎𝑎 + 𝑏𝑎𝑏𝑎 + 𝑏𝑎𝑏𝑏 + 𝑏𝑏𝑎 + 𝑏𝑏𝑏𝑎 + 𝑏𝑏𝑏𝑏.
В этом примере все одночлены в правой части различны (если не пере-
ставлять переменные), и это не случайно: так будет для любого одно-
значного кода. В самом деле, по определению однозначности никакое
слово не может быть получено двумя способами при соединении кодо-
вых слов.
Теперь подставим 𝑎 = 𝑏 = 1/2 в наше равенство (если оно верно для
букв, то оно верно и для любых их числовых значений). Слева получится
(2
−
𝑛
1
+ 2
−
𝑛
2
+ . . . + 2
−
𝑛
𝑘
)
𝑁
(в скобке как раз выражение из неравенства Крафта { Макмиллана).
Правую часть мы оценим сверху, сгруппировав слова по длинам: име-
ется не более 2
𝑙
слагаемых длины 𝑙, каждое из которых равно 2
−
𝑙
,
и потому слагаемые данной длины в сумме не превосходят единицы,
а правая часть не превосходит максимальной длины слагаемых, то есть
𝑁 max 𝑛
𝑖
. Итак, получаем, что
(2
−
𝑛
1
+ 2
−
𝑛
2
+ . . . + 2
−
𝑛
𝑘
)
𝑁
< 𝑁 max 𝑛
𝑖
,
и это верно при любом 𝑁. Если основание степени в левой части больше
единицы, то при больших 𝑁 это неравенство нарушится (показательная
функция растёт быстрее линейной). Поэтому для однозначного кода
выполняется неравенство Крафта { Макмиллана.

234
12. Оптимальное кодирование
12.3. Код Хаффмана
Теперь задача о коде минимальной средней длины приобретает та-
кую форму: для данных положительных 𝑝
1
, . . . , 𝑝
𝑘
, равных в сумме еди-
нице, найти целые положительные 𝑛
1
, . . . , 𝑛
𝑘
, для которых выполнено
неравенство Крафта { Макмиллана, а сумма
𝑘
∑︁
𝑖=1
𝑝
𝑖
𝑛
𝑖
является минимально возможной (среди наборов 𝑛
1
, . . . , 𝑛
𝑘
, удовлетво-
ряющих неравенству). Задача
12.2.5
показывает показывает, что сред-
няя длина однозначного кода не меньше этого минимума, а задача
12.2.3
говорит, что этот минимум достигается, причём даже для префиксного
кода. Как же найти числа 𝑛
1
, . . . , 𝑛
𝑘
, доставляющие этот минимум?
12.3.1. Докажите, что для двух букв оптимальный код состоит из
двух слов длины 1, независимо от частот букв.
Чтобы решить задачу в общем случае, начнём с нескольких простых
замечаний.
12.3.2. Пусть частоты расположены в убывающем порядке: 𝑝
1
>
> 𝑝
2
> . . . > 𝑝
𝑘
. Докажите, что тогда длины слов оптимального кода
идут в неубывающем порядке: 𝑛
1
6
𝑛
2
6
. . .
6
𝑛
𝑘
.
Решение. Если бы более редкая буква имела бы более короткое кодо-
вое слово, то, обменяв кодовые слова, мы сократили бы среднюю длину
кода.
12.3.3. Останется ли утверждение предыдущей задачи в силе, если
частоты расположены в невозрастающем порядке (возможны равные)?
Решение. Нет: если, скажем, имеются три буквы с частотой 1/3, то
оптимальный код будет иметь длины слов 1, 2, 2 (если бы два кодовых
слова имели длину 1, то на третье уже не осталось бы места), и они
могут идти в любом порядке.
Заметим, однако, что при поиске оптимального кода (для невоз-
растающих частот) мы вправе ограничиваться лишь кодами, в кото-
рых длины кодовых слов неубывают (поскольку кодовые слова для букв
одинаковых частот можно переставлять без изменения средней длины
кода).

12.3. Код Хаффмана
235
12.3.4. Пусть частоты расположены в невозрастающем порядке
(𝑝
1
>
𝑝
2
>
. . .
>
𝑝
𝑘
), а длины слов в оптимальном коде расположены в не-
убывающем порядке 𝑛
1
6
𝑛
2
6
. . .
6
𝑛
𝑘
. Докажите, что 𝑛
𝑘
−
1
= 𝑛
𝑘
(при
𝑘
>
2).
Решение. Предположим, что это не так, и что есть единственное са-
мое длинное кодовое слово длины 𝑛
𝑘
. Тогда неравенство Крафта { Мак-
миллана не может обращаться в равенство, поскольку все слагаемые,
кроме наименьшего (последнего), кратны удвоенному последнему сла-
гаемому. Значит, в этом неравенстве есть запас, причём не меньший
последнего слагаемого. А тогда можно уменьшить 𝑛
𝑘
на единицу, не
нарушая неравенства, что противоречит предположению об оптималь-
ности исходного кода.
Эта задача показывает, что при поиске оптимального кода можно
рассматривать лишь коды, в которых две самые редкие буквы имеют
коды одинаковой длины.
12.3.5. Как свести задачу отыскания длин кодовых слов оптималь-
ного кода для 𝑘 частот
𝑝
1
>
𝑝
2
>
. . .
>
𝑝
𝑘
−
2
>
𝑝
𝑘
−
1
>
𝑝
𝑘
к задаче поиска длин оптимального кода для 𝑘
−
1 частот
𝑝
1
, 𝑝
2
, . . . , 𝑝
𝑘
−
2
, 𝑝
𝑘
−
1
+ 𝑝
𝑘
(частоты двух самых редких букв объединены)?
Решение. Мы уже знаем, что можно рассматривать лишь коды с
𝑛
𝑘
−
1
= 𝑛
𝑘
. Неравенство Крафта { Макмиллана тогда запишется как
2
−
𝑛
1
+ 2
−
𝑛
2
+ . . . + 2
−
𝑛
𝑘
−
2
+ 2
−
𝑛
𝑘
−
1
+ 2
−
𝑛
𝑘
=
= 2
−
𝑛
1
+ 2
−
𝑛
2
+ . . . + 2
−
𝑛
𝑘
−
2
+ 2
−
𝑛
6
1,
если положить 𝑛
𝑘
−
1
= 𝑛
𝑘
= 𝑛 + 1. Таким образом, числа 𝑛
1
, . . . , 𝑛
𝑘
−
2
, 𝑛
должны удовлетворять неравенству Крафта { Макмиллана для 𝑘
−
1
букв. Средняя длины этих двух кодов будут связаны:
𝑝
1
𝑛
1
+ . . . + 𝑝
𝑘
−
2
𝑛
𝑘
−
2
+ 𝑝
𝑘
−
1
𝑛
𝑘
−
1
+ 𝑝
𝑘
𝑛
𝑘
=
= 𝑝
1
𝑛
1
+ . . . + 𝑝
𝑘
−
2
𝑛
𝑘
−
2
+ (𝑝
𝑘
−
1
+ 𝑝
𝑘
)𝑛 + [𝑝
𝑘
−
1
+ 𝑝
𝑘
].
Последнее слагаемое (квадратная скобка) не зависит от выбираемого
кода, поэтому минимизировать надо остальное, то есть как раз сред-
нюю длину кода с длинами слов 𝑛
1
, . . . , 𝑛
𝑘
−
2
, 𝑛 для частот 𝑝
1
, 𝑝
2
, . . .
. . . , 𝑝
𝑘
−
2
, 𝑝
𝑘
−
1
+ 𝑝
𝑘
. После этого надо положить 𝑛
𝑘
−
1
= 𝑛
𝑘
= 𝑛 + 1, и это
даст оптимальный код для исходной задачи.

236
12. Оптимальное кодирование
Используя эту задачу, несложно составить рекурсивную программу
для отыскания длин кодовых слов. С каждым вызовом число букв бу-
дет уменьшаться, пока мы не сведём задачу к случаю двух букв, когда
оптимальный код состоит из слов 0 и 1. Затем можно найти и сами
кодовые слова (согласно задаче
ствия и сразу искать кодовые слова: ведь замена числа 𝑛 на два числа
𝑛 + 1 соответствует замене кодового слова 𝑃 на два слова 𝑃 0 и 𝑃 1 на
единицу большей длины (и эта последняя замена сохраняет префикс-
ность кода).
Код, построенный таким методом, называется кодом Хаффмана.
Мы доказали, что он имеет минимальную среднюю длину среди всех
кодов (для данных частот букв). В следующей задаче оценивается чи-
сло операций, необходимых для построения кода Хаффмана.
12.3.6. Покажите, что можно обработать частоты 𝑝
1
, . . . , 𝑝
𝑘
, сде-
лав 𝑂(𝑘 log 𝑘) операций, после чего 𝑖-е кодовое слово можно указать за
время, пропорциональное его длине.
[Указание. Заметим, что оценка времени довольно сильная: толь-
ко на сортировку чисел 𝑝
𝑖
уже уходит 𝑂(𝑘 log 𝑘) действий. Поэтому,
применяя предыдущую задачу, нужно использовать результаты сорти-
ровки 𝑘 чисел при сортировке меньшего количества чисел. Это можно
сделать с помощью очереди с приоритетами, вынимая два минималь-
ных числа и добавляя их сумму за 𝑂(log 𝑘) действий. Это позволяет
определить, какие две буквы надо соединять в одну на каждом шаге.
Параллельно с соединением букв можно строить дерево кодов, проводя
рёбра (помеченные 0 и 1) от соединённой буквы к каждой из её по-
ловинок. При этом требуется 𝑂(1) действий на каждом шаге. После
завершения построение прослеживать код любой буквы можно символ
за символом.]
12.4. Код Шеннона { Фано
Мы видели, как можно построить оптимальный код (имеющий ми-
нимальную среднюю длину) для данного набора частот. Однако эта
конструкция не даёт никакой оценки для средней длины оптимального
кода (как функции от частот 𝑝
𝑖
). Следующие задачи указывает такую
оценку (с абсолютной погрешностью не более 1).
12.4.1. Покажите, что для любых положительных частот 𝑝
1
, . . . , 𝑝
𝑘
(в сумме равных единице) существует код средней длиной не более
𝐻(𝑝
1
, . . . , 𝑝
𝑘
) + 1, где функция 𝐻 (называемая энтропией Шеннона)

12.4. Код Шеннона { Фано
237
определяется формулой
𝐻(𝑝
1
, . . . , 𝑝
𝑛
) = 𝑝
1
(
−
log
2
𝑝
1
) + . . . + 𝑝
𝑘
(
−
log
2
𝑝
𝑘
)
Решение. Если частоты 𝑝
𝑖
представляют собой целые (отрицатель-
ные) степени двойки, то это утверждение почти очевидно. Положим
𝑛
𝑖
=
−
log 𝑝
𝑖
(здесь и далее все логарифмы двоичные). Тогда 2
−
𝑛
𝑖
= 𝑝
𝑖
и потому для чисел 𝑛
𝑖
выполнено неравенство Крафта { Макмиллана.
По задаче
можно построить префиксный код с длинами кодовых
слов 𝑛
1
, . . . , 𝑛
𝑘
, и средняя длина этого кода будет равна 𝐻(𝑝
1
, . . . , 𝑝
𝑘
)
(и даже единицу добавлять не надо).
Эта единица пригодится, если log 𝑝
𝑖
не целые. В этом случае надо
взять наименьшее 𝑛
𝑖
, при котором 2
−
𝑛
𝑖
6
𝑝
𝑖
. Для таких 𝑛
𝑖
выполняется
неравенство Крафта { Макмиллана, и они больше
−
log 𝑝
𝑖
не более чем
на единицу (потому и после усреднения ухудшение будет не более чем
на единицу).
Построенный на основе этой задачи код называется кодом Шенно-
на { Фано
1
. Это построение легко извлекается из решения задачи
рассматривая числа 𝑛
𝑖
=
−⌊
log 𝑝
𝑖
⌋
(наименьшие целые числа, для ко-
торых 2
−
𝑛
𝑖
6
𝑝
𝑖
) в порядке убывания, мы отводим для каждого из
них кодовое слово и соответствующий участок отрезка [0, 1] слева на-
право.
При этом мы проигрываем в длине кода (по сравнению с оптималь-
ным кодом) не более единицы: как мы сейчас увидим, средняя длина
любого (в том числе и оптимального) кода не меньше 𝐻(𝑝
1
, . . . , 𝑝
𝑘
).
12.4.2. (Для знакомых с математическим анализом) Докажите, что
(при данных положительных частотах, в сумме дающих единицу) сред-
няя длина любого (однозначного) кода не меньше 𝐻(𝑝
1
, . . . , 𝑝
𝑘
).
Решение. Имея в виду неравенство Крафта { Макмиллана, мы дол-
жны доказать такой факт: если
2
−
𝑛
1
+ . . . 2
−
𝑛
𝑘
6
1,
то
𝑝
1
𝑛
1
+ . . . + 𝑝
𝑘
𝑛
𝑘
>
𝐻(𝑝
1
, . . . , 𝑝
𝑘
).
1
Хотя это название и употребительно, оно не вполне правильно с исторической
точки зрения. Описанное построение было предложено Шенноном; Фано предложил
другой метод построения кода, в котором буквы упорядочиваются по убыванию
частот и разбиваются на две группы в таком месте, чтобы суммы частот в группах
были как можно ближе друг к другу. Буквы первой группы кодируются кодами,
начинающимися с нуля, а второй | кодами, начинающимися с единицы. Процесс
повторяется рекурсивно для каждой группы.

238
12. Оптимальное кодирование
Это верно для любых 𝑛
𝑖
, не обязательно целых. Удобно перейти от 𝑛
𝑖
к величинам 𝑞
𝑖
= 2
−
𝑛
𝑖
; интересующее нас утверждение тогда гласит,
что если 𝑝
1
, . . . , 𝑝
𝑘
и 𝑞
1
, . . . , 𝑞
𝑘
| два набора положительных чисел,
и сумма чисел в каждом равна единице, то
𝑝
1
(
−
log 𝑞
1
) + . . . + 𝑝
𝑘
(
−
log 𝑞
𝑘
)
>
𝑝
1
(
−
log 𝑝
1
) + . . . + 𝑝
𝑘
(
−
log 𝑝
𝑘
).
Другими словами, выражение
𝑝
1
(
−
log 𝑞
1
) + . . . + 𝑝
𝑘
(
−
log 𝑞
𝑘
)
(рассматриваемое при фиксированных 𝑝
𝑖
как функция на множестве
всех положительных 𝑞
1
, . . . , 𝑞
𝑘
, в сумме равных единице) достигает ми-
нимума при 𝑞
𝑖
= 𝑝
𝑖
. Область определения этой функции есть внутрен-
ность симплекса (треугольника при 𝑛 = 3, тетраэдра при 𝑛 = 4 и т. д.)
и при приближении к границе одно из 𝑞
𝑖
становится малым, а его минус
логарифм уходит в бесконечность. Значит, минимум функции достига-
ется внутри области. В точке минимума градиент (
−
𝑝
1
/𝑞
1
, . . . ,
−
𝑝
𝑛
/𝑞
𝑛
)
должен быть перпендикулярен плоскости, на которой функция опре-
делена (иначе сдвиг вдоль этой плоскости уменьшал бы функцию), то
есть все 𝑝
𝑖
/𝑞
𝑖
равны. Поскольку
∑︀
𝑝
𝑖
=
∑︀
𝑞
𝑖
= 1, то это означает, что
𝑝
𝑖
= 𝑞
𝑖
.
Другое объяснение: функция log выпукла вверх, поэтому для любых
неотрицательных коэффициентов 𝛼
𝑖
, в сумме равных единице, и для
любых точек 𝑥
𝑖
из области определения логарифма выполняется нера-
венство
log
(︁∑︁
𝛼
𝑖
𝑥
𝑖
)︁
>
∑︁
𝛼
𝑖
log 𝑥
𝑖
.
Остаётся положить 𝛼
𝑖
= 𝑝
𝑖
, 𝑥
𝑖
= 𝑞
𝑖
/𝑝
𝑖
; в левой части будет логарифм
единицы, то есть нуль, а
∑︀
𝑝
𝑖
log(𝑞
𝑖
/𝑝
𝑖
) есть как раз разность между
левой и правой частями доказываемого неравенства.
Велика ли экономия от использования кодов, описанных в этом раз-
деле? Это, конечно, зависит от частот букв: если они все одинако-
вые, то никакой экономии не будет. Легко заметить, что в русском
языке разные буквы имеют разную частоту. Если, скажем, в текстах
(TEX-файлах) этой книжки (на момент эксперимента) оставить толь-
ко 33 строчные русские буквы от «а» до «я», а все остальные символы
не учитывать, то самой частой буквой будет буква «о» (частота 0,105),
а самой редкой | твёрдый знак (частота 0,00019). Значение энтропии
Шеннона при этом будет равно 4,454 (сравните с 5 битами, необхо-
димыми для кодирования 32 букв). Выигрыш не так велик. Он будет

12.4. Код Шеннона { Фано
239
больше, если учитывать также и другие символы (прописные буквы,
знаки препинания и др.), которые встречаются в тексте гораздо реже.
Наконец, можно кодировать не буквы, а двухбуквенные комбинации или
ещё что-нибудь. Именно так поступают популярные программы сжатия
информации (типа zip), которые позволяют сократить многие тексты
в полтора-два раза (а некоторые другие файлы данных | и в большее
число раз).
12.4.3. Компания M. утверждает, что её новая программа супер-
сжатия файлов позволяет сжать любой файл длиной больше 100 000 бай-
тов по крайней мере на 10% без потери информации (можно восстано-
вить исходный файл по его сжатому варианту). Докажите, что она
врёт.

13. ПРЕДСТАВЛЕНИЕ
МНОЖЕСТВ.
ХЕШИРОВАНИЕ
13.1. Хеширование с открытой адресацией
В главе
было указано несколько представлений для множеств, эле-
ментами которых являются целые числа произвольной величины. Одна-
ко в любом из них хотя бы одна из операций проверки принадлежности,
добавления и удаления элемента требовала количества действий, про-
порционального числу элементов множества. На практике это бывает
слишком много. Существуют способы, позволяющие получить для всех
трёх упомянутых операций оценку 𝐶 log 𝑛. Один из таких способов мы
рассмотрим в следующей главе. В этой главе мы разберём способ, кото-
рые хотя и приводит к 𝐶𝑛 действиям в худшем случае, но зато «в сред-
нем» требует значительно меньшего их числа. (Мы не будем уточнять
слов «в среднем», хотя это и можно сделать.) Этот способ называется
хешированием.
Пусть нам необходимо представлять множества элементов типа T,
причём число элементов в них заведомо меньше n. Выберем некото-
рую функцию h, определённую на значениях типа T и принимающую
значения 0 . . . n-1. Было бы хорошо, чтобы эта функция принимала на
элементах будущего множества по возможности более разнообразные
значения. (Худший случай | это когда её значения на всех элемен-
тах хранимого множества одинаковы.) Эту функцию будем называть
хеш-функцией, или, как ещё говорят, функцией расстановки.
Введём два массива
val: array [0..n-1] of T;
used: array [0..n-1] of boolean;
(мы позволяем себе писать n-1 в качестве границы в определении типа,

13.1. Хеширование с открытой адресацией
241
хотя в паскале это не разрешается). В этих массивах будут храниться
элементы множества: оно равно множеству всех val [i] для тех i, для
которых used [i], причём все эти val [i] различны. По возможности
мы будем хранить элемент t на месте h(t), считая это место «искон-
ным» для элемента t. Однако может случиться так, что новый элемент,
который мы хотим добавить, претендует на уже занятое место (для
которого used истинно). В этом случае мы отыщем ближайшее справа
свободное место и запишем элемент туда. («Справа» значит «в сторо-
ну увеличения индексов»; дойдя до края, мы перескакиваем в начало.)
По предположению, число элементов всегда меньше n, так что пустые
места заведомо будут.
Формально говоря, в любой момент должно соблюдаться такое тре-
бование: для любого элемента множества участок справа от его искон-
ного места до его фактического места полностью заполнен.
Благодаря этому проверка принадлежности заданного элемента t
осуществляется легко: встав на h(t), двигаемся направо, пока не дой-
дём до пустого места или до элемента t. В первом случае элемент t
отсутствует в множестве, во втором | присутствует. Если элемент
отсутствует, то его можно добавить на найденное пустое место. Если
присутствует, то можно его удалить (положив used = false).
13.1.1. В предыдущем абзаце есть ошибка. Найдите её и исправьте.
Решение. Дело в том, что при удалении требуемое свойство «отсут-
ствия пустот» может нарушиться. Поэтому будем делать так. Создав
дыру, будем двигаться направо, пока не натолкнёмся на элемент, сто-
ящий не на исконном месте, или на ещё одно пустое место. Во втором
случае на этом можно успокоиться. В первом случае посмотрим, не
нужно ли найденный элемент поставить на место дыры. Если нет, то
продолжаем поиск, если да, то затыкаем им старую дыру. При этом
образуется новая дыра, с которой делаем всё то же самое.
13.1.2. Напишите программы проверки принадлежности, добавле-
ния и удаления.
Решение.
function принадлежит (t: T): boolean;
var i: integer;
begin
i := h (t);
while used [i] and (val [i] <> t) do begin
i := (i + 1) mod n;
end; {not used [i] or (val [i] = t)}

242
13. Представление множеств. Хеширование
принадлежит := used [i] and (val [i] = t);
end;
procedure добавить (t: T);
var i: integer;
begin
i := h (t);
while used [i] and (val [i] <> t) do begin
i := (i + 1) mod n;
end; {not used [i] or (val [i] = t)}
if not used [i] then begin
used [i] := true;
val [i] := t;
end;
end;
procedure исключить (t: T);
var i, gap: integer;
begin
i := h (t);
while used [i] and (val [i] <> t) do begin
i := (i + 1) mod n;
end; {not used [i] or (val [i] = t)}
if used [i] and (val [i] = t) then begin
used [i] := false;
gap := i;
i := (i + 1) mod n;
{gap - дыра, которая может закрыться одним из i,i+1,...}
while used [i] do begin
if i = h (val[i]) then begin
{на своём месте, ничего не делать}
end else if dist(h(val[i]),i) < dist(gap,i) then begin
{gap...h(val[i])...i, ничего не делать}
end else begin
used [gap] := true;
val [gap] := val [i];
used [i] := false;
gap := i;
end;
i := (i + 1) mod n;
end;
end;
end;
Здесь dist (a,b) | измеренное по часовой стрелке (слева направо)

13.2. Хеширование со списками
243
расстояние от a до b, то есть
dist (a,b) = (b - a + n) mod n.
(Мы прибавили n, так как функция mod правильно работает при поло-
жительном делимом.)
13.1.3. Существует много вариантов хеширования. Один из них та-
ков: обнаружив, что исконное место (обозначим его 𝑖) занято, будем ис-
кать свободное не среди 𝑖 + 1, 𝑖 + 2, . . ., а среди 𝑟(𝑖), 𝑟(𝑟(𝑖)), 𝑟(𝑟(𝑟(𝑖))), . . .,
где 𝑟 | некоторое отображение
{
0, . . . , 𝑛
−
1
}
в себя. Какие при этом
будут трудности?
Ответ. (1) Не гарантируется, что если пустые места есть, то мы
их найдём. (2) При удалении неясно, как заполнять дыры. (На практи-
ке во многих случаях удаление не нужно, так что такой способ также
применяется. Считается, что удачный подбор функции 𝑟 может пре-
дотвратить образование «скоплений» занятых ячеек.)
13.1.4. Пусть для хранения множества всех правильных русских
слов в программе проверки орфографии используется хеширование.
Что нужно добавить, чтобы к тому же уметь находить английский
перевод любого правильного слова?
Решение. Помимо массива val, элементы которого являются русски-
ми словами, нужен параллельный массив их английских переводов.
13.2. Хеширование со списками
На хеш-функцию с 𝑘 значениями можно смотреть как на способ све-
сти вопрос о хранении одного большого множества к вопросу о хране-
нии нескольких меньших. Именно, если у нас есть хеш-функция с 𝑘 зна-
чениями, то любое множество разбивается на 𝑘 подмножеств (возмож-
но, пустых), соответствующих возможным значениям хеш-функции.
Вопрос о проверке принадлежности, добавлении или удалении для боль-
шого множества сводится к такому же вопросу для одного из меньших
(чтобы узнать, для какого, надо посмотреть на значение хеш-функции).
Эти меньшие множества удобно хранить с помощью ссылок; их сум-
марный размер равен числу элементов хешируемого множества. Следу-
ющая задача предлагает реализовать этот план.
13.2.1. Пусть хеш-функция принимает значения 1 . . . k. Для каждо-
го значения хеш-функции рассмотрим список всех элементов множе-

244
13. Представление множеств. Хеширование
ства с данным значением хеш-функции. Будем хранить эти k списков
с помощью переменных
Содержание: array [1..n] of T;
Следующий: array [1..n] of 1..n;
ПервСвоб: 1..n;
Вершина: array [1..k] of 1..n;
так же, как мы это делали для k стеков ограниченной суммарной дли-
ны. Напишите соответствующие программы. (Удаление по сравнению
с открытой адресацией упрощается.)
Решение. Перед началом работы надо положить Вершина[i] = 0 для
всех i = 1 . . . k, и связать все места в список свободного пространства,
положив ПервСвоб = 1 и Следующий[i] = i+1 для i = 1 . . . n-1, а также
Следующий[n] = 0.
function принадлежит (t: T): boolean;
var i: integer;
begin
i := Вершина[h(t)];
{осталось искать в списке, начиная с i}
while (i <> 0) and (Содержание[i] <> t) do begin
i := Следующий[i];
end; {(i=0) or (Содержание [i] = t)}
принадлежит := (i<>0) and (Содержание[i]=t);
end;
procedure добавить (t: T);
var i: integer;
begin
if not принадлежит(t) then begin
i := ПервСвоб;
{ПервСвоб <> 0 - считаем, что не переполняется}
ПервСвоб := Следующий[ПервСвоб]
Содержание[i]:=t;
Следующий[i]:=Вершина[h(t)];
Вершина[h(t)]:=i;
end;
end;
procedure исключить (t: T);
var i, pred: integer;
begin
i := Вершина[h(t)]; pred := 0;

13.2. Хеширование со списками
245
{осталось искать в списке, начиная с i; pred -
предыдущий, если он есть, и 0, если нет}
while (i <> 0) and (Содержание[i] <> t) do begin
pred := i; i := Следующий[i];
end; {(i=0) or (Содержание [i] = t)}
if i <> 0 then begin
{Содержание[i]=t, элемент есть, надо удалить}
if pred = 0 then begin
{элемент оказался первым в списке}
Вершина[h(t)] := Следующий[i];
end else begin
Следующий[pred] := Следующий[i]
end;
{осталось вернуть i в список свободных}
Следующий[i] := ПервСвоб;
ПервСвоб:=i;
end;
end;
13.2.2. (Для знакомых с теорией вероятностей.) Пусть хеш-функ-
ция с 𝑘 значениями используется для хранения множества, в котором
в данный момент 𝑛 элементов. Докажите, что математическое ожида-
ние числа действий в предыдущей задаче не превосходит 𝐶(1 + 𝑛/𝑘),
если добавляемый (удаляемый, искомый) элемент 𝑡 выбран случайно,
причём все значения ℎ(𝑡) имеют равные вероятности (равные 1/𝑘).
Решение. Если 𝑙(𝑖) | длина списка, соответствующего хеш-значе-
нию 𝑖, то число операций не превосходит 𝐶(1 + 𝑙(ℎ(𝑡))); усредняя, по-
лучаем искомый ответ, так как
∑︀
𝑖
𝑙(𝑖) = 𝑛.
Эта оценка основана на предположении о равных вероятностях. Од-
нако в конкретной ситуации всё может быть совсем не так, и значения
хеш-функции могут «скучиваться»: для каждой конкретной хеш-функ-
ции есть «неудачные» ситуации, когда число действий оказывается
большим. Приём, называемый универсальным хешированием, позволя-
ет обойти эту проблему. Идея состоит в том, что берётся семейство
хеш-функций, причём любая ситуация оказывается неудачной лишь для
небольшой части этого семейства.
Пусть 𝐻 | семейство функций, каждая из которых отображает
множество 𝑇 в множество из 𝑘 элементов (например, 0 . . . 𝑘
−
1). Гово-
рят, что 𝐻 | универсальное семейство хеш-функций, если для любых
двух различных значений 𝑠 и 𝑡 из множества 𝑇 вероятность события
ℎ(𝑠) = ℎ(𝑡) для случайной функции ℎ из семейства 𝐻 равна 1/𝑘. (Дру-

246
13. Представление множеств. Хеширование
гими словами, те функции из 𝐻, для которых ℎ(𝑠) = ℎ(𝑡), составляют
1/𝑘-ю часть всех функций в 𝐻.)
Замечание. Более сильное требование к семейству 𝐻 могло бы со-
стоять в том, чтобы для любых двух различных элементов 𝑠 и 𝑡 мно-
жества 𝑇 значения ℎ(𝑠) и ℎ(𝑡) случайной функции ℎ являются неза-
висимыми случайными величинами, равномерно распределёнными на
0 . . . 𝑘
−
1.
13.2.3. Пусть 𝑡
1
, . . . , 𝑡
𝑛
| произвольная последовательность различ-
ных элементов множества 𝑇 . Рассмотрим количество действий, проис-
ходящих при помещении элементов 𝑡
1
, . . . , 𝑡
𝑛
в множество, хешируемое
с помощью функции ℎ из универсального семейства 𝐻. Докажите, что
среднее количество действий (усреднение | по всем ℎ из 𝐻) не превос-
ходит 𝐶𝑛(1 + 𝑛/𝑘).
Решение. Обозначим через 𝑚
𝑖
количество элементов последователь-
ности, для которых хеш-функция равна 𝑖. (Числа 𝑚
0
, . . . , 𝑚
𝑘
−
1
зави-
сят, конечно, от выбора хеш-функции.) Количество действий, кото-
рое мы хотим оценить, с точностью до постоянного множителя рав-
но 𝑚
2
0
+ 𝑚
2
1
+ . . . + 𝑚
2
𝑘
−
1
. (Если 𝑠 чисел попадают в одну хеш-ячейку,
то для этого требуется примерно 1 + 2 + . . . + 𝑠 действий.) Эту же
сумму квадратов можно записать как число пар
⟨
𝑝, 𝑞
⟩
, для которых
ℎ(𝑡
𝑝
) = ℎ(𝑡
𝑞
). Последнее равенство, если его рассматривать как собы-
тие при фиксированных 𝑝 и 𝑞, имеет вероятность 1/𝑘 при 𝑝
̸
= 𝑞, поэтому
среднее значение соответствующего члена суммы равно 1/𝑘, а для всей
суммы получаем оценку порядка 𝑛
2
/𝑘, а точнее 𝑛 + 𝑛
2
/𝑘, если учесть
члены с 𝑝 = 𝑞.
Эта задача показывает, что на каждый добавляемый элемент при-
ходится в среднем 𝐶(1 + 𝑛/𝑘) операций. В этой оценке дробь 𝑛/𝑘 имеет
смысл «коэффициента заполнения» хеш-таблицы.
13.2.4. Докажите аналогичное утверждение для произвольной по-
следовательности операций добавления, поиска и удаления (а не только
для добавления, как в предыдущей задаче).
[Указание. Будем представлять себе, что в ходе поиска, добавле-
ния и удаления элемент проталкивается по списку своих коллег с тем
же хеш-значением, пока не найдёт своего двойника или не дойдёт до
конца списка. Будем называть 𝑖-𝑗-столкновением столкновение 𝑡
𝑖
с 𝑡
𝑗
.
(Оно либо произойдёт, либо нет | в зависимости от ℎ.) Общее чи-
сло действий примерно равно числу всех происшедших столкновений
плюс число элементов. При 𝑡
𝑖
̸
= 𝑡
𝑗
вероятность 𝑖-𝑗-столкновения не пре-
восходит 1/𝑘. Осталось проследить за столкновениями между равными

13.2. Хеширование со списками
247
элементами. Фиксируем некоторое значение 𝑥 из множества 𝑇 и посмо-
трим на связанные с ним операции. Они идут по циклу: добавление |
проверки | удаление | добавление | проверки | удаление | . . .
Столкновения происходят между добавляемым элементом и следующи-
ми за ним проверками (до удаления включительно), поэтому общее их
число не превосходит числа элементов, равных 𝑥.]
Теперь приведём примеры универсальных семейств. Очевидно, для
любых конечных множеств 𝐴 и 𝐵 семейство всех функций, отобража-
ющих 𝐴 в 𝐵, является универсальным. Однако этот пример с практи-
ческой точки зрения бесполезен: для запоминания случайной функции
из этого семейства нужен массив, число элементов в котором равно чи-
слу элементов в множестве 𝐴. (А если мы можем себе позволить такой
массив, то никакого хеширования не требуется!)
Более практичные примеры универсальных семейств могут быть
построены с помощью несложных алгебраических конструкций. Че-
рез
Z
𝑝
мы обозначаем множество вычетов по простому модулю 𝑝, т. е.
{
0, 1, . . . , 𝑝
−
1
}
; арифметические операции в этом множестве выпол-
няются по модулю 𝑝. Универсальное семейство образуют все линей-
ные функционалы на
Z
𝑛
𝑝
со значениями в
Z
𝑝
. Более подробно, пусть
𝑎
1
, . . . , 𝑎
𝑛
| произвольные элементы
Z
𝑝
; рассмотрим отображение
ℎ :
⟨
𝑥
1
. . . 𝑥
𝑛
⟩ ↦→
𝑎
1
𝑥
1
+ . . . + 𝑎
𝑛
𝑥
𝑛
.
Мы получаем семейство из 𝑝
𝑛
отображений
Z
𝑛
𝑝
→
Z
𝑝
параметризован-
ное наборами
⟨
𝑎
1
. . . 𝑎
𝑛
⟩
.
13.2.5. Докажите, что это семейство является универсальным.
[Указание. Пусть 𝑥 и 𝑦 | различные точки пространства
Z
𝑛
𝑝
. Какова
вероятность того, что случайный функционал принимает на них оди-
наковые значения? Другими словами, какова вероятность того, что он
равен нулю на их разности 𝑥
−
𝑦? Ответ даётся таким утверждением:
пусть 𝑢 | ненулевой вектор; тогда все значения случайного функцио-
нала на нём равновероятны.]
В следующей задаче множество
B
=
{
0, 1
}
рассматривается как мно-
жество вычетов по модулю 2.
13.2.6. Семейство всех линейных отображений из
B
𝑛
в
B
𝑚
является
универсальным.
Родственные хешированию идеи неожиданно оказываются полезны-
ми в следующей ситуации (рассказал Д. Варсанофьев). Пусть мы хо-

248
13. Представление множеств. Хеширование
тим написать программу, которая обнаруживала (большинство) опеча-
ток в тексте, но не хотим хранить список всех правильных словоформ.
Предлагается поступить так: выбрать некоторое 𝑁 и набор функций
𝑓
1
, . . . , 𝑓
𝑘
, отображающих русские слова в 1, . . . , 𝑁. В массиве из 𝑁 би-
тов положим все биты равными нулю, кроме тех, которые являются зна-
чением какой-то функции набора на какой-то правильной словоформе.
Теперь приближённый тест на правильность словоформы таков: прове-
рить, что значения всех функций набора на этой словоформе попадают
на места, занятые единицами. (Этот тест может не заметить некото-
рых ошибок, но все правильные словоформы будут одобрены.)

14. ПРЕДСТАВЛЕНИЕ
МНОЖЕСТВ. ДЕРЕВЬЯ.
СБАЛАНСИРОВАННЫЕ
ДЕРЕВЬЯ
14.1. Представление множеств
с помощью деревьев
Полное двоичное дерево. 𝑇 -деревья
Нарисуем точку. Из неё проведём две стрелки (влево вверх и впра-
во вверх) в две другие точки. Из каждой из этих точек проведём по
две стрелки и так далее. Полученную картинку (в 𝑛-м слое будет 2
𝑛
−
1
точек) называют полным двоичным деревом. Нижнюю точку называ-
ют корнем. У каждой вершины есть два сына (две вершины, в которые
идут стрелки) | левый и правый. У всякой вершины, кроме корня, есть
единственный отец.
Пусть выбрано некоторое конечное множество вершин полного дво-
ичного дерева, содержащее вместе с каждой вершиной и всех её пред-
ков. Пусть на каждой вершине этого множества написано значение фик-
сированного типа 𝑇 (то есть задано отображение множества вершин
в множество значений типа 𝑇 ). То, что получится, будем называть 𝑇 -де-
ревом. Множество всех 𝑇 -деревьев обозначим Tree(𝑇 ).
Рекурсивное определение. Всякое непустое 𝑇 -дерево разбивается на
три части: корень (несущий пометку из 𝑇 ), левое и правое поддеревья
(которые могут быть пустыми). Это разбиение устанавливает взаим-
но однозначное соответствие между множеством непустых 𝑇 -деревьев
и произведением 𝑇
×
Tree(𝑇 )
×
Tree(𝑇 ). Обозначив через empty пустое
дерево, можно написать
Tree(𝑇 ) =
{
empty
}
+ 𝑇
×
Tree(𝑇 )
×
Tree(𝑇 ).

250
14. Деревья. Сбалансированные деревья
Поддеревья. Высота
Фиксируем некоторое 𝑇 -дерево. Для каждой его вершины 𝑥 опре-
делено её левое поддерево (левый сын вершины 𝑥 и все его потомки),
правое поддерево (правый сын вершины 𝑥 и все его потомки) и подде-
рево с корнем в 𝑥 (вершина 𝑥 и все её потомки).
q
@
@
@
@
B
B
B
B
корень
левое
правое
Левое и правое поддеревья вершины 𝑥 могут быть пустыми, а подде-
рево с корнем в 𝑥 всегда непусто (содержит по крайней мере 𝑥). Вы-
сотой поддерева будем считать максимальную длину цепи 𝑦
1
. . . 𝑦
𝑛
его
вершин, в которой 𝑦
𝑖+1
| сын 𝑦
𝑖
для всех 𝑖. (Высота дерева из одного
корня равна единице, высота пустого дерева | нулю.)
Упорядоченные 𝑇 -деревья
Пусть на множестве значений типа 𝑇 фиксирован порядок. Назовём
𝑇 -дерево упорядоченным, если выполнено такое свойство: для любой
вершины 𝑥 все пометки в её левом поддереве меньше пометки в 𝑥, а все
пометки в её правом поддереве больше пометки в 𝑥.
r
@
@
@
@
@
B
B
B
B
B
𝑥
< 𝑥
> 𝑥
14.1.1. Докажите, что в упорядоченном дереве все пометки раз-
личны.
[Указание. Индукция по высоте дерева.]
Представление множеств с помощью деревьев
Каждое дерево будем считать представлением множества всех по-
меток на его вершинах. При этом одно и то же множество может иметь
различные представления.

14.1. Представление множеств с помощью деревьев
251
Если дерево упорядочено, то каждый элемент может легко «найти
своё место» в дереве: придя в какую-то вершину и сравнив себя с тем,
кто там находится, элемент решает, идти ему налево или направо.
6
𝑦
𝑥
@
@
I
𝑦 < 𝑥
𝑦 > 𝑥
Начав с корня и двигаясь по этому правилу, он либо обнаружит, что
такой элемент уже есть, либо найдёт место, в котором он должен быть.
Всюду далее мы предполагаем, что на значениях типа 𝑇 задан по-
рядок, и рассматриваем только упорядоченные деревья.
Хранение деревьев в программе
Можно было бы сопоставить вершины полного двоичного дерева
с числами 1, 2, 3, . . . (считая, что левый сын 𝑘 есть 2𝑘, правый сын 𝑘 есть
2𝑘 + 1) и хранить пометки в массиве val[1..n]. Однако этот способ
неэкономен, поскольку тратится место на хранение пустых вакансий
в полном двоичном дереве.
Более экономен такой способ. Введём три массива
val: array [1..n] of T;
left, right: array [1..n] of 0..n;
(n | максимальное возможное число вершин дерева) и переменную
root:0..n. Каждая вершина хранимого 𝑇 -дерева будет иметь номер |
число от 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]], ...

252
14. Деревья. Сбалансированные деревья
Для последнего свободного числа i значение left[i] равно 0. Равен-
ство free=0 означает, что свободных чисел больше нет.
Замечание. Мы использовали для связывания свободных вершин в
список массив left, но, конечно, с тем же успехом можно было исполь-
зовать массив right.
Вместо значения 0 (обозначающего отсутствие вершины) можно бы-
ло бы воспользоваться любым другим числом вне 1..n. Чтобы подчерк-
нуть это, будем вместо 0 использовать константу null=0.
14.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;
14.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

14.1. Представление множеств с помощью деревьев
253
x := right [x];
end;
end;
..ответ: (x <> null).
14.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]}

254
14. Деревья. Сбалансированные деревья
right [x] := i;
end;
end;
end;
14.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;
Удаление вершины использует процедуру
procedure make_free (i: integer);
begin
left [i] := free;
free := i;
end;

14.1. Представление множеств с помощью деревьев
255
Она включает число i в список свободных. При удалении различаются
4 случая в зависимости от наличия или отсутствия сыновей у удаляемой
вершины.
if (left [x] = null) and (right [x] = null) then begin
{x - лист, т.е. не имеет сыновей}
make_free (x);
if x = root then begin
root := null;
end else if direction = l then begin
left [father] := null;
end else begin {direction = r}
right [father] := null;
end;
end else if (left[x]=null) and (right[x] <> null) then begin
{x удаляется, а right [x] занимает место x}
make_free (x);
if x = root then begin
root := right [x];
end else if direction = l then begin
left [father] := right [x];
end else begin {direction = r}
right [father] := right [x];
end;
end else if (left[x] <> null) and (right[x]=null) then begin
..симметрично
end else begin {left [x] <> null, right [x] <> null}
..удалить вершину с двумя сыновьями
end;
Удаление вершины с двумя сыновьями нельзя сделать просто так, но её
можно предварительно поменять с вершиной, пометка на которой явля-
ется непосредственно следующим (в порядке возрастания) элементом за
пометкой на x.
y := right [x];
father := x; direction := r;
{теперь father и direction относятся к вершине y}
while left [y] <> null do begin
father := y; direction := l;
y := left [y];
end;
{val [y] - минимальная из пометок, больших val [x],
y не имеет левого сына}

256
14. Деревья. Сбалансированные деревья
val [x] := val [y];
..удалить вершину y (как удалять вершину, у которой нет
левого сына, мы уже знаем)
14.1.6. Упростите эту программу, заметив, что некоторые случаи
(например, первые два из четырёх) можно объединить.
14.1.7. Используйте упорядоченные деревья для представления
функций, область определения которых | конечные множества значе-
ний типа T, а значения имеют некоторый тип U. Операции: вычисление
значения на данном аргументе, изменение значения на данном аргумен-
те, доопределение функции на данном аргументе, исключение элемента
из области определения функции.
Решение. Делаем как раньше, добавив ещё один массив
func_val: array [1..n] of U;
если val[x] = t, func val[x] = u, то значение хранимой функции на t
равно u.
14.1.8. Предположим, что необходимо уметь также отыскивать k-й
элемент множества (в порядке возрастания), причём количество дей-
ствий должно быть не более 𝐶
·
(высота дерева). Какую дополнитель-
ную информацию надо хранить в вершинах дерева?
Решение. В каждой вершине будем хранить число всех её потомков.
Добавление и исключение вершины требует коррекции лишь на пути от
корня к этой вершине. В процессе поиска k-й вершины поддерживается
такой инвариант: искомая вершина является s-й вершиной поддерева
с корнем в x (здесь s и x | переменные).
Оценка количества действий
Для каждой из операций (проверки, добавления и исключения) коли-
чество действий не превосходит 𝐶
·
(высота дерева). Для «ровно под-
стриженного» дерева (когда все листья на одной высоте) высота по
порядку величины равна логарифму числа вершин. Однако для криво-
бокого дерева всё может быть гораздо хуже: в наихудшем случае все
вершины образуют цепь и высота равна числу вершин. Так случит-
ся, если элементы множества добавляются в возрастающем или убы-
вающем порядке. Можно доказать, однако, что при добавлении эле-
ментов «в случайном порядке» средняя высота дерева будет не больше
𝐶 log(число вершин). Если этой оценки «в среднем» мало, необходимы
дополнительные действия по поддержанию «сбалансированности» дере-
ва. Об этом см. в следующем пункте.

14.2. Сбалансированные деревья
257
14.2. Сбалансированные деревья
Дерево называется сбалансированным (или АВЛ-деревом в честь
изобретателей этого метода Г. М. Адельсона-Вельского и E. М. Ланди-
са), если для любой его вершины высоты левого и правого поддеревьев
этой вершины отличаются не более чем на 1. (В частности, когда од-
ного из сыновей нет, другой | если он есть | обязан быть листом.)
14.2.1. Найдите минимальное и максимальное возможное количе-
ство вершин в сбалансированном дереве высоты 𝑛.
Решение. Максимальное число вершин равно 2
𝑛
−
1. Если 𝑚
𝑛
| ми-
нимальное число вершин, то, как легко видеть, 𝑚
𝑛+2
= 1 + 𝑚
𝑛
+ 𝑚
𝑛+1
,
откуда 𝑚
𝑛
= ˘
𝑛+2
−
1 (˘
𝑛
| 𝑛-е число Фибоначчи, ˘
1
= 1, ˘
2
= 1,
˘
𝑛+2
= ˘
𝑛
+ ˘
𝑛+1
).
14.2.2. Докажите, что сбалансированное дерево с 𝑛 вершинами име-
ет высоту не больше 𝐶 log 𝑛 для некоторой константы 𝐶, не зависящей
от 𝑛.
Решение. Индукцией по 𝑛 легко доказать, что ˘
𝑛+2
>
𝑎
𝑛
, где
𝑎 | больший корень квадратного уравнения 𝑎
2
= 1 + 𝑎, то есть 𝑎 =
= (
√
5 + 1)/2. Остаётся воспользоваться предыдущей задачей.
Вращения
Мы хотим восстанавливать сбалансированность дерева после вклю-
чения и удаления элементов. Для этого необходимы какие-то преобра-
зования дерева, не меняющие множества пометок на его вершинах и не
нарушающие упорядоченности, но способствующие лучшей сбаланси-
рованности. Опишем несколько таких преобразований.
t
𝑎
t
𝑏
t
H
H
H
H
𝑎
t
𝑏
@
@
@
@
@
@
B
B
B
B
B
B
𝑃
@
@
@
@
@
@
B
B
B
B
B
B
𝑄
𝑅
→
𝑄
@
@
@
@
@
@
B
B
B
B
B
B
𝑃
𝑅
Пусть вершина 𝑎 имеет правого сына 𝑏. Обозначим через 𝑃 левое под-
дерево вершины 𝑎, через 𝑄 и 𝑅 | левое и правое поддеревья вершины 𝑏.
Упорядоченность дерева требует, чтобы 𝑃 < 𝑎 < 𝑄 < 𝑏 < 𝑅 (точнее сле-

258
14. Деревья. Сбалансированные деревья
довало бы сказать «любая пометка на 𝑃 меньше пометки на 𝑎», «пометка
на 𝑎 меньше любой пометки на 𝑄» и т. д., но мы позволим себе этого
не делать). Точно того же требует упорядоченность дерева с корнем 𝑏,
его левым сыном 𝑎, в котором 𝑃 и 𝑄 | левое и правое поддеревья 𝑎,
𝑅 | правое поддерево 𝑏. Поэтому первое дерево можно преобразо-
вать во второе, не нарушая упорядоченности. Такое преобразование
назовём малым правым вращением (правым | поскольку существует
симметричное, левое, малым | поскольку есть и большое, которое мы
сейчас опишем).
Пусть 𝑏 | правый сын 𝑎, 𝑐 | левый сын 𝑏, 𝑃 | левое поддерево 𝑎,
𝑄 и 𝑅 | левое и правое поддеревья 𝑐, 𝑆 | правое поддерево 𝑏. Тогда
𝑃 < 𝑎 < 𝑄 < 𝑐 < 𝑅 < 𝑏 < 𝑆.
s
s
s
s
s
s
H
H
H
Q
Q
Q
Q
𝑎
𝑏
𝑐
𝑐
𝑎
𝑏
@
@
@
@
B
B
B
B
𝑃
@
@
@
@
B
B
B
B
𝑄
𝑅
𝑆
→
@
@
@
@
B
B
B
B
𝑃
𝑄
J
J
J
J
𝑅
𝑆
Такой же порядок соответствует дереву с корнем 𝑐, имеющим левого
сына 𝑎 и правого сына 𝑏, для которого 𝑃 и 𝑄 | поддеревья вершины 𝑎,
а 𝑅 и 𝑆 | поддеревья вершины 𝑏. Соответствующее преобразование
будем называть большим правым вращением. (Аналогично определяет-
ся симметричное ему большое левое вращение.)
14.2.3. Дано дерево, сбалансированное всюду, кроме корня, в ко-
тором разница высот равна 2 (т. е. левое и правое поддеревья корня
сбалансированы и их высоты отличаются на 2). Докажите, что оно мо-
жет быть превращено в сбалансированное одним из четырёх описанных
преобразований, причём высота его останется прежней или уменьшит-
ся на 1.
Решение. Пусть более низким является, например, левое поддерево,
и его высота равна 𝑘. Тогда высота правого поддерева равна 𝑘 + 2.
Обозначим корень через 𝑎, а его правого сына (он обязательно есть)
через 𝑏. Рассмотрим левое и правое поддеревья вершины 𝑏. Одно из них
обязательно имеет высоту 𝑘 + 1, а другое может иметь высоту 𝑘 или
𝑘 + 1 (меньше 𝑘 быть не может, так как поддеревья сбалансированы).

14.2. Сбалансированные деревья
259
Если высота левого поддерева равна 𝑘 + 1, а правого | 𝑘, то потребу-
ется большое правое вращение; в остальных случаях помогает малое.
Вот как выглядят три случая балансировки дерева:
@
@
𝑎
s
𝑏
s
s
s
@
@
@
A
A
A
@
@
@
A
A
A
→
@
@
@
A
A
A
@
@
s
𝑎
s
𝑏
s
s
@
@
@
A
A
A
J
J
J
J
B
B
B
B
→
@
@
@
A
A
A
@
@
@
@
𝑎
s
s
𝑏
s
s
s
s
@
@
@
@
J
J
J
J
@
@
@
A
A
A
@
@
@
@
A
A
A
A
→
@
@
@
@
J
J
J
J
A
A
A
A
A
A
A
?
?
?
?
14.2.4. В сбалансированное дерево добавили или из него удалили
лист. Докажите, что можно восстановить сбалансированность с помо-
щью нескольких вращений, причём их число не больше высоты дерева.
Решение. Будем доказывать более общий факт:
Лемма. Если в сбалансированном дереве 𝑋 одно из его поддере-
вьев 𝑌 заменили на сбалансированное дерево 𝑍, причём высота 𝑍 от-
личается от высоты 𝑌 не более чем на 1, то полученное такой «привив-
кой» дерево можно превратить в сбалансированное вращениями (при-
чём количество вращений не превосходит высоты, на которой делается
прививка).
Частным случаем прививки является замена пустого поддерева на
лист или наоборот, так что достаточно доказать эту лемму.
Доказательство леммы. Индукция по высоте, на которой делается
прививка. Если она происходит в корне (заменяется всё дерево цели-

260
14. Деревья. Сбалансированные деревья
ком), то всё очевидно («привой» сбалансирован по условию). Пусть за-
меняется некоторое поддерево, например, левое поддерево некоторой
вершины 𝑥. Возможны два случая.
1) После прививки сбалансированность в вершине 𝑥 не нарушилась
(хотя, возможно, нарушилась сбалансированность в предках 𝑥:
высота поддерева с корнем в 𝑥 могла измениться). Тогда можно
сослаться на предположение индукции, считая, что мы прививали
целиком поддерево с корнем в 𝑥.
2) Сбалансированность в 𝑥 нарушилась. При этом разница высот
равна 2 (больше она быть не может, так как высота 𝑍 отличается
от высоты 𝑌 не более чем на 1). Разберём два варианта.
s
@
@
@
A
A
A
@
@
@
@
A
A
A
A
𝑌
𝑍
𝑘
s
A
A
A
A
A
A
𝑌
𝑍
𝑘
(а)
(б)
а) Выше правое (не заменявшееся) поддерево вершины 𝑥. Пусть
высота левого (т. е. 𝑍) равна 𝑘, правого | 𝑘 + 2. Высота ста-
рого левого поддерева вершины 𝑥 (т. е. 𝑌 ) была равна 𝑘 + 1.
Поддерево с корнем 𝑥 имело в исходном дереве высоту 𝑘 + 3,
и эта высота не изменилась после прививки.
По предыдущей задаче вращение преобразует поддерево с
корнем в 𝑥 в сбалансированное поддерево высоты 𝑘 + 2 или
𝑘 + 3. То есть высота поддерева с корнем 𝑥 | в сравнении
с его прежней высотой | не изменилась или уменьшилась
на 1, и мы можем воспользоваться предположением индук-
ции.
б) Выше левое поддерево вершины 𝑥. Пусть высота левого
(т. е. 𝑍) равна 𝑘 + 2, правого | 𝑘. Высота старого левого
поддерева (т. е. 𝑌 ) была равна 𝑘 + 1. Поддерево с корнем 𝑥
в исходном дереве 𝑋 имело высоту 𝑘 + 2, после прививки она
стала равна 𝑘 + 3. После подходящего вращения (см. преды-
дущую задачу) поддерево с корнем в 𝑥 станет сбалансиро-
ванным, его высота будет равна 𝑘 + 2 или 𝑘 + 3, так что
изменение высоты по сравнению с высотой поддерева с кор-
нем 𝑥 в дереве 𝑋 не превосходит 1 и можно сослаться на
предположение индукции.

14.2. Сбалансированные деревья
261
14.2.5. Составьте программы добавления и удаления элементов, со-
храняющие сбалансированность. Число действий не должно превосхо-
дить 𝐶
·
(высота дерева). Разрешается хранить в вершинах дерева до-
полнительную информацию, необходимую при балансировке.
Решение. Будем хранить для каждой вершины разницу между вы-
сотой её правого и левого поддеревьев:
diff [i] = (высота правого поддерева вершины i)
−
−
(высота левого поддерева вершины i).
Нам потребуются четыре процедуры, соответствующие большим и ма-
лым правым и левым вращениями. Но вначале два замечания. (1) Нам
нужно, чтобы при вращении поддерева номер его корня не менялся.
(В противном случае потребовалось бы корректировать информацию
в отце корня, что нежелательно.) Этого можно достичь, так как но-
мера вершин дерева можно выбирать независимо от их значений. (На
картинках номер указан сбоку от вершины, а значение | внутри.)
𝑎
𝑏
𝑏
𝑎
@
@
@
@
I
@
@
@
𝑃
@
@
@
𝑄
𝑅
𝛼
𝛽
→
@
@
@
𝑃
𝑄
𝑅
𝛼
𝛽
𝑎
𝑏
𝑐
𝑏
𝑎
𝑐
@
@
@
@
I
H
H
H
Y
*
@
@
@
𝑃
@
@
@
𝑄
𝑅
𝑆
𝛼
𝛽
𝛾
→
@
@
@
𝑃
𝑄
@
@
@
𝑅
𝑆
𝛼
𝛾
𝛽
(2) После преобразований мы должны также изменить соответственно
значения в массиве diff. Для этого достаточно знать высоты деревьев
𝑃, 𝑄, . . . с точностью до константы, поэтому можно предполагать, что
одна из высот равна нулю.

262
14. Деревья. Сбалансированные деревья
Вот процедуры вращений:
procedure SR (a:integer); {малое правое вращение с корнем a}
var b: 1..n; val_a,val_b: T; h_P,h_Q,h_R: integer;
begin
b := right [a]; {b <> null}
val_a := val [a]; val_b := val [b];
h_Q := 0; h_R := diff[b]; h_P := (max(h_Q,h_R)+1)-diff[a];
val [a] := val_b; val [b] := val_a;
right [a] := right [b] {поддерево R}
right [b] := left [b] {поддерево Q}
left [b] := left [a] {поддерево P}
left [a] := b;
diff [b] := h_Q - h_P;
diff [a] := h_R - (max (h_P, h_Q) + 1);
end;
procedure BR(a:integer);{большое правое вращение с корнем a}
var b,c: 1..n; val_a,val_b,val_c: T;
h_P,h_Q,h_R,h_S: integer;
begin
b := right [a]; c := left [b]; {b,c <> null}
val_a := val [a]; val_b := val [b]; val_c := val [c];
h_Q := 0; h_R := diff[c]; h_S := (max(h_Q,h_R)+1)+diff[b];
h_P := 1 + max (h_S, h_S-diff[b]) - diff [a];
val [a] := val_c; val [c] := val_a;
left [b] := right [c] {поддерево R}
right [c] := left [c] {поддерево Q}
left [c] := left [a] {поддерево P}
left [a] := c;
diff [b] := h_S - h_R;
diff [c] := h_Q - h_P;
diff [a] := max (h_S, h_R) - max (h_P, h_Q);
end;
Левые вращения (большое и малое) записываются симметрично.
Процедуры добавления и удаления элементов пишутся как раньше,
но только добавление и удаление должно сопровождаться коррекцией
массива diff и восстановлением сбалансированности.
При этом используется процедура с такими свойствами:
дано: левое и правое поддеревья вершины с номером a
сбалансированы, в самой вершине разница высот не боль-
ше 2, в поддереве с корнем a массив diff заполнен пра-
вильно;

14.2. Сбалансированные деревья
263
надо: поддерево с корнем a сбалансировано и массив diff
соответственно изменён, d | изменение его высоты (равно 0
или -1); в остальной части всё осталось как было | в част-
ности, значения diff.
procedure balance (a: integer; var d: integer);
begin {-2 <= diff[a] <= 2}
if diff [a] = 2 then begin
b := right [a];
if diff [b] = -1 then begin
BR (a); d := -1;
end else if diff [b] = 0 then begin
SR (a); d := 0;
end else begin {diff [b] = 1}
SR (a); d := - 1;
end;
end else if diff [a] = -2 then begin
b := left [a];
if diff [b] = 1 then begin
BL (a); d := -1;
end else if diff [b] = 0 then begin
SL (a); d := 0;
end else begin {diff [b] = -1}
SL (a); d := - 1;
end;
end else begin {-2 < diff [a] < 2, ничего делать не надо}
d := 0;
end;
end;
Восстановление сбалансированности требует движения от листьев
к корню, поэтому будем хранить в стеке путь от корня дерева к рас-
сматриваемой в данный момент вершине. Элементами стека будут пары
⟨
вершина, направление движения из неё
⟩
, т. е. значения типа
record
vert: 1..n; {вершина}
direction : (l, r); {l - левое, r - правое}
end;
Программа добавления элемента t теперь выглядит так:
if root = null then begin
get_free (root);
left[root] := null; right[root] := null; diff[root] := 0;

264
14. Деревья. Сбалансированные деревья
val[root] := t;
end else begin
x := root;
..сделать стек пустым
{инвариант: осталось добавить t к непустому поддереву с
корнем в x; стек содержит путь к 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); val [i] := t;
left [i] := null; right [i] := null; diff [i] := 0;
if t < val [x] then begin
..добавить в стек пару 
left [x] := i;
end else begin {t > val [x]}
..добавить в стек пару 
right [x] := i;
end;
d := 1;
{инвариант: стек содержит путь к изменившемуся
поддереву, высота которого увеличилась по сравнению
с высотой в исходном дереве на d (=0 или 1); это
поддерево сбалансировано; значения diff для его
вершин правильны; в остальном дереве всё осталось
как было - в частности, значения diff}
while (d <> 0) and ..стек непуст do begin {d = 1}
..взять из стека пару в 
if direct = l then begin
if diff [v] = 1 then begin
c := 0;
end else begin
c := 1;
end;
diff [v] := diff [v] - 1;
end else begin
{direct = r}

14.2. Сбалансированные деревья
265
if diff [v] = -1 then begin
c := 0;
end else begin
c := 1;
end;
diff [v] := diff [v] + 1;
end;
{c = изменение высоты поддерева с корнем в v по
сравнению с исходным деревом; массив diff
содержит правильные значения для этого поддерева;
возможно нарушение сбалансированности в v}
balance (v, d1); d := c + d1;
end;
end;
end;
Легко проверить, что значение d может быть равно только 0 или 1 (но
не -1): если c=0, то diff[v]=0 и балансировка не производится.
Программа удаления строится аналогично. Её основной фрагмент
таков:
{инвариант: стек содержит путь к изменившемуся поддереву,
высота которого изменилась по сравнению с высотой в
исходном дереве на d (=0 или -1); это поддерево
сбалансировано; значения diff для его вершин правильны;
в остальном дереве всё осталось как было -
в частности, значения diff}
while (d <> 0) and ..стек непуст do begin
{d = -1}
..взять из стека пару в 
if direct = l then begin
if diff [v] = -1 then begin
c := -1;
end else begin
c := 0;
end;
diff [v] := diff [v] + 1;
end else begin {direct = r}
if diff [v] = 1 then begin
c := -1;
end else begin
c := 0;
end;
diff [v] := diff [v] - 1;
end;

266
14. Деревья. Сбалансированные деревья
{c = изменение высоты поддерева с корнем в v по
сравнению с исходным деревом; массив diff содержит
правильные значения для этого поддерева;
возможно нарушение сбалансированности в v}
balance (v, d1);
d := c + d1;
end;
Легко проверить, что значение d может быть равно только 0 или -1 (но
не -2): если c=-1, то diff[v]=0 и балансировка не производится.
Отметим также, что наличие стека делает излишними переменные
father и direction (их роль теперь играет вершина стека).
14.2.6. Докажите, что при добавлении элемента
(а) второй из трёх случаев балансировки (см. рисунок на с.
259
)
невозможен;
(б) полная балансировка требует не более одного вращения (после
чего всё дерево становится сбалансированным), в то время как при
удалении элемента может понадобиться много вращений.
Замечание. Мы старались записать программы добавления и уда-
ления так, чтобы они были как можно более похожими друг на друга.
Используя специфику каждой из них, можно многое упростить.
Существуют и другие способы представления множеств, гаранти-
рующие число действий порядка log 𝑛 на каждую операцию. Опишем
один из них (называемый Б-деревьями).
До сих пор каждая вершина содержала один элемент хранимого мно-
жества. Этот элемент служил границей между левым и правым подде-
ревом. Будем теперь хранить в вершине 𝑘
>
1 элементов множества
(число 𝑘 может меняться от вершины к вершине, а также при добавле-
нии и удалении новых элементов, см. далее). Эти 𝑘 элементов служат

жүктеу/скачать 1,66 Mb.

Достарыңызбен бөлісу: