Полное двоичное дерево. 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 - переменные).)
Дерево называется сбалансированным (или АВЛ-деревом в честь
изобретателей этого метода Г.М.Адельсона-Вельского и Е.М.Ланди-
са), если для любой его вершины высоты левого и правого подде-
ревьев этой вершины отличаются не более чем на 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, до потребуется большое правое вращение; в
остальных случаях помогает малое.
12.2.4. В сбалансированное дерево добавили или из него уда-
лили лист. Доказать, что можно восстановить сбалансированность с
помощью нескольких вращений, причем их число не больше высоты
дерева.
Решение. Будем доказывать более общий факт:
Лемма. Если в сбалансированном дереве X одно из его подде-
ревьев Y заменили на сбалансированное дерево Z, причем высота Z
отличается от высоты Y не более чем на 1, то полученное такой
"прививкой" дерево можно превратить в сбалансированное вращени-
ями (причем количество вращений не превосходит высоты, на кото-
рой делается прививка).
Частным случаем прививки является замена пустого поддерева
на лист или наоборот, так что достаточно доказать эту лемму.
Доказательство леммы. Индукция по высоте, на которой дела-
ется прививка. Если она происходит в корне (заменяется все дере-
во целиком), то все очевидно ("привой" сбалансирован по усло-
вию). Пусть заменяется некоторое поддерево, например, левое под-
дерево некоторой вершины x. Возможны два случая.
(1) После прививки сбалансированность в вершине x не нару-
шилась (хотя, возможно, нарушилась сбалансированность в предках
x: высота поддерева с корнем в x могла измениться). Тогда можно
сослаться на предположение индукции, считая, что мы прививали
целиком поддерево с корнем в x.
(2) Сбалансированность в x нарушилась. При этом разница вы-
сот равна 2 (больше она быть не может, так как высота Z отлича-
ется от высоты Y не более чем на 1). Разберем два варианта.
(2а) Выше правое (не заменявшееся) поддерево вершины x.
Пусть высота левого (т.е. Z) равна k, правого - k+2. Высота ста-
рого левого поддерева вершины x (т.е. Y) была равна k+1. Подде-
рево с корнем x имело в исходном дереве высоту k+3, и эта высота
не изменилась после прививки.
По предыдущей задаче вращение преобразует поддерево с кор-
нем в x в сбалансированное поддерево высоты k+2 или k+3. То есть
высота поддерева с корнем x - в сравнении с его прежней высотой
- не изменилась или уменьшилась на 1, и мы можем воспользоваться
предположением индукции.
(2б) Выше левое поддерево вершины x. Пусть высота левого
(т.е. Z) равна k+2, правого - k. Высота старого левого поддерева
(т.е. Y) была равна k+1. Поддерево с корнем x в исходном дереве
X имело высоту k+2, после прививки она стала равна k+3. После
подходящего вращения (см. предыдущую задачу) поддерево с корнем
в x станет сбалансированным, его высота будет равна k+2 или k+3,
так что изменение высоты по сравнению с высотой поддерева с кор-
нем x в дереве X не превосходит 1 и можно сослаться на предполо-
жение индукции.
12.2.5. Составить программы добавления и удаления элемен-
тов, сохраняющие сбалансированность. Число действий не должно
превосходить C*(высота дерева). Разрешается хранить в вершинах
дерева дополнительную информацию, необходимую при балансировке.
Решение. Будем хранить для каждой вершины разницу между
высотой ее правого и левого поддеревьев:
diff [i] = (высота правого поддерева вершины с номером i) -
(высота левого поддерева вершины с номером i).
Нам потребуются четыре процедуры, соответствующие большим и ма-
лым правым и левым вращениями. Но вначале два замечания.
(1) Нам нужно, чтобы при вращении поддерева номер его корня
не менялся. (В противном случае потребовалось бы корректировать
информацию в отце корня, что нежелательно.) Этого можно достичь,
так как номера вершин дерева можно выбирать независимо от их
значений. (На картинках номер указан сбоку от вершины, а значе-
ние - внутри.)
(2) После преобразований мы должны также изменить соот-
ветственно значения в массиве diff. Для этого достаточно знать
высоты деревьев P, Q, ... с точностью до константы, поэтому мож-
но предполагать, что одна из высот равна нулю.
Вот процедуры вращений:
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 заполнен правильно;
надо: поддерево с корнем a сбалансировано и массив diff со-
ответственно изменен, d - изменение его высоты (равно 0
или -1); в остальной части все осталось как было}
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;
| 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, l>
| | | x := left [x];
| | end else begin {t > val [x]}
| | | ..добавить в стек пару <x, r>
| | | 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
| | | ..добавить в стек пару <x, l>
| | | left [x] := i;
| | end else begin {t > val [x]}
| | | ..добавить в стек пару <x, r>
| | | right [x] := i;
| | end;
| | d := 1;
| | {инвариант: стек содержит путь к изменившемуся поддереву,
| | высота которого увеличилась по сравнению с высотой в
| | исходном дереве на d (=0 или 1); это поддерево сбалан-
| | сировано; значения diff для его вершин правильны; в ос-
| | тальном дереве все осталось как было - в частности,
| | значения diff}
| | while (d <> 0) and ..стек непуст do begin {d = 1}
| | | ..взять из стека пару в <v, direct>
| | | 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}
| | | | 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}
| ..взять из стека пару в <v, direct>
| 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;
| {c = изменение высоты поддерева с корнем в v по срав-
| нению с исходным деревом; массив diff содержит
| правильные значения для этого поддерева;
| возможно нарушение сбалансированности в v}
| balance (v, d1);
| d := c + d1;
end;
Легко проверить, что значение d может быть равно только 0 или -1
(но не -2): если c = -1, то diff [v] = 0 и балансировка не про-
изводится.
Отметим также, что наличие стека делает излишними перемен-
ные father и direction (их роль теперь играет вершина стека).
12.2.6. Доказать, что при добавлении элемента
(а) второй из трех случаев балансировки (см. рисунок выше)
невозможен;
(б) полная балансировка требует не более одного вращения
(после чего все дерево становится сбалансированным),
в то время как при удалении элемента может понадобиться
много вращений.
Замечание. Мы старались записать программы добавления и
удаления так, чтобы они были как можно более похожими друг на
друга. Используя специфику каждой из них, можно многое упрос-
тить.
Существуют и другие способы представления множеств, гаран-
тирующие число действий порядка log n на каждую операцию. Опишем
один из них (называемый Б-деревьями).
До сих пор каждая вершина содержала один элемент хранимого
множества. Этот элемент служил границей между левым и правым
поддеревом. Будем теперь хранить в вершине k >= 1 элементов мно-
жества (число k может меняться от вершины к вершине, а также при
добавлении и удалении новых элементов, см. далее). Эти k элемен-
тов служат разделителями для k+1 поддерева. Пусть фиксировано
некоторое число n >= 1. Будем рассматривать деревья, обладающие
такими свойствами:
(1) Каждая вершина содержит от n до 2n элементов (за исклю-
чением корня, который может содержать любое число элементов от 0
до 2n).
(2) Вершина с k элементами либо имеет k+1 сына, либо не
имеет сыновей вообще (такие вершины называются листьями).
(3) Все листья находятся на одной и той же высоте.
Добавление элемента происходит так. Если лист, в который он
попадает, неполон (т.е. содержит менее 2n элементов), то нет
проблем. Если он полон, то 2n+1 элемент (все элементы листа и
новый элемент) разбиваем на два листа по n элементов и разделя-
ющий их серединный элемент. Этот серединный элемент надо доба-
вить в вершину предыдущего уровня. Это возможно, если в ней ме-
нее 2n элементов. Если и она полна, то ее разбивают на две, вы-
деляют серединный элемент и т.д. Если в конце концов мы захотим
добавить элемент в корень, а он окажется полным, то корень рас-
щепляется на две вершины, а высота дерева увеличивается на 1.
Удаление элемента. Удаление элемента, находящемся не в лис-
те, сводится к удалению непосредственно следующего за ним, кото-
рый находится в листе. Поэтому достаточно научиться удалять эле-
мент из листа. Если лист при этом становится неполным, то его
можно пополнить за счет соседнего листа - если только и он не
имеет минимально возможный размер n. Если же оба листа имеют
размер n, то на них вместе 2n элементов, вместе с разделителем -
2n+1. После удаления одного элемента остается 2n элементов - как
раз на один лист. Если при этом вершина предыдущего уровня ста-
новится меньше нормы, процесс повторяется и т.д.
12.2.7. Реализовать описанную схему хранения множеств, убе-
дившись, что она также позволяет обойтись C*log(n) действий для
операций включения, исключения и проверки принадлежности.
12.2.8. Можно определять сбалансированность дерева иначе:
требовать, чтобы для каждой вершины ее левое и правое поддеревья
имели не слишком сильно отличающиеся количества вершин. (Преиму-
щество такого определения состоит в том, что при вращениях изме-
няется сбалансированность только в одной вершине.) Реализовать
на основе этой идеи способ хранения множеств, гарантирующий
оценку в C*log(n) действий для включения, удаления и проверки
принадлежности. (Указание. Он также использует большие и малые
вращения. Подробности см. в книге Рейнгольда, Нивергельта и Део
"Комбинаторные алгоритмы".)