12.3.1. Включение в сбалансированное дерево

Представим себе дерево с корнем r и двумя поддеревьями: левым L, имеющим высоту h_L, и правым R с высотой h_R. При включении нового узла в L возможны три случая:

1. h_L = h_R: L и R становятся неравной высоты, но критерий сбалансированности не нарушается;

2. h_L < h_R: L и R приобретают равную высоту, то есть сбалансированность даже улучшается;

3. h_L > h_R: критерий сбалансированности нарушается, и дерево нужно перестраивать.

В качестве примера рассмотрим дерево на рис. 12.7.

Рис. 12.7. АВЛ-дерево.

Без последующей балансировки в это дерево можно вставить узлы с ключами 8 и 10. При этом сбалансированность дерева улучшается. Однако при вставке узлов с ключами 0, 2, 4 или 6 необходима последующая балансировка дерева.

Теперь рассмотрим некое условное дерево, представленное на рис. 12.8. На рисунке изображены только узел X и два его сына — A и B, остальные части дерева обозначены треугольниками, так как их детали не важны для предстоящего рассмотрения.

Рис.12.8. Условное изображение дерева для анализа разбалансированности

Новый узел может быть вставлен в одно из этих поддеревьев: R, LR, RL или L. Мы рассмотрим два принципиально разных случая, требующих индивидуального подхода. Оставшиеся могут быть получены симметричными преобразованиями этих двух.

Сначала рассмотрим случай, который называется вращением вправо или однократным правым поворотом (R). Такая ситуация возникает, когда к поддереву R на рис. 12.8 добавляется новый узел. В этом случае два правых поддерева узла X изменяться не будут, поэтому их можно сгруппировать в один треугольник, как показано на рис. 12.9(а). На том же рисунке добавляемый узел обозначен темным квадратом. Новый узел был добавлен к поддереву T₁, поэтому перебалансировка требуется только в том случае, когда высота T₁ становится больше высоты T₃ на 2.

На рис. 12.9(б) показан результат перебалансировки. Следует отметить, что допускаются перемещения лишь в вертикальном направлении, в то время как относительное горизонтальное расположение показанных узлов и поддеревьев должно оставаться без изменений, чтобы не "испортить" упорядоченность дерева. Действительно, при этом сохраняется порядок элементов дерева меньше чем. Порядок обхода слева направо этих двух деревьев одинаков: T₁, A, T₂, X, T₃. Такая модификация дерева называется поворотом вправо, так как узлы A и X как бы смещаются на одну позицию вправо.

Рис.12.9. Вращение вправо

А как изменилась высота поддерева? Из рис. 12.9 видно, что после добавления узла и применения вращения вправо высота поддерева не увеличивается. Следует также отметить, что после вращения вправо любая часть дерева, лежащая выше узла X, остается сбалансированной.

Если добавить новый узел к поддереву LR на рис. 12.8, то потребуется перебалансировка, которая называется вращением влево‑вправо или двукратным поворотом налево и направо (LR). На рис. 12.10(а) показано дерево, в котором новый узел вставляется в левое поддерево узла C — в T₂

Рис. 12.10. Вращение влево-вправо

Новый узел мог бы быть вставлен и в правое поддерево узла C — в T₃. В любом из этих случаев поддеревья с корнями A и C являются сбалансированными, а поддерево с корнем X — нет. Это дерево необходимо перебалансировать так, как показано на рис. 12.10(б). Это вращение называется влево‑вправо, потому что узлы A и C сдвигаются на одну позицию влево, а узлы C и X — на одну позицию вправо. Упорядоченность дерева не меняется, и для двух деревьев на рис. 12.10 обход слева направо дает один и тот же результат: T₁, A, T₂, C, T₃, X, T₄. Высота перебалансированного поддерева не изменилась.

Добавление узла к поддереву L на рис. 12.8 является зеркальным отражением вращения вправо и называется вращением влево (однократный L‑поворот).

Добавление узла к поддереву RL на рис. 12.8 является зеркальным отражением вращения влево‑вправо и называется вращением вправо‑влево (двукратный RL‑поворот).

Для реализации алгоритма включения и информацию о сбалансированности дерева. Поэтому каждый узел должен содержать показатель сбалансированности, который указывает, какое поддерево выше. Эта переменная принимает значение LongLeft, если левое поддерево выше; LongRight — если правое поддерево выше, и Long0 — если поддеревья имеют одинаковую высоту.

Процесс включения узла состоит из трех этапов:

1. идти по дереву, пока не найдется место для вставки;

2. включить новый узел и определить новый показатель сбалансированности;

3. пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла. При необходимости провести балансировку.

Этот алгоритм можно реализовать с помощью расширения процедуры вставки в упорядоченное дерево (Insert), которая представлена в листинге 12.2. Так как процедура рекурсивная, ее можно дополнить восходящей рекурсией: операцией, выполняемой "по дороге назад вдоль пути поиска". На каждом шаге должна передаваться информация о том, увеличилась ли высота дерева, в которое произведено включение. Поэтому к списку параметров процедуры добавляется новый булевский параметр increase, означающий, что высота поддерева увеличилась. Очевидно, что increase должна быть параметром‑переменной, поскольку используется для передачи результата.

