А. шень Издание шестое, дополненное Москва

• Название: А. шень Издание шестое, дополненное Москва
• Дата: 17.09.2022
• Размер: 1.62 Mb.
• Имя файла: shen-progbook.pdf
• Тип: Книга; #681926
• страница: 16 из 19

где 𝑟 | некоторое отображение {0, . . . , 𝑛 − 1} в себя. Какие при этом будут трудности?
Ответ. (1) Не гарантируется, что если пустые места есть, то мы их найдём. (2) При удалении неясно, как заполнять дыры. (На практи- ке во многих случаях удаление не нужно, так что такой способ также применяется. Считается, что удачный подбор функции 𝑟 может пре- дотвратить образование «скоплений» занятых ячеек.)

13.1.4. Пусть для хранения множества всех правильных русских слов в программе проверки орфографии используется хеширование.

Что нужно добавить, чтобы к тому же уметь находить английский перевод любого правильного слова?
Решение. Помимо массива val, элементы которого являются русски- ми словами, нужен параллельный массив их английских переводов. 
13.2. Хеширование со списками
На хеш-функцию с 𝑘 значениями можно смотреть как на способ све- сти вопрос о хранении одного большого множества к вопросу о хране- нии нескольких меньших. Именно, если у нас есть хеш-функция с 𝑘 зна- чениями, то любое множество разбивается на 𝑘 подмножеств (возмож- но, пустых), соответствующих возможным значениям хеш-функции.
Вопрос о проверке принадлежности, добавлении или удалении для боль- шого множества сводится к такому же вопросу для одного из меньших
(чтобы узнать, для какого, надо посмотреть на значение хеш-функции).
Эти меньшие множества удобно хранить с помощью ссылок; их сум- марный размер равен числу элементов хешируемого множества. Следу- ющая задача предлагает реализовать этот план.
13.2.1. Пусть хеш-функция принимает значения 1 . . . k. Для каждо- го значения хеш-функции рассмотрим список всех элементов множе-

13.2. Хеширование со списками
245
ства с данным значением хеш-функции. Будем хранить эти 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;

246 13. Представление множеств. Хеширование
{осталось искать в списке, начиная с 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/𝑘. (Дру-

13.2. Хеширование со списками
247
гими словами, те функции из 𝐻, для которых ℎ(𝑠) = ℎ(𝑡), составляют
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/𝑘. Осталось проследить за столкновениями между равными

248 13. Представление множеств. Хеширование элементами. Фиксируем некоторое значение 𝑥 из множества 𝑇 и посмо- трим на связанные с ним операции. Они идут по циклу: добавление |
проверки | удаление | добавление | проверки | удаление | . . .
Столкновения происходят между добавляемым элементом и следующи- ми за ним проверками (до удаления включительно), поэтому общее их число не превосходит числа элементов, равных 𝑥.]

Теперь приведём примеры универсальных семейств. Очевидно, для любых конечных множеств 𝐴 и 𝐵 семейство всех функций, отобража- ющих 𝐴 в 𝐵, является универсальным. Однако этот пример с практи- ческой точки зрения бесполезен: для запоминания случайной функции из этого семейства нужен массив, число элементов в котором равно чи- слу элементов в множестве 𝐴. (А если мы можем себе позволить такой массив, то никакого хеширования не требуется!)
Более практичные примеры универсальных семейств могут быть построены с помощью несложных алгебраических конструкций. Че- рез 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
𝑚
является универсальным.

Родственные хешированию идеи неожиданно оказываются полезны- ми в следующей ситуации (рассказал Д. Варсанофьев). Пусть мы хо-

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

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

14.1. Представление множеств с помощью деревьев
251
Поддеревья. Высота
Фиксируем некоторое 𝑇 -дерево. Для каждой его вершины 𝑥 опре- делено её левое поддерево (левый сын вершины 𝑥 и все его потомки),
правое поддерево (правый сын вершины 𝑥 и все его потомки) и подде- рево с корнем в 𝑥 (вершина 𝑥 и все её потомки).
q
@
@
@
@
B
B
B
B




корень левое правое
Левое и правое поддеревья вершины 𝑥 могут быть пустыми, а подде- рево с корнем в 𝑥 всегда непусто (содержит по крайней мере 𝑥). Вы- сотой поддерева будем считать максимальную длину цепи 𝑦
1
. . . 𝑦
𝑛
его вершин, в которой 𝑦
𝑖+1
| сын 𝑦
𝑖
для всех 𝑖. (Высота дерева из одного корня равна единице, высота пустого дерева | нулю.)
Упорядоченные 𝑇 -деревья
Пусть на множестве значений типа 𝑇 фиксирован порядок. Назовём
𝑇 -дерево упорядоченным, если выполнено такое свойство: для любой вершины 𝑥 все пометки в её левом поддереве меньше пометки в 𝑥, а все пометки в её правом поддереве больше пометки в 𝑥.
r
@
@
@
@
@
B
B
B
B
B





𝑥
< 𝑥
> 𝑥
14.1.1. Докажите, что в упорядоченном дереве все пометки раз- личны.
[Указание. Индукция по высоте дерева.]

Представление множеств с помощью деревьев
Каждое дерево будем считать представлением множества всех по- меток на его вершинах. При этом одно и то же множество может иметь различные представления.

252 14. Деревья. Сбалансированные деревья
Если дерево упорядочено, то каждый элемент может легко «найти своё место» в дереве: придя в какую-то вершину и сравнив себя с тем,
кто там находится, элемент решает, идти ему налево или направо.
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]], ...

