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) Сбалансированность в 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) Нам нужно, чтобы при вращении поддерева номер его корня
не менялся. (В противном случае потребовалось бы корректировать
информацию в отце корня, что нежелательно.) Этого можно достичь,
так как номера вершин дерева можно выбирать независимо от их
значений. (На картинках номер указан сбоку от вершины, а значе-
