Глава 12. Множества и деревья.

     Глава 12. Множества и деревья.

     12.1. Представление множеств с помощью деревьев.

     Полное двоичное дерево. 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 - переменные).)

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








          Малое правое вращение









          Большое правое вращение

     (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)  действий для включения, удаления и проверки
принадлежности. (Указание. Он также использует большие  и  малые
вращения.  Подробности см. в книге Рейнгольда, Нивергельта и Део
"Комбинаторные алгоритмы".)