14.1. Представление множеств с помощью деревьев
253
Для последнего свободного числа 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

254 14. Деревья. Сбалансированные деревья 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]}

14.1. Представление множеств с помощью деревьев
255
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;

256 14. Деревья. Сбалансированные деревья
Она включает число 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 не имеет левого сына}

14.1. Представление множеств с помощью деревьев
257
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(число вершин). Если этой оценки «в среднем» мало, необходимы дополнительные действия по поддержанию «сбалансированности» дере- ва. Об этом см. в следующем пункте.

258 14. Деревья. Сбалансированные деревья
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
𝑃






𝑅
Пусть вершина 𝑎 имеет правого сына 𝑏. Обозначим через 𝑃 левое под- дерево вершины 𝑎, через 𝑄 и 𝑅 | левое и правое поддеревья вершины 𝑏.
Упорядоченность дерева требует, чтобы 𝑃 < 𝑎 < 𝑄 < 𝑏 < 𝑅 (точнее сле-

14.2. Сбалансированные деревья
259
довало бы сказать «любая пометка на 𝑃 меньше пометки на 𝑎», «пометка на 𝑎 меньше любой пометки на 𝑄» и т. д., но мы позволим себе этого не делать). Точно того же требует упорядоченность дерева с корнем 𝑏,
его левым сыном 𝑎, в котором 𝑃 и 𝑄 | левое и правое поддеревья 𝑎,
𝑅 | правое поддерево 𝑏. Поэтому первое дерево можно преобразо- вать во второе, не нарушая упорядоченности. Такое преобразование назовём малым правым вращением (правым | поскольку существует симметричное, левое, малым | поскольку есть и большое, которое мы сейчас опишем).
Пусть 𝑏 | правый сын 𝑎, 𝑐 | левый сын 𝑏, 𝑃 | левое поддерево 𝑎,
𝑄 и 𝑅 | левое и правое поддеревья 𝑐, 𝑆 | правое поддерево 𝑏. Тогда
𝑃 < 𝑎 < 𝑄 < 𝑐 < 𝑅 < 𝑏 < 𝑆.
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 (меньше 𝑘 быть не может, так как поддеревья сбалансированы).

260 14. Деревья. Сбалансированные деревья
Если высота левого поддерева равна 𝑘 + 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, то полученное такой «привив- кой» дерево можно превратить в сбалансированное вращениями (при- чём количество вращений не превосходит высоты, на которой делается прививка).
Частным случаем прививки является замена пустого поддерева на лист или наоборот, так что достаточно доказать эту лемму.
Доказательство леммы. Индукция по высоте, на которой делается прививка. Если она происходит в корне (заменяется всё дерево цели-

14.2. Сбалансированные деревья
261
ком), то всё очевидно («привой» сбалансирован по условию). Пусть за- меняется некоторое поддерево, например, левое поддерево некоторой вершины 𝑥. Возможны два случая.
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 и можно сослаться на предположение индукции.


262 14. Деревья. Сбалансированные деревья
14.2.5. Составьте программы добавления и удаления элементов, со- храняющие сбалансированность. Число действий не должно превосхо- дить 𝐶 · (высота дерева). Разрешается хранить в вершинах дерева до- полнительную информацию, необходимую при балансировке.
Решение. Будем хранить для каждой вершины разницу между вы- сотой её правого и левого поддеревьев:
diff [i] = (высота правого поддерева вершины i) −
−
(высота левого поддерева вершины i).
Нам потребуются четыре процедуры, соответствующие большим и ма- лым правым и левым вращениями. Но вначале два замечания. (1) Нам нужно, чтобы при вращении поддерева номер его корня не менялся.
(В противном случае потребовалось бы корректировать информацию в отце корня, что нежелательно.) Этого можно достичь, так как но- мера вершин дерева можно выбирать независимо от их значений. (На картинках номер указан сбоку от вершины, а значение | внутри.)
𝑎
𝑏
𝑏
𝑎

@
@
@
@
I
@
@
@
𝑃
@
@
@
𝑄
𝑅
𝛼
𝛽
→
@
@
@
𝑃
𝑄
𝑅
𝛼
𝛽
𝑎
𝑏
𝑐
𝑏
𝑎
𝑐

@
@
@
@
I
H
H
H
Y



*
@
@
@
𝑃
@
@
@
𝑄
𝑅
𝑆
𝛼
𝛽
𝛾
→
@
@
@
𝑃
𝑄
@
@
@
𝑅
𝑆
𝛼
𝛾
𝛽
(2) После преобразований мы должны также изменить соответственно значения в массиве diff. Для этого достаточно знать высоты деревьев
𝑃, 𝑄, . . . с точностью до константы, поэтому можно предполагать, что одна из высот равна нулю.

14.2. Сбалансированные деревья
263
Вот процедуры вращений:
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 заполнен пра- вильно;

264 14. Деревья. Сбалансированные деревья надо: поддерево с корнем 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;

14.2. Сбалансированные деревья
265
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}

266 14. Деревья. Сбалансированные деревья 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;

