Фиксируем некоторое 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