Теперь предположим, что алгоритм возвращается к узлу A с левой ветви, как на рис. 12.9, с сообщением, что ее высота увеличилась. Необходимо различать три возможные ситуации в зависимости от высоты поддеревьев перед включением:

1. левое поддерево было короче правого, то есть показатель сбалансированности был равен LongRight; после вставки сбалансированность уравновешивается;

2. левое и правое поддеревья были одинаковой высоты (Long0); после вставки левое дерево становится выше правого, но сбалансированность в АВЛ‑смысле остается;

3. левое дерево было выше правого (LongLeft); вставка узла приводит к разбалансированности дерева, и необходима балансировка.

В последнем  — третьем — случае показатель сбалансированности узла A определяет, в левое или в правое поддерево узла была произведена вставка. Если воспользоваться рис. 12.8, то увеличилась высота поддерева R или поддерева LR соответственно.

Необходимые операции балансировки заключаются в обмене значениями ссылок. Фактически ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному "повороту" двух или трех узлов. Кроме "вращения" ссылок необходимо изменить соответствующие показатели сбалансированности узлов. В листинге 12.9 приведена процедура вставки и балансировки.

Листинг 12.9. Вставка в АВЛ-дерево и балансировка

type

Balance = (LongLeft, LongRight, Long0);

// левая ветвь длиннее, правая длиннее, длины ветвей равны

TKey=integer;

TNode=^PNode;

PNode=record

key : TKey;

xN,yN: integer; // координаты узла на канве

left, right: TNode;

bal: Balance;

end;

procedure InsertBalance(var t: TNode; i: TKey; var increase: Boolean);

var p1,p2: TNode;

begin

if t = Nil then begin // включение в дерево

new(t); increase:=true;

with t^ do begin

Left:=Nil; Right:=Nil;

key:=i;

bal:=Long0;

end;

end

else

if i<=t^.key then begin

InsertBalance(t^.Left, i, increase);

if increase then // выросла левая ветвь

case t^.bal of

LongRight: // правое поддерево было выше,

// выросла левая ветвь,

// поэтому балансировка не нужна

begin t^.bal:=Long0; increase:=false; end;

Long0: // был баланс, но выросла левая ветвь,

// требуется проверка сбалансированности на верхних уровнях

t^.bal:=LongLeft;

LongLeft: // левое поддерево было выше,

// да еще выросла левая ветвь, поэтому необходима балансировка

begin

p1:=t^.Left;

if p1^.bal=LongLeft then begin // однократный L-поворот

t^.left:=p1^.right; p1^.right:=t;

t^.bal:=Long0; t:=p1;

end

else begin // двукратный LR-поворот

p2:=p1^.right; p1^.right:=p2^.left; p2^.left:=p1;

t^.left:=p2^.right; p2^.right:=t;

if p2^.bal=LongLeft then t^.bal:=LongRight

else t^.bal:=Long0;

if p2^.bal=LongRight then p1^.bal:=LongLeft

else p1^.bal:=Long0;

t:=p2;

end;

t^.bal:=Long0; increase:=false;

end

end // case

end

else begin // if i > t^.key

InsertBalance(t^.right, i, increase);

if increase then // выросла правая ветвь

case t^.bal of

LongLeft: begin t^.bal:=Long0; increase:=false; end;

Long0 : t^.bal:=LongRight;

LongRight:

begin p1:=t^.right; // балансировка

if p1^.bal=LongRight then begin // однократный R-поворот

t^.right:=p1^.left; p1^.left:=t;

t^.bal:=Long0; t:=p1;

end

else begin // двукратный RL-поворот

p2:=p1^.left;

p1^.left:=p2^.right; p2^.right:=p1;

t^.right:=p2^.left; p2^.left:=t;

if p2^.bal=LongRight then t^.bal:=LongLeft

else t^.bal:=Long0;

if p2^.bal=LongLeft then p1^.bal:=LongRight

else p1^.bal:=Long0;

t:=p2

end;

t^.bal:=Long0; increase:=false

end

end; // case

end;

end;

Принцип работы алгоритма показан на рис. 12.11.

Рис. 12.11. Последовательность включений в АВЛ-дерево

Рассмотрим бинарное дерево (а), которое состоит только из двух узлов. Включение ключа 7 вначале дает линейный список — несбалансированное дерево. Для его балансировки нужен однократный правый (R) поворот, который приводит к идеально сбалансированному дереву (б). Последующее включение узлов 2 (в) и 1 дает несбалансированное дерево с корнем 4. Это поддерево балансируется однократным левым (L) поворотом и приводит к (д). Затем включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5. Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (LR); результатом является дерево (е). Следующее включение ключа 6 приводит к потере сбалансированности узла 5. Для восстановления сбалансированности необходимо применить четвертый вид балансировки: двукратный поворот направо и налево (RL). Результат показан на рис. 12.11е.

Эмпирические оценки показывают, что на практике АВЛ‑сбалансированные деревья ведут себя так же, как и идеально сбалансированные деревья, хотя с ними намного легче работать. Из тех же оценок делается предположение, что на каждые два включения в среднем требуется одна балансировка. При этом однократный и двукратный повороты равновероятны. В этом смысле пример на рис. 12.11 не является показательным: он был тщательно подобран с целью проиллюстрировать все возможные повороты при минимальном числе включений.