14.2. Сбалансированные деревья
267
{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. Докажите, что при добавлении элемента
(а) второй из трёх случаев балансировки (см. рисунок на с.
260
)
невозможен;
(б) полная балансировка требует не более одного вращения (после чего всё дерево становится сбалансированным), в то время как при удалении элемента может понадобиться много вращений.

Замечание. Мы старались записать программы добавления и уда- ления так, чтобы они были как можно более похожими друг на друга.
Используя специфику каждой из них, можно многое упростить.
Существуют и другие способы представления множеств, гаранти- рующие число действий порядка log 𝑛 на каждую операцию. Опишем один из них (называемый Б-деревьями).
До сих пор каждая вершина содержала один элемент хранимого мно- жества. Этот элемент служил границей между левым и правым подде- ревом. Будем теперь хранить в вершине 𝑘 > 1 элементов множества
(число 𝑘 может меняться от вершины к вершине, а также при добавле- нии и удалении новых элементов, см. далее). Эти 𝑘 элементов служат разделителями для 𝑘 + 1 поддеревьев. Пусть фиксировано некоторое число 𝑡 > 1. Будем рассматривать деревья, обладающие такими свойст- вами:
1) Каждая вершина содержит от 𝑡 до 2𝑡 элементов (за исключени- ем корня, который может содержать любое число элементов от 0
до 2𝑡).
2) Вершина с 𝑘 элементами либо имеет 𝑘 + 1 сыновей, либо не имеет сыновей вообще (является листом).
3) Все листья находятся на одной и той же высоте.

268 14. Деревья. Сбалансированные деревья
Добавление элемента происходит так. Если лист, в который он по- падает, неполон (т. е. содержит менее 2𝑡 элементов), то нет проблем.
Если он полон, то 2𝑡 + 1 элемент (все элементы листа и новый элемент)
разбиваем на два листа по 𝑡 элементов и разделяющий их серединный элемент. Этот серединный элемент надо добавить в вершину предыду- щего уровня. Это возможно, если в ней менее 2𝑡 элементов. Если и она полна, то её разбивают на две, выделяют серединный элемент и т. д. Ес- ли в конце концов мы захотим добавить элемент в корень, а он окажет- ся полным, то корень расщепляется на две вершины, а высота дерева увеличивается на 1.
Удаление элемента, находящегося не в листе, сводится к удалению непосредственно следующего за ним, который находится в листе. По- этому достаточно научиться удалять элемент из листа. Если лист при этом становится слишком маленьким, то его можно пополнить за счёт соседнего листа | если только и он не имеет минимально возможный размер 𝑡. Если же оба листа имеют размер 𝑡, то на них вместе 2𝑡 эле- ментов, вместе с разделителем | 2𝑡 + 1. После удаления одного эле- мента остаётся 2𝑡 элементов | как раз на один лист. Если при этом вершина предыдущего уровня становится меньше нормы, процесс по- вторяется и т. д.
14.2.7. Реализуйте описанную схему хранения множеств, убедив- шись, что она также позволяет обойтись 𝐶 log 𝑛 действий для операций включения, исключения и проверки принадлежности.

14.2.8. Можно определять сбалансированность дерева иначе: требо- вать, чтобы для каждой вершины её левое и правое поддеревья имели не слишком сильно отличающиеся количества вершин. (Преимущество такого определения состоит в том, что при вращениях не нарушается сбалансированность в вершинах, находящихся ниже точки вращения.)
Реализуйте на основе этой идеи способ хранения множеств, гаранти- рующий оценку в 𝐶 log 𝑛 действий для включения, удаления и проверки принадлежности.
[Указание. Он также использует большие и малые вращения. По- дробности см. в книге Рейнгольда, Нивергельта и Део «Комбинаторные алгоритмы».]


15. КОНТЕКСТНО-СВОБОДНЫЕ
ГРАММАТИКИ
15.1. Общий алгоритм разбора
Чтобы определить то, что называют контекстно-свободной грам- матикой (КС-грамматикой), надо:
∙
указать конечное множество 𝐴, называемое алфавитом; его эле- менты называют символами; конечные последовательности сим- волов называют словами (в данном алфавите);
∙
разделить все символы алфавита 𝐴 на две группы: терминальные
(«окончательные») и нетерминальные («промежуточные»);
∙
выбрать среди нетерминальных символов один, называемый на- чальным;
∙
указать конечное число правил грамматики, каждое из которых должно иметь вид 𝐾 → 𝑋, где 𝐾 | некоторый нетерминальный символ, а 𝑋 | слово (в него могут входить и терминальные, и не- терминальные символы).
Пусть фиксирована КС-грамматика (мы часто будем опускать пре- фикс «КС-», так как других грамматик у нас не будет). Выводом в этой грамматике называется последовательность слов 𝑋
0
, 𝑋
1
, . . . , 𝑋
𝑛
, в ко- торой 𝑋
0
состоит из одного символа, и этот символ | начальный,
а 𝑋
𝑖+1
получается из 𝑋
𝑖
заменой некоторого нетерминального сим- вола 𝐾 на слово 𝑋 по одному из правил грамматики. Слово, соста- вленное из терминальных символов, называется выводимым, если суще- ствует вывод, который им кончается. Множество всех выводимых слов
(из терминальных символов) называется языком, порождаемым данной грамматикой.

