в степени 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) Сбалансированность в 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, и мы можем воспользоваться
предположением индукции.
------------- ----------------
------------- ----------------
-------------k ----------------k
2а 2б
(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 := 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 для его вершин правильны; в ос-
| | тальном дереве все осталось как было - в частности,
