Жанр: Учеба
Программирование в теоремах и задачах
...ножества
с данным значением хеш-функции. Будем хранить эти k списков
с помощью переменныхтак же, как мы это делали для 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 := Вершина[h(t)];
| {осталось искать в списке, начиная с i}
| while (i "" 0) and (Содержание[i] "" t) do begin
| | i := Следующий[i];
| end; {(i=0) or (Содержание [i] = t)}
| belong := Содержание[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;
| {осталось искать в списке, начиная с i; pred -
| предыдущий. если он есть, и 0, если нет}
| while (i "" 0) and (Содержание[i] "" t) do begin
| | pred := i; i := Следующий[i];
| end; {(i=0) or (Содержание [i] = t)}
| if Содержание[i]=t then begin
| | {элемент есть, надо удалить}
| | if pred = 0 then begin
| | | {элемент оказался первым в списке}
| | | Вершина[h(t)] := Следующий[i];
| | end else begin
| | | Следующий[pred] := Следующий[i]
| | end;
| | {осталось вернуть i в список свободных}
| | Следующий[i] := ПервСвоб;
| | ПервСвоб:=i;
| end;
end;
11.2.2. (Для знакомых с теорией вероятностей.) Пусть
хеш-функция с m значениями используется для хранения множества,
в котором в данный момент n элементов. Доказать, что математическое
ожидание числа действий в предыдущей задаче не превосходит
С*(1+n/m), если добавляемый (удаляемый, искомый) элемент t
выбран случайно, причем все значения h(t) имеют равные вероятности
(равные 1/m).
Решение. Если l(i) - длина списка, соответствующего
хеш-значению i, то число операцией не превосходит C*(1+l(h(i)));
усредняя, получаем искомый ответ, так как сумма всех l(i) равна
n.
Эта оценка основана на предположении о равных вероятностях.
Однако в конкретной ситуации всё может быть совсем не так, и
значения хеш-функции могут "скучиваться": для каждой конкретной
хеш-функции есть "неудачные" ситуации, когда число действий оказывается
большим. Приём, называемый "универсальным хешированием",
позволяет обойти эту проблему. Идея состоит в том, что берётся
семейство хеш-функций, причем любая ситуация оказывается
неудачной лишь для небольшой части этого семества.
Пусть H - семейство функций, каждая из которых отображает
множество T в множество из n элементов (например, 0..n-1). Говорят,
что H - универсальное семейство хеш-функций, если для любых
двух различных значений s и t из множества T вероятность события
"h(s)=h(t)" для случайной функции h из семейства H равна 1/n.
(Другими словами, те функции из H, для которых h(s)=h(t), составляют
1/n-ую часть всех функций в H.)
Замечание. Более сильное требование к семейству H могло бы
состоять в том, чтобы для любых двух различных элементов s и t
множества T значения h(s) и h(t) случайной функции h являются
независимыми случайными величинами, равномерно распределенными
на 0..n-1.
11.2.3. Пусть t[1]..t[u] - произвольная последовательность
различных элементов множества T. Рассмотрим количество действий,
происходящих при помещении элементов t[1]..t[u] в множество, хешируемое
с помощью функции h из универсального семейства H. Доказать,
что среднее количество действий (усреднение - по всем h
из H) не превосходит C*u*(1+u/n).
Решение. Обозначим через m[i] количество элементов последовательности,
для которых хеш-функция равна i. (Числа
m[0]..m[n-1] зависят, конечно, от выбора хеш-функции.) Количество
действий, которое мы хотим оценить, с точностью до постоянного
множителя равно сумме квадратов чисел m[0]..m[n-1]. (Если
k чисел попадают в одну хеш-ячейку, то для этого требуется примерно
1+2+...+k действий.) Эту же сумму квадратов можно записать
как число пар "p,q", для которых h[t[p]]=h[t[q]]. Последнее равенство,
если его рассматривать как событие при фиксированных p
и q, имеет вероятность 1/n при p""q, поэтому среднее значение
соответствующего члена суммы равно 1/n, а для всей суммы получаем
оценку порядка u*u/n, а точнее u*u/n + u, если учесть члены с
p=q.
Оценка этой задачи показывает, что в на каждый добавляемый
элемент приходится в среднем C*(1+u/n) операций. В этой оценке
дробь u/n имеет смысл "коэффициента заполнения" хеш-таблицы.
11.2.4. Доказать аналогичное утверждение для произвольной
последовательности операций добавления, поиска и удаления (а не
только для добавления, как в предыдущей задаче).
Указание. Будем представлять себе, что в ходе поиска, добавления
и удаления элемент проталкивается по списку своих коллег
с тем же хеш-значением, пока не найдет своего двойника или
не дойдет до конца списка. Будем называть i-j-столкновением
столкновение t[i] с t[j]. Общее число действий примерно равно
числу всех столкновений плюс число элементов. При t[i]""t[j] вероятность
i-j-столкновения равна 1/n. Осталось проследить за
столкновениями между равными элементами. Фиксируем некоторое
значение x из множества T и посмотрим на связанные с ним операции.
Они идут по циклу: добавление - проверки - удаление - добавление
- проверки - удаление - ... Столкновения между ними
происходят между добавляемым элементом и следующими за ним проверками
(до удаления включительно), поэтому общее их число не
превосходит числа элементов, равных x.
Теперь приведем примеры универсальных семейств. Очевидно,
для любых конечных множеств A и B семейство всех функций, отображающих
A в B, является универсальным. Однако этот пример с
практической точки зрения бесполезен: для запоминания случайной
функции из этого семейства нужен массив, число элементов в котором
равно числу элементов в множестве A. (А если мы можем себе
позволить такой массив, то никакого хеширования нам не требуется!)
Более практичные примеры универсальных семейств могут быть
построены с помощью несложных алгебраических конструкций. Через
Z[p] мы обозначаем множество вычетов по простому модулю p, т.е.
{0,1,...,p-1}; арифметические операции в этом множестве выполняются
по модулю p. Универсальное семейство образуют все линейные
функционалы на Z[p] в степени n со значениями в Z[p]. Более подробно,
пусть a[1],...,a[n] - произвольные элементы Z[p];
рассмотрим отображение
h: "x[1]...x[n]" |-" a[1]x{1]+...+a{n]z[n]
Мы получаем семейство из (p в степени n) отображений, параметризованное
наборами a[1]...a[n].
11.2.5. Доказать, что это семейство является универсальным.
Указание. Пусть x и y - различные точки пространства Z[p] в
степени n. Какова вероятность того, что случайный функционал
принимает на них одинаковые значения? Другими словами, какова
вероятность того, что он равен нулю на их разности x-y? Ответ
дается таким утверждением: пусть u - ненулевой вектор; тогда все
значения случайного функционала на нем равновероятны.
В следующей задаче множество B={0,1} рассматривается как
множество вычетов по модулю 2.
11.2.6. Семейство всех линейных отображений из (B в степени
m) в (B в степени n) является универсальным.
Родственные идеи неожиданно оказываются полезными в следующей
ситуации (рассказал Д.Варсонофьев). Пусть мы хотим написать
программу, которая обнаруживала (большинство) опечаток в тексте,
но не хотим хранить список всех правильных словоформ. Предлагается
поступить так: выбрать некоторое N и набор функций
f[1],...,f[k], отображающих русские слова в 1..N. В массиве из N
битов положим все биты равными нулю, кроме тех, которые являются
значением какой-то функции набора на какой-то правильной словоформе.
Теперь приближённый тест на правильность словоформы таков:
проверить, что значения всех функций набора на этой словоформе
попадают на места, занятые единицами.
Глава 12. Множества и деревья.
12.1. Представление множеств с помощью деревьев.
Полное двоичное дерево. T-деревья.
Нарисуем точку. Из нее проведем две стрелки (влево вверх и
вправо вверх) в две другие точки. Из каждой из этих точек проведем
по две стрелки и так далее. Полученную картинку (в n-ом слое
будет (2 в степени (n - 1)) точек) называют полным двоичным деревом.
Нижнюю точку называют корнем. У каждой вершины есть два
сына (две вершины, в которые идут стрелки) - левый и правый. У
всякой вершины, кроме корня, есть единственный отец.
Пусть выбрано некоторое конечное множество вершин полного
двоичного дерева, содержащее вместе с каждой вершиной и всех ее
предков. Пусть на каждой вершине этого множества написано значение
фиксированного типа T (то есть задано отображение множества
вершин в множество значений типа T). То, что получится, будем
называть T-деревом. Множество всех T-деревьев обозначим Tree(T).
Рекурсивное определение. Всякое непустое T-дерево разбивается
на три части: корень (несущий пометку из T), левое и правое
поддеревья (которые могут быть и пустыми). Это разбиение устанавливает
взаимно однозначное соответствие между множеством непустых
T-деревьев и произведением T * Tree (T) * Tree (T). Обозначив
через empty пустое дерево, можно написать
Tree (T) = {empty} + T * Tree (T) * Tree (T).
Поддеревья. Высота.
Фиксируем некоторое T-дерево. Для каждой его вершины x определено
ее левое поддерево (левый сын вершины x и все его потомки),
правое поддерево (правый сын вершины x и все его потомки)
и поддерево с корнем в x (вершина x и все ее потомки). Левое
и правое поддеревья вершины x могут быть пустыми, а поддерево с
корнем в x всегда непусто (содержит по крайней мере x). Высотой
поддерева будем считать максимальную длину цепи y[1]..y[n] его
вершин, в которой y [i+1] - сын y [i] для всех i. (Высота пустого
дерева равна нулю, высота дерева из одного корня - единице.)
Упорядоченные T-деревья.
Пусть на множестве значений типа T фиксирован порядок. Назовем
T-дерево упорядоченным, если выполнено такое свойство: для
любой вершины x все пометки в ее левом поддереве меньше пометки
в x, а все пометки в ее правом поддереве больше пометки в x.
12.1.1. Доказать, что в упорядоченном дереве все пометки
различны.
Указание. Индукция по высоте дерева.
Представление множеств с помощью деревьев.
Каждое дерево будем считать представлением множества всех
пометок на его вершинах. При этом одно и то же множество может
иметь различные представления.
Благодаря упорядоченности каждый элемент легко может "найти
свое место" в дереве: придя в какую-то вершину и сравнив себя с
тем, кто там находится, элемент решает, идти ему налево или направо.
Начав с корня и двигаясь по этому правилу, он либо обнаружит,
что такой элемент уже есть, либо найдет место, в котором он
должен быть. Всюду далее мы предполагаем, что на значениях типа
T задан порядок, и рассматриваем только упорядоченные деревья.
Хранение деревьев в программе.
Можно было бы сопоставить вершины полного двоичного дерева
с числами 1, 2, 3,... (считая, что левый сын (n) = 2n, правый
сын (n) = 2n + 1) и хранить пометки в массиве val [1...]. Однако
этот способ неэкономен, поскольку тратится место на хранение
пустых вакансий в полном двоичном дереве.
Более экономен такой способ. Введем три массива
val: array [1..n] of T;
left, right: array [1..n] of 0..n;
(n - максимальное возможное число вершин дерева) и переменную
root: 0..n. Каждая вершина хранимого T-дерева будет иметь номер
- число от 1 до n. Разные вершины будут иметь разные номера. Пометка
в вершине с номером x равна val [x]. Корень имеет номер
root. Если вершина с номером i имеет сыновей, то их номера равны
left [i] и right [i]. Отсутствующим сыновьям соответствует число
0. Аналогичным образом значение root = 0 соответствует пустому
дереву.
Для хранения дерева используется лишь часть массива; для
тех i, которые свободны - т.е. не являются номерами вершин -
значения val [i] безразличны. Нам будет удобно, чтобы все свободные
числа были "связаны в список": первое хранится в специальное
переменной free: 0..n, а следующее за i свободное число
хранится в left [i], так что свободны числа
free, left [free], left [left[free]],...
Для последнего свободного числа i значение left [i] = 0. Равенство
free = 0 означает, что свободных чисел больше нет. (Замечание.
Мы использовали для связывания свободных вершин массив
left, но, конечно, с тем же успехом можно было использовать массив
right.)
Вместо значения 0 (обозначающего отсутствие вершины) можно
было бы воспользоваться любым другим числом вне 1..n. Чтобы подчеркнуть
это, будем вместо 0 использовать константу null = 0.
12.1.2. Составить программу, определяющую, содержится ли
элемент t: T в упорядоченном дереве (хранимом так, как только
что описано).
Решение.
if root = null then begin
| ..не принадлежит
end else begin
| x := root;
| {инвариант: остается проверить наличие t в непустом подде-
| реве с корнем x}
| while ((t " val [x]) and (left [x] "" null)) or
| | ((t " val [x]) and (right [x] "" null)) do begin
| | if t " val [x] then begin {left [x] "" null}
| | | x := left [x];
| | end else begin {t " val [x], right [x] "" null}
| | | x := right [x];
| | end;
| end;
| {либо t = val [x], либо t отсутствует в дереве}
| ..ответ = (t = val [x])
end;
12.1.3. Упростить решение, используя следующий трюк. Расширим
область определения массива val, добавив ячейку с номером
null и положим val [null] = t.
Решение.
val [null] := t;
x := root;
while t "" val [x] do begin
| if t " val [x] then begin
| | x := left [x];
| end else begin
| | x := right [x];
| end;
end;
..ответ: (x "" null).
12.1.4. Составить программу добавления элемента t в множество,
представленное упорядоченным деревом (если элемент t уже
есть, ничего делать не надо).
Решение. Определим процедуру get_free (var i: integer), дающую
свободное (не являющееся номером) число i и соответствующим
образом корректирующую список свободных чисел.
procedure get_free (var i: integer);
begin
| {free "" null}
| i := free;
| free := left [free];
end;
С ее использованием программа приобретает вид:
if root = null then begin
| get_free (root);
| left [root] := null; right [root] := null;
| val [root] := t;
end else begin
| x := root;
| {инвариант: осталось добавить t к непустому поддереву с
| корнем в x}
| while ((t " val [x]) and (left [x] "" null)) or
| | ((t " val [x]) and (right [x] "" null)) do begin
| | if t " val [x] then begin
| | | x := left [x];
| | end else begin {t " val [x]}
| | | x := right [x];
| | end;
| end;
| if t "" val [x] then begin {t нет в дереве}
| | get_free (i);
| | left [i] := null; right [i] := null;
| | val [i] := t;
| | if t " val [x] then begin
| | | left [x] := i;
| | end else begin {t " val [x]}
| | | right [x] := i;
| | end;
| end;
end;
12.1.5. Составить программу удаления элемента t из множества,
представленного упорядоченным деревом (если его там нет,
ничего делать не надо).
Решение.
if root = null then begin
| {дерево пусто, ничего делать не надо}
end else begin
| x := root;
| {осталось удалить t из поддерева с корнем в x; поскольку
| это может потребовать изменений в отце x, введем
| переменные father: 1..n и direction: (l, r);
| поддерживаем такой инвариант: если x не корень, то father
| - его отец, а direction равно l или r в зависимости от
| того, левым или правым сыном является x}
| while ((t " val [x]) and (left [x] "" null)) or
| | ((t " val [x]) and (right [x] "" null)) do begin
| | if t " val [x] then begin
| | | father := x; direction := l;
| | | x := left [x];
| | end else begin {t " val [x]}
| | | father := x; direction := r;
| | | x := right [x];
| | end;
| end;
| {t = val [x] или t нет в дереве}
| if t = val [x] then begin
| | ..удаление вершины x с отцом father и направлением
| | direction
| end;
end;
Удаление вершины x происходит по-разному в разных случаях. При
этом используется процедура
procedure make_free (i: integer);
begin
| left [i] := free;
| free := i;
end;
она включает число 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 := r;
| y := left [y];
end;
{val [y] - минимальная из пометок, больших val [x],
y не имеет левого сына}
val [x] := val [y];
..удалить вершину y (как удалять вершину, у которой нет ле-
вого сына, мы уже знаем)
12.1.6. Упростить программу удаления, заметив, что некоторые
случаи (например, первые два из четырех) можно объединить.
12.1.7. Использовать упорядоченные деревья для представления
функций, область определения которых - конечные множества
значений типа T, а значения имеют некоторый тип U. Операции: вычисление
значения на данном аргументе, изменение значения на
данном аргументе, доопределение функции на данном аргументе,
исключение элемента из области определения функции.
Решение. Делаем как раньше, добавив еще один массив
func_val: array [1..n] of U;
если val [x] = t, func_val [x] = u, то значение хранимой функции
на t равно u.
Оценка количества действий.
Для каждой из операций (проверки, добавления и исключения)
количество действий не превосходит C * (высота дерева). Для
"ровно подстриженного" дерева (когда все листья на одной высоте)
высота по порядку величины равна логарифму числа вершин. Однако
для кривобокого дерева все может быть гораздо хуже: в наихудшем
случае все вершины образуют цепь и высота равна числу вершин.
Так случится, если элементы множества добавляются в возрастающем
или убывающем порядке. Можно доказать, однако, что при добавлении
элементов "в случайном порядке" средняя высота дерева будет
не больше C * (логарифм числа вершин). Если этой оценки "в среднем"
мало, необходимы дополнительные действия по поддержанию
"сбалансированности" дерева. Об этом см. в следующем пункте.
12.1.8. Предположим, что необходимо уметь также отыскивать
k-ый элемент множества (в порядке возрастания), причем количество
действий должно быть не более C*(высота дерева). Какую
дополнительную информацию надо хранить в вершинах дерева?
Решение. В каждой вершине будем хранить число всех ее потомков.
Добавление и исключение вершины требует коррекции лишь
на пути от корня к этой вершине. В процессе поиска k-ой вершины
поддерживается такой инвариант: искомая вершина является s-ой
вершиной поддерева с корнем в x (здесь s и x - переменные).)
12.2. Сбалансированные деревья.
Дерево называется сбалансированным (или АВЛ-деревом в честь
изобретателей этого метода Г.М.Адельсона-Вельского и Е.М.Ландиса),
если для любой его вершины высоты левого и правого поддеревьев
этой вершины отличаются не более чем на 1. (В частности,
когда одного из сыновей нет, другой - если он есть - обязан быть
листом.)
12.2.1. Найти минимальное и максимальное возможное количество
вершин в сбалансированном дереве высоты n.
Решение. Максимальное число вершин равно (2 в степени n) -
1. Если m (n) - минимальное число вершин, то, как легко видеть,
m (n + 2) = 1 + m (n) + m (n+1),
откуда
m (n) = fib (n+1) - 1
(fib(n) - n-ое число Фибоначчи, fib(0)=1, fib(1)=1, fib(n+2) =
fib(n) + fib(n+1)).
12.2.2. Доказать, что сбалансированное дерево с n вершинами
имеет высоту не больше C * (log n) для некоторой константы C, не
зависящей от n.
Решение. Индукцией по n легко доказать, что fib [n+1] "= (a
в степени n), где a - больший корень квадратного уравнения a*a =
1 + a, то есть a = (sqrt(5) + 1)/2. Остается воспользоваться
предыдущей задачей.
Вращения.
Мы хотим восстанавливать сбалансированность дерева после
включения и удаления элементов. Для этого необходимы какие-то
преобразования дерева, не меняющие множества пометок на его вершинах
и не нарушающие упорядоченности, но способствующие лучшей
сбалансированности. Опишем несколько таких преобразований.
Пусть вершина a имеет правого сына b. Обозначим через P левое
поддерево вершины a, через Q и R - левое и правое поддеревья
вершины b.
Упорядоченность дерева требует, чтобы P " a " Q " b " R
(точнее следовало бы сказать "любая пометка на P меньше пометки
на a", "пометка на a меньше любой пометки на Q" и т.д., но мы
позволим себе этого не делать). Точно того же требует упорядоченность
дерева с корнем b, его левым сыном a, в котором P и Q -
левое и правое поддеревья a, R - правое поддерево b. Поэтому
первое дерево можно преобразовать во второе, не нарушая упорядоченности.
Такое преобразование назовем малым правым вращением
(правым - поскольку существует симметричное, левое, малым - поскольку
есть и большое, которое мы сейчас опишем).
Пусть b - правый сын a, c - левый сын b, P -левое поддерево
a, Q и R -левое и правое поддеревья c, S - правое поддерево b.
Тогда P " a " Q " c " R " b " S.
Такой же порядок соответствует дереву с корнем c, имеющим левого
сына a и правого сына b, для которого P и Q - поддеревья вершины
a, а R и S - поддеревья вершины b. Соответствующее преобразование
будем называть большим правым вращением. (Аналогично определяется
симметричное ему большое левое вращение.)
12.2.3. Дано дерево, сбалансированное всюду, кроме корня, в
котором разница высот равна 2 (т.е. левое и правое поддеревья
корня сбалансированы и их высоты отличаются на 2). Доказать, что
оно может быть превращено в сбалансированное одним из четырех
описанных преобразований, причем высота его останется прежней
или уменьшится на 1.
Решение. Пусть более низким является, например, левое поддерево,
и его высота равна k. Тогда высота правого поддерева
равна k+2. Обозначим корень через a, а его правого сына (он обязательно
есть) через b. Рассмотрим левое и правое поддеревья
вершины b. Одно из них обязательно имеет высоту k+1, а другое
может иметь высоту k или k+1 (меньше k быть не может, так как
поддеревья сбалансированы). Если высота левого поддерева равна
k+1, а правого - k, до потребуется большое правое вращение; в
остальных случаях помогает малое.
------------------------------------
------------------------------------
------------------------------------
высота уменьшилась на 1
------------------------------------
------------------------------------
------------------------------------
высота не изменилась
k-1 или k (в одном из случаев k)
------------------------------------
------------------------------------
------------------------------------
высота уменьшилась на 1
Три случая балансировки дерева.
12.2.4. В сбалансированное дерево добавили или из него удалили
лист. Доказать, что можно восстановить сбалансированность с
помощью нескольких вращений, причем их число не больше высоты
дерева.
Решение. Будем доказывать более общий факт:
Лемма. Если в сбалансированном дереве X одно из его поддеревьев
Y заменили на сбалансированное дерево Z, причем высота Z
отличается от высоты Y не более чем на 1, то полученное такой
"прививкой" дерево можно превратить в сбалансированное вращениями
(причем количество вращений не превосходит высоты, на которой
делается прививка).
Частным случаем прививки является замена пустого поддерева
на лист или наоборот, так что достаточно доказать эту лемму.
Доказательство леммы. Индукция по высоте, на которой делается
прививка. Если она происходит в корне (заменяется все дерево
целиком), то все очевидно ("привой" сбалансирован по условию).
Пусть заменяется некоторое поддерево, например, левое поддерево
некоторой вершины x. Возможны два случая.
(1) После прививки сбалансированность в вершине x не нарушилась
(хотя, возможно, нарушилась сбалансированность в предках
x: высота поддерева с корнем в x могла измениться). Тогда можно
сослаться на предположение индукции, считая, что мы прививали
целиком поддерево с корнем в x.
(2) Сба
...Закладка в соц.сетях
