Хранение деревьев в программе

Можно было бы сопоставить вершины полного двоичного дерева с числами $1,2,3,\ldots$ (считая, что левый сын 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.

$\scriptstyle{\blacktriangleright}$ 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;`

$\scriptstyle{\blacktriangleright}$ 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).`

$\scriptstyle{\blacktriangleright}$ 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;`

$\scriptstyle{\blacktriangleright}$ 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;

Удаление вершины использует процедуру

  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 := l;
  | y := left [y];
  end;
  {val [y] - минимальная из пометок, больших val [x],
   y не имеет левого сына}
  val [x] := val [y];
  ..удалить вершину y (как удалять вершину, у которой нет
    левого сына, мы уже знаем)`

$\scriptstyle{\blacktriangleright}$ 12.1.6. Упростить программу удаления, заметив, что некоторые случаи (например, первые два из четырех) можно объединить. $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 12.1.7. Использовать упорядоченные деревья для представления функций, область определения которых -- конечные множества значений типа T, а значения имеют некоторый тип U. Операции: вычисление значения на данном аргументе, изменение значения на данном аргументе, доопределение функции на данном аргументе, исключение элемента из области определения функции.

Решение. Делаем как раньше, добавив еще один массив

func_val: array [1..n] of U;

если val[x] = t, func_val[x] = u, то значение хранимой функции на t равно u. $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 12.1.8. Предположим, что необходимо уметь также отыскивать k-ый элемент множества (в порядке возрастания), причем количество действий должно быть не более $C\cdot(\hbox{\rm высота дерева})$ . Какую дополнительную информацию надо хранить в вершинах дерева?

Решение. В каждой вершине будем хранить число всех ее потомков. Добавление и исключение вершины требует коррекции лишь на пути от корня к этой вершине. В процессе поиска k-ой вершины поддерживается такой инвариант: искомая вершина является s-ой вершиной поддерева с корнем в x (здесь s и x -- переменные). $\scriptstyle\blacktriangleleft$

pvv
1/8/1999