270 15. Контекстно-свободные грамматики
В этой и следующей главе нас будет интересовать такой вопрос:
дана КС-грамматика; построить алгоритм, который по любому слову проверяет, выводимо ли оно в этой грамматике.
Пример 1. Алфавит:
( ) [ ] E
(четыре терминальных символа и один нетерминальный символ E). На- чальный символ: E. Правила:
E → (E)
E → [E]
E → EE
E →
(в последнем правиле справа стоит пустое слово).
Примеры выводимых слов:
(пустое слово)
()
([ ])
()[([ ])]
[()[ ]()[ ]]
Примеры невыводимых слов:
(
)(
(]
([)]
Эта грамматика встречалась в разделе
6.1
(где выводимость в ней про- верялась с помощью стека).
Пример 2. Другая грамматика, порождающая тот же язык:
Алфавит: ( ) [ ] T E
Правила:
E →
E → TE
T → (E)
T → [E]

15.1. Общий алгоритм разбора
271
Начальным символом во всех приводимых далее примерах будем счи- тать символ, стоящий в левой части первого правила (в данном случае это символ E), не оговаривая этого особо.
Для каждого нетерминального символа можно рассмотреть множе- ство всех слов из терминальных символов, которые из него выводятся
(аналогично тому, как это сделано для начального символа в определе- нии выводимости в грамматике). Каждое правило грамматики можно рассматривать как свойство этих множеств. Покажем это на примере только что приведённой грамматики. Пусть 𝑇 и 𝐸 | множества слов
(из скобок), выводимых из нетерминалов T и E соответственно. Тогда правилам грамматики соответствуют такие свойства:
E →
𝐸 содержит пустое слово
E → TE
если слово 𝐴 принадлежит 𝑇 ,
а слово 𝐵 принадлежит 𝐸, то слово 𝐴𝐵 принадлежит 𝐸
T → [E] если 𝐴 принадлежит 𝐸, то слово
[𝐴] принадлежит 𝑇
T → (E) если 𝐴 принадлежит 𝐸, то слово
(𝐴) принадлежит 𝑇
Сформулированные свойства множеств 𝐸, 𝑇 не определяют эти мно- жества однозначно (например, они остаются верными, если в каче- стве 𝐸 и 𝑇 взять множество всех слов). Однако можно доказать, что множества, задаваемые грамматикой, являются минимальными среди удовлетворяющих этим условиям.
15.1.1. Сформулируйте точно и докажите это утверждение для про- извольной контекстно-свободной грамматики.

15.1.2. Постройте грамматику, в которой выводимы слова
(а) 00..0011..11 (число нулей равно числу единиц);
(б) 00..0011..11 (число нулей вдвое больше числа единиц);
(в) 00..0011..11 (число нулей больше числа единиц);
(и только они).

15.1.3. Докажите, что не существует КС-грамматики, в которой были бы выводимы слова вида 00..0011..1122..22, в которых числа нулей, единиц и двоек равны, и только они.
[Указание. Докажите следующую лемму о произвольной КС-грам- матике: для любого достаточно длинного слова 𝐹 , выводимого в этой грамматике, существует такое его представление в виде 𝐴𝐵𝐶𝐷𝐸, что

272 15. Контекстно-свободные грамматики любое слово вида 𝐴𝐵 . . . 𝐵𝐶𝐷 . . . 𝐷𝐸, где 𝐵 и 𝐷 повторены одинаковое число раз, также выводимо в этой грамматике. (Это можно устано- вить, найдя нетерминальный символ, оказывающийся своим собствен- ным «наследником» в процессе вывода.)]

Нетерминальный символ можно рассматривать как «родовое имя»
для выводимых из него слов. В следующем примере для наглядности в качестве нетерминальных символов использованы фрагменты рус- ских слов, заключённые в угловые скобки. (С точки зрения грамматики каждый такой фрагмент | один символ!)
Пример 3. Алфавит:
терминалы:
+ * ( ) x нетерминалы:
⟨
выр⟩ ⟨оствыр⟩ ⟨слаг⟩ ⟨остслаг⟩ ⟨множ⟩
Правила:
⟨
выр⟩ → ⟨слаг⟩ ⟨оствыр⟩
⟨
оствыр⟩ → + ⟨выр⟩
⟨
оствыр⟩ →
⟨
слаг⟩ → ⟨множ⟩ ⟨остслаг⟩
⟨
остслаг⟩ → * ⟨слаг⟩
⟨
остслаг⟩ →
⟨
множ⟩ → x
⟨
множ⟩ → ( ⟨выр⟩ )
Согласно этой грамматике, выражение ⟨выр⟩ | это последователь- ность слагаемых ⟨слаг⟩, разделённых плюсами, слагаемое | это после- довательность множителей ⟨множ⟩, разделённых звёздочками (знаками умножения), а множитель | это либо буква x, либо выражение в скоб- ках.
15.1.4. Приведите пример другой грамматики, задающей тот же язык.
Ответ. Вот один из вариантов:
⟨
выр⟩ → ⟨выр⟩ + ⟨выр⟩
⟨
выр⟩ → ⟨выр⟩ * ⟨выр⟩
⟨
выр⟩ → x
⟨
выр⟩ → ( ⟨выр⟩ )

Эта грамматика хоть и проще, но в некоторых отношениях хуже,
о чём мы ещё будем говорить.

15.1. Общий алгоритм разбора
273 15.1.5. Дана произвольная КС-грамматика. Постройте алгоритм проверки принадлежности задаваемому ей языку, работающий поли- номиальное время (т. е. число действий не превосходит полинома от длины проверяемого слова; полином может зависеть от грамматики).
Решение. Заметим, что требование полиномиальности исключает возможность решения, основанном на переборе всех возможных вы- водов. Тем не менее полиномиальный алгоритм существует. Посколь- ку практического значения он не имеет (используемые на практике
КС-грамматики обладают дополнительными свойствами, позволяющи- ми строить более эффективные алгоритмы), мы изложим лишь общую схему решения.
(1) Пусть в грамматике есть нетерминалы 𝐾
1
, . . . , 𝐾
𝑛
. Построим но- вую грамматику с нетерминалами 𝐾
′
1
, . . . , 𝐾
′
𝑛
так, чтобы выполнялось такое свойство: из 𝐾
′
𝑖
выводятся (в новой грамматике) те же слова, что из 𝐾
𝑖
в старой, за исключением пустого слова, которое не выводится.
Чтобы выполнить такое преобразование грамматики, надо выяс- нить, из каких нетерминалов исходной грамматики выводится пустое слово, а затем каждое правило заменить на совокупность правил, полу- чающихся, если в правой части опустить какие-либо из нетерминалов,
из которых выводится пустое слово, а у остальных поставить штрихи.
Например, если в исходной грамматике было правило
K → L M N,
причём из L и N выводится пустое слово, а из M нет, то это правило надо заменить на правила
K
′
→
L
′
M
′
N
′
K
′
→
M
′
N
′
K
′
→
L
′
M
′
K
′
→
M
′
(2) Итак, мы свели дело к грамматике, где ни из одного нетерминала не выводится пустое слово. Теперь устраним «циклы» вида
K → L
L → M
M → N
N → K
(в правой части каждого правила один символ, и эти символы обра- зуют цикл произвольной длины): это легко сделать, отождествив все входящие в цикл нетерминалы.

274 15. Контекстно-свободные грамматики
(3) Теперь проверка принадлежности какого-либо слова языку, по- рождённому грамматикой, может выполняться так: для каждого под- слова проверяемого слова и для каждого нетерминала выясняем, поро- ждается ли это подслово этим нетерминалом. При этом подслова прове- ряются в порядке возрастания длин, а нетерминалы | в таком порядке,
чтобы при наличии правила 𝐾 → 𝐿 нетерминал 𝐿 проверялся раньше нетерминала 𝐾. (Это возможно в силу отсутствия циклов.) Поясним этот процесс на примере.
Пусть в грамматике есть правила
K → L
K → M N L
и других правил, содержащих K в левой части, нет. Мы хотим узнать,
выводится ли данное слово 𝐴 из нетерминала K. Это будет так в одном из случаев:
∙
если 𝐴 выводится из L;
∙
если 𝐴 можно разбить на непустые слова 𝐵, 𝐶, 𝐷, для которых
𝐵 выводится из M, 𝐶 выводится из N, а 𝐷 выводится из L.
Вся эта информация уже есть (слова 𝐵, 𝐶, 𝐷 короче 𝐴, а L рассмотрен до K).
Легко видеть, что число действий этого алгоритма полиномиально.
Степень полинома зависит от числа нетерминалов в правых частях пра- вил и может быть понижена, если грамматику преобразовать к форме,
в которой правая часть каждого правила не более 2 нетерминалов (это легко сделать, вводя новые нетерминалы: например, правило K → LMK
можно заменить на K → LN и N → MK, где N | новый нетерминал). 
15.1.6. Рассмотрим грамматику с единственным нетерминалом K,
нетерминалами 0, 1, 2, 3 и правилами
K → 0
K → 1 K
K → 2 K K
K → 3 K K K
Как проверить выводимость слова в этой грамматике, читая слово сле- ва направо? (Число действий при прочтении одной буквы должно быть ограничено.)

15.2. Метод рекурсивного спуска
275
Решение. Хранится целая переменная n, инвариант: слово выводи- мо ⇔ непрочитанная часть представляет собой конкатенацию (соеди- нение) n выводимых слов.

15.1.7. Тот же вопрос для грамматики
K → 0
K → K 1
K → K K 2
K → K K K 3

15.2. Метод рекурсивного спуска
В отличие от алгоритма предыдущего раздела (представляюще- го чисто теоретический интерес), алгоритмы на основе рекурсивного спуска часто используются на практике. Этот метод применим, однако,
далеко не ко всем грамматикам. Мы обсудим необходимые ограничения позднее.
Идея метода рекурсивного спуска такова. Для каждого нетермина- ла K мы строим процедуру ReadK, которая | в применении к любому входному слову 𝑥 | делает две вещи:
∙
находит наибольшее начало 𝑧 слова 𝑥, которое может быть нача- лом выводимого из K слова;
∙
сообщает, является ли найденное слово 𝑧 выводимым из K.
Прежде чем описывать этот метод более подробно, договоримся о том, как процедуры получают сведения о входном слове и как сооб- щают о результатах своей работы. Мы предполагаем, что буквы вход- ного слова поступают к ним по одной, т. е. имеется граница, отделя- ющая «прочитанную» часть от «непрочитанной». Будем считать, что есть функция (без параметров)
Next: Symbol дающая первый непрочитанный символ. Её значениями могут быть тер- минальные символы, а также специальный символ EOI (End Of Input |
конец входа), означающий, что всё слово уже прочитано. Вызов этой функции, разумеется, не сдвигает границы между прочитанной и не- прочитанной частью | для этого есть процедура Move, которая сдви- гает границу на один символ. (Она применима, если Next<>EOI.) Пусть,
наконец, имеется булевская переменная b.

276 15. Контекстно-свободные грамматики
Теперь мы можем сформулировать наши требования к процедуре
ReadK. Они состоят в следующем:
∙
ReadK прочитывает из оставшейся части слова максимальное на- чало 𝐴, являющееся началом некоторого слова, выводимого из K;
∙
значение b становится истинным или ложным в зависимости от того, является ли 𝐴 выводимым из K или лишь невыводимым на- чалом выводимого (из K) слова.
Для удобства введём такую терминологию: выводимое из K слово бу- дем называть K-словом, а любое начало любого выводимого из K слова |
K-началом. Два сформулированных требования вместе будем выражать словами «ReadK корректна для K».
Начнём с примера. Пусть правило
K → L M
является единственным правилом грамматики, содержащим K в левой части, пусть L, M | нетерминалы и ReadL, ReadM | корректные (для них) процедуры.
Рассмотрим такую процедуру:
procedure ReadK;
begin
ReadL;
if b then begin
ReadM;
end;
end;
15.2.1. Приведите пример, когда эта процедура будет некорректной для K.
Ответ. Пусть из L выводится любое слово вида 00..00, а из M выво- дится лишь слово 01. Тогда из K выводится слово 00001, но процедура
ReadK этого не заметит.

Укажем достаточные условия корректности процедуры ReadK. Для этого нам понадобятся некоторые обозначения. Пусть фиксированы
КС-грамматика и некоторый нетерминал 𝑁 этой грамматики. Рассмо- трим 𝑁-слово 𝐴, которое имеет собственное начало 𝐵, также являю-

15.2. Метод рекурсивного спуска
277
щееся 𝑁-словом (если такие есть). Для любой пары таких слов 𝐴 и 𝐵
рассмотрим терминальный символ, идущий в 𝐴 непосредственно за 𝐵.
Множество всех таких терминалов обозначим Посл(𝑁). (Если никакое
𝑁-слово не является собственным началом другого 𝑁-слова, то множе- ство Посл(𝑁) пусто.)
15.2.2. Укажите (а) Посл(E) для примера 1 (с.
270
); (б) Посл(E) и
Посл(T) для примера 2 (с.
270
); (в) Посл(⟨слаг⟩) и Посл(⟨множ⟩) для примера 3 (с.
272
);
Ответ. (а) Посл(E) = {[, (}. (б) Посл(E) = {[, (}; Посл(T) пусто (ни- какое T-слово не является началом другого). (в) Посл(⟨слаг⟩) = {*};
Посл(⟨множ⟩) пусто.

Кроме того, для каждого нетерминала 𝑁 обозначим через Нач(𝑁)
множество всех терминалов, являющихся первыми буквами непустых
𝑁-слов. Это обозначение | вместе с предыдущим | позволит дать достаточное условие корректности процедуры ReadK в описанной выше ситуации.
15.2.3. Докажите, что если Посл(L) не пересекается с Нач(M) и мно- жество всех M-слов непусто, то ReadK корректна.
Решение. Рассмотрим два случая.
(1) Пусть после ReadL значение переменной b ложно. В этом слу- чае ReadL читает со входа максимальное L-начало 𝐴, не являющееся
L-словом. Оно является K-началом (здесь важно, что множество M-слов непусто.). Будет ли оно максимальным K-началом среди начал входа?
Если нет, то 𝐴 является началом слова 𝐵𝐶, где 𝐵 есть L-слово, 𝐶 есть
M-начало и 𝐵𝐶 | более длинное начало входа, чем 𝐴. Если 𝐵 длиннее 𝐴,
то 𝐴 | не максимальное начало входа, являющееся L-началом, что про- тиворечит корректности ReadL. Если 𝐵 = 𝐴, то 𝐴 было бы L-словом,
а это не так. Значит, 𝐵 короче 𝐴, 𝐶 непусто и первый символ слова 𝐶
следует в 𝐴 за последним символом слова 𝐵, т. е. Посл(L) пересекается с Нач(M). Противоречие. Итак, 𝐴 максимально. Из сказанного следу- ет также, что 𝐴 не является K-словом. Корректность процедуры ReadK
в этом случае проверена.
(2) Пусть после ReadL значение переменной b истинно. Тогда прочи- танное процедурой ReadK начало входа имеет вид 𝐴𝐵, где 𝐴 есть L-сло- во, а 𝐵 есть M-начало. Тем самым 𝐴𝐵 есть K-начало. Проверим его мак- симальность. Пусть 𝐶 есть большее K-начало. Тогда либо 𝐶 есть L-на- чало (что невозможно, так как 𝐴 было максимальным L-началом), либо
𝐶 = 𝐴
′
𝐵
′
, где 𝐴
′
| L-слово, 𝐵
′
| M-начало. Если 𝐴
′
короче 𝐴, то 𝐵
′
не- пусто и начинается с символа, принадлежащего и Нач(M), и Посл(L),

278 15. Контекстно-свободные грамматики что невозможно. Если 𝐴
′
длиннее 𝐴, то 𝐴 | не максимальное L-начало.
Итак, 𝐴
′
= 𝐴. Но в этом случае 𝐵
′
есть продолжение 𝐵, что противоре- чит корректности ReadM. Таким образом, 𝐴𝐵 | максимальное K-нача- ло. Остаётся проверить правильность выдаваемого процедурой ReadK
значения переменной b. Если оно истинно, то это очевидно. Если оно ложно, то 𝐵 не есть M-слово, и надо проверить, что 𝐴𝐵 | не K-слово.
В самом деле, если бы выполнялось 𝐴𝐵 = 𝐴
′
𝐵
′
, где 𝐴
′
| L-слово, 𝐵
′
|
M-слово, то 𝐴
′
не может быть длиннее 𝐴 (ReadL читает максимальное слово), 𝐴
′
не может быть равно 𝐴 (тогда 𝐵
′
равно 𝐵 и не является
M-словом) и 𝐴
′
не может быть короче 𝐴 (тогда первый символ 𝐵
′
при- надлежит и Нач(M), и Посл(L)). Задача решена.

Перейдём теперь к другому частному случаю. Пусть в КС-грамма- тике есть правила
K → L
K → M
K → N
и других правил с левой частью K нет.
15.2.4. Считая, что ReadL, ReadM и ReadN корректны (для L, M и N)
и что множества Нач(L), Нач(M) и Нач(N) не пересекаются, напишите процедуру, корректную для K.
Решение. Схема процедуры такова:
procedure ReadK;
begin if (Next принадлежит Нач(L)) then begin
ReadL;
end else if (Next принадлежит Нач(M)) then begin
ReadM;
end else if (Next принадлежит Нач(N)) then begin
ReadN;
end else begin b := true или false в зависимости от того,
выводимо ли пустое слово из K или нет end;
end;
Докажем, что ReadK корректно реализует K. Если Next не принадлежит ни одному из множеств Нач(L), Нач(M), Нач(N), то пустое слово является

15.2. Метод рекурсивного спуска
279
наибольшим началом входа, являющимся K-началом. Если Next принад- лежит одному (и, следовательно, только одному) из этих множеств, то максимальное начало входа, являющееся K-началом, непусто и читается соответствующей процедурой.

15.2.5. Используя сказанное, составьте процедуру распознавания выражений для грамматики (пример 3, с.
272
):
⟨
выр⟩ → ⟨слаг⟩ ⟨оствыр⟩
⟨
оствыр⟩ → + ⟨выр⟩
⟨
оствыр⟩ →
⟨
слаг⟩ → ⟨множ⟩ ⟨остслаг⟩
⟨
остслаг⟩ → * ⟨слаг⟩
⟨
остслаг⟩ →
⟨
множ⟩ → x
⟨
множ⟩ → ( ⟨выр⟩ )
Решение. Эта грамматика не полностью подпадает под рассмотрен- ные частные случаи: в правых частях есть комбинации терминалов и не- терминалов
+ ⟨выр⟩
и группы из трёх символов
( ⟨выр⟩ )
В грамматике есть также несколько правил с одной левой частью и с правыми частями разного рода, например
⟨
оствыр⟩ → + ⟨выр⟩
⟨
оствыр⟩ →
Эти ограничения не являются принципиальными. Так, правило типа
K → L M N можно было бы заменить на два правила K → L Q и Q → M N,
терминальные символы в правой части | на нетерминалы (с един- ственным правилом замены на соответствующие терминалы). Несколь- ко правил с одной левой частью и разнородными правыми также можно

280 15. Контекстно-свободные грамматики свести к уже разобранному случаю: например,
K → L M N
K → P Q
K →
можно заменить на правила
K → K
1
K → K
2
K → K
3
K
1
→
L M N
K
2
→
P Q
K
3
→
Но мы не будем этого делать | а сразу же запишем то, что получится,
если подставить описания процедур для новых терминальных символов в места их использования. Например, для правила
K → L M N
это даёт процедуру procedure ReadK;
begin
ReadL;
if b then begin
ReadM;
end;
if b then begin
ReadN;
end;
end;
Для её корректности надо, чтобы Посл(L) не пересекалось с Нач(MN)
(которое равно Нач(M), если из M не выводится пустое слово, и равно объединению Нач(M) и Нач(N), если выводится), а также чтобы Посл(M)
не пересекалось с Нач(N).
Аналогичным образом правила
K → L M N
K → P Q
K →

15.2. Метод рекурсивного спуска
281
приводят к процедуре procedure ReadK;
begin if (Next принадлежит Нач(LMN)) then begin
ReadL;
if b then begin ReadM; end;
if b then begin ReadN; end;
end else if (Next принадлежит Нач(PQ)) then begin
ReadP;
if b then begin ReadQ; end;
end else begin b := true;
end;
end;
корректность которой требует, чтобы Нач(LMN) не пересекалось с
Нач(PQ).
Читая приведённую далее программу, полезно иметь в виду соот- ветствие между русскими и английскими словами:
ВЫРажение
EXPRession
ОСТаток ВЫРажения
REST of EXPRession
СЛАГаемое
ADDitive term
ОСТаток СЛАГаемого REST of ADDitive term
МНОЖитель
FACTor procedure ReadSymb (c: Symbol);
b := (Next = c);
if b then begin
Move;
end;
end;
procedure ReadExpr;
ReadAdd;
if b then begin ReadRestExpr; end;
end;
procedure ReadRestExpr;
if Next = ’+’ then begin
ReadSymb (’+’);
if b then begin ReadExpr; end;
end else begin

282 15. Контекстно-свободные грамматики b := true;
end;
end;
procedure ReadAdd;
ReadFact;
if b then begin ReadRestAdd; end;
end;
procedure ReadRestAdd;
if Next = ’*’ then begin
ReadSymb (’*’);
if b then begin ReadAdd; end;
end else begin b := true;
end;
end;
procedure ReadFact;
if Next = ’x’ then begin
ReadSymb (’x’);
end else if Next = ’(’ then begin
ReadSymb (’(’);
if b then begin ReadExpr; end;
if b then begin ReadSymb (’)’); end;
end else begin b := false;
end;
end;
Осталось обсудить проблемы, связанные с взаимной рекурсивностью этих процедур (одна использует другую и наоборот). В паскале это допускается, только требуется дать предварительное описание проце- дур («forward»). Как всегда для рекурсивных процедур, помимо доказа- тельства того, что каждая процедура работает правильно в предполо- жении, что используемые в ней вызовы процедур работают правильно,
надо доказать отдельно, что работа завершается. (Это не очевидно:
если в грамматике есть правило K → KK, то из K ничего не выводится,
Посл(K) и Нач(K) пусты, но написанная по нашим канонам процедура procedure ReadK;
begin
ReadK;
if b then begin

15.2. Метод рекурсивного спуска
283
ReadK;
end;
end;
не заканчивает работы.)
В данном случае процедуры ReadRestExpr, ReadRestAdd, ReadFact либо завершаются, либо уменьшают длину непрочитанной части входа.
Поскольку любой цикл вызовов включает одну из них, то зацикливание невозможно.

15.2.6. Пусть в грамматике имеются два правила с нетерминалом K
в левой части, имеющих вид
K → L K
K →
по которым K-слово представляет собой конечную последовательность
L-слов, причём множества Посл(L) и Нач(K) (в данном случае рав- ное Нач(L)) не пересекаются. Используя корректную для L процеду- ру ReadL, напишите корректную для K процедуру ReadK, не используя рекурсии.
Решение. По нашим правилам следовало бы написать procedure ReadK;
begin if (Next принадлежит Нач(L)) then begin
ReadL;
if b then begin ReadK; end;
end else begin b := true;
end;
end;
завершение работы гарантируется тем, что перед рекурсивным вызо- вом длина непрочитанной части уменьшается.
Эта рекурсивная процедура эквивалентна нерекурсивной:
procedure ReadK;
begin b := true;
while b and (Next принадлежит Нач(L)) do begin
ReadL;
end;
end;

284 15. Контекстно-свободные грамматики
Формально можно проверить эту эквивалентность так. Завершаемость в обоих случаях ясна. Достаточно проверить поэтому, что тело рекур- сивной процедуры эквивалентно нерекурсивной в предположении, что её рекурсивный вызов эквивалентен вызову нерекурсивной процедуры.
Подставим:
if (Next принадлежит Нач(L)) then begin
ReadL;
if b then begin b := true;
while b and (Next принадлежит Нач(L)) do begin
ReadL;
end;
end;
end else begin b := true;
end;
Первую команду b:=true можно выкинуть (в этом месте и так b ис- тинно). Вторую команду можно перенести в начало:
b := true;
if (Next принадлежит Нач(L) then begin
ReadL;
if b then begin while b and (Next принадлежит Нач(L)) do begin
ReadL;
end;
end;
end;
Теперь внутренний if можно выкинуть (если b ложно, цикл while всё
равно не выполняется) и добавить в условие внешнего if условие b
(которое всё равно истинно).
b := true;
if b and (Next принадлежит Нач(L)) then begin
ReadL;
while b and (Next принадлежит Нач(L)) do begin
ReadL;
end;
end;
что эквивалентно приведённой выше нерекурсивной процедуре (из ко- торой вынесена первая итерация цикла).


15.2. Метод рекурсивного спуска
285 15.2.7. Докажите корректность приведённой выше нерекурсивной программы непосредственно, без ссылок на рекурсивную.
Решение. Рассмотрим наибольшее начало входа, являющееся K-на- чалом. Оно представляется в виде конкатенации (последовательного приписывания) нескольких непустых L-слов и, возможно, одного непу- стого L-начала, не являющегося L-словом. Инвариант цикла: прочитано несколько из них; b ⇔ (последнее прочитанное является L-словом).
Сохранение инварианта: если осталось последнее слово, это очевид- но; если осталось несколько, то за первым L-словом (из числа оставших- ся) идёт символ из Нач(L), и потому это слово | максимальное начало входа, являющееся L-началом.

На практике при записи грамматики используют сокращения. Если правила для какого-то нетерминала K имеют вид
K → L K
K →
(т. е. K-слова | это последовательности L-слов), то этих правил не пи- шут, а вместо K пишут L в фигурных скобках. Несколько правил с одной левой частью и разными правыми записывают как одно правило, раз- деляя альтернативные правые части вертикальной чертой.
Например, рассмотренная выше грамматика для ⟨выр⟩ может быть записана так:
⟨
выр⟩ → ⟨слаг⟩ { + ⟨слаг⟩ }
⟨
слаг⟩ → ⟨множ⟩ { * ⟨множ⟩ }
⟨
множ⟩ → x | ( ⟨выр⟩ )
15.2.8. Напишите процедуру, корректную для ⟨выр⟩, следуя этой грамматике и используя цикл вместо рекурсии, где можно.
Решение.
procedure ReadSymb (c: Symbol);
b := (Next = c);
if b then begin Move; end;
end;
procedure ReadExpr;
begin
ReadAdd;

286 15. Контекстно-свободные грамматики while b and (Next = ’+’) do begin
Move; ReadAdd;
end;
end;
procedure ReadAdd;
begin
ReadFact;
while b and (Next = ’*’) do begin
Move; ReadFact;
end;
end;
procedure ReadFact;
begin if Next = ’x’ do begin
Move; b := true;
end else if Next = ’(’ then begin
Move; ReadExpr;
if b then begin ReadSymb (’)’); end;
end else begin b := false;
end;
end;

15.2.9. В последней процедуре команду b:=true можно опустить.