Лекция 8

1.  Балансировка деревьев

Дерево называется идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддеревьях различается не более чем на 1.

Если дерево поиска является идеально сбалансированным, то даже в худшем случае за время порядка O(log2n) в нем можно найти вершину с любым значением ключа или выяснить, что такой вершины нет. В идеально сбалансированном дереве при полностью заполненных уровнях на последнем уровне находится больше половины узлов дерева. Например, последовательность значений 4, 6, 2, 1, 5, 3, 7 дает такое идеально сбалансированное дерево:

PIC61

В этом дереве 7 узлов, на последнем уровне находится 4 узла. Если доступ к одному узлу требует 1 единицу времени, то до узла 4 можно добраться за 1 единицу времени, до 2 и 6 - за 2 единицы, до 1, 3 , 5, 7 - за 3. То есть в худшем случае требуется 3 единицы времени, в среднем: (1+2*2+3*4)/7 = 2.4 единицы времени (log 2n=log 8=3).

Приведение уже существующего дерева к идеально сбалансированному - процесс сложный. Проще балансировать дерево в процессе его роста (после включения каждого узла). Однако требование идеальной сбалансированности делает и этот процесс достаточно сложным, способным затрагивать все узлы дерева.

Другое определение сбалансированности дерева была предложена советскими математиками Адельсоном-Вельским и Ландисом в 1962 год. Дерево называется сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1. Деревья, удовлетворяющие этому условию, называются АВЛ-деревьями.

НЕ нашли? Не то? Что вы ищете?

Примеры АВЛ-сбалансированных деревьев:

PIC64

Примеры деревьев, не являющихся АВЛ-сбалансированными:

PIC65

Для каждого узла дерева можно определить показатель сбалансированности как разность между высотой правого и левого поддерева данного узла. Пусть hR - высота правого поддерева, hL - высота левого. Если дерево АВЛ-сбалансировано, то для каждого узла выполняется: |hR - hL| <= 1.

Показатель баланса hR - hL в АВЛ-дереве может принимать следующие значения:

·  -1, если левое поддерево на единицу выше правого;

·  0, если высоты обоих поддеревьев одинаковы;

·  1, если правое поддерево на единицу выше левого.

Если хотя бы для одного узла дерева это не так, то дерево не является АВЛ-сбалансированным. Приведем примеры АВЛ-сбалансированного и АВЛ-несбалансированного дерева (у каждого узла указан показатель сбалансированности):

PIC66

АВЛ-сбалансированное дерево

PIC67

АВЛ-несбалансированное дерево

Включение в АВЛ-дерево

После включения нового узла в АВЛ-дерево оно должно оставаться сбалансированным. Рассмотрим, в каких случаях потребуется балансировка дерева после включения узла. Во всех случаях будем указывать показатель сбалансированности корневого узла.

До включения (дерево АВЛ-сбалансиро-вано)

После включения

В левое поддерево

В правое поддерево

PIC68
hR = hL

hR-hL= 0

PIC69

или

hR < hL

hR-hL= -1

PIC610

критерий сбалансированности не нарушен

PIC611

или

hR > hL

hR-hL= 1

PIC612

критерий сбалансированности не нарушен

PIC613
hR < hL

hR-hL= -1

PIC614

hR < hL

hR-hL= -2

PIC615

критерий сбалансированности нарушен, нужна балансировка

PIC68
hR = hL

hR-hL= 0

критерий сбалансированности

не нарушен

PIC616


hR > hL

hR-hL= 1

PIC68
hR = hL

hR-hL= 0

критерий сбалансированности не нарушен

PIC617

hR > hL

hR-hL= 2

PIC618

критерий сбалансированности нарушен, нужна балансировка

Таким образом, есть 4 варианта нарушения балансировки:

PIC619

Балансировка выполняется с помощью действий, называемых поворотами узлов. Рассмотрим алгоритмы поворотов, используя указатели p, q и r и считая, что p указывает на узел с нарушенной балансировкой.

Одинарный LL-поворот (малый правый). Выполняется, когда идет по пути L-L от узла с нарушенной балансировкой.

Алгоритм:

q=p->left;

q->bal=0;

p->bal=0;

p->left=q->right;

q->right=p;

p=q;

При включении вершины ветви левого поддерева сильно опустились (добавленная высота отмечена серым цветом). Надо поднять левое поддерево на единицу и одновременно опустить на единицу правое. Эта модификация приводит к изменении. корня – корень левого поддерева становится корнем всего дерева. Требуется также изменить и некоторые связи между вершинами, т. к. корни меняются ролями, меняются на обратные и отношения «предок – потомок».

Введем обозначения: h(t) – высота дерева t; t=vuw – дерево, состоящее из левого поддерева v, корня u, правого поддерева w. Имеет место соотношение h(t)=1+max(h(v),h(w)).

Пусть дерево имеет вид t=(T1AT2)BT3, т. е. корнем является B, правым поддеревом T3, левое поддерево имеет корень A, и состоит, в свою очередь, из левого поддерева T1 и правого поддерева T2(см. рисунок). До включения новой вершины в левое поддерево имело место равенство h(v)=h(w)+1. После включения новой вершины в поддерево T1 общее соотношение высот может стать равным h(v)=h(w)+2.

Надо преобразовать дерево t в новую форму:( T1AT2)BT3Þ T1A(T2BT3).

Одинарный RR-поворот (малый левый). Выполняется, когда идет по пути R-R от узла с нарушенной балансировкой.

Симметричная ситуация имеет место, если новая вершина включается в поддерево R дерева t=T1A(T2BT3). В этом случае преобразование балансировки будет обратным: T1A(T2BT3) Þ (T1AT2)BT3 (выполняется, когда «перевес» идет по пути R-R от узла с нарушенной балансировкой).

Алгоритм:

q=p->right;

q->bal=0;

p->bal=0;

p->right=q->left;

q->left=p;

p=q;

Двойной LR-поворот (большой правый). Выполняется, когда идет по пути L-R от узла с нарушенной балансировкой.

Если включить новую вершину в B, то можно выделить корень, левое и правое поддеревья: B=T2BT3. Исходное дерево будет представлено в виде: t=(T1A(T2BT3))CT4. Вершина, включенная в поддерево B и увеличившая высоту дерева t, принадлежит одному из поддеревьев T2 или T3 (неважно, какому именно, оба их можно поднять).

Преобразование (T1A(T2BT3))CT4Þ (T1AT2)B(T3CT4) разделяет поддеревья T2 или T3, привязывая их к различным корням, и уменьшая высоту дерева на единицу.

Алгоритм:

q=p->left; r=q->right;

if (r->bal<0)

{p->bal=1; q->bal=0;}

else

{p->bal=0; q->bal=-1;}

r->bal=0;

p->left=r->right; q->right=r->left;

r->left=q; r->right=p; p=r;

Двойной RL-поворот (большой левый). Выполняется, когда идет по пути R-L от узла с нарушенной балансировкой.

Выполняется преобразование: T1C((T2BT3)AT4) Þ (T1CT2)B(T3AT4).

Алгоритм:

q=p->right; r=q->left;

if (r->bal>0)

{p->bal=-1; q->bal=0;}

else

{p->bal=0; q->bal=1};

r->bal=0;

p->right=r->left; q->left=r->right;

r->left=p; r->right=q; p=q;

При включении узлов повороты выполняются для узла с нарушенной балансировкой, ближайшего к включенному,. То есть, если после включения узла в дереве образуется несколько узлов с нарушенной балансировкой, поворот выполняется для того, который находится ниже (то есть, ближе к включенному). После балансировки этого узла восстанавливается баланс и выше расположенных узлов.

Построение АВЛ-деревьев

Рассмотрим диаграмму роста АВЛ-дерева поиска, получающегося из последовательности значений 4, 5, 7, 2, 1, 3, 6 (будем указывать тип применяемых поворотов и показатель сбалансированности у узлов с нарушенным балансом):

PIC630

Ясно, что включение узла в АВЛ-дерево в среднем требует больше времени, чем включение в обычное дерево, так как может возникать необходимость проведения балансировки. Поэтому АВЛ-деревья целесообразно использовать в тех случаях, когда поиск узлов в дереве происходит гораздо чаще, чем включение и исключение улов.

Процедура включения в АВЛ-дерево.

Добавление новой вершины в АВЛ-дерево происходит следующим образом.

1) Добавление новой вершины в дерево так же как в бинарного дерева поиска (проход по пути поиска до нужного места).

2) Двигаясь назад по пути поиска от новой вершины к корню дерева, будем искать вершину, в которой нарушился баланс (т. е. высоты левого и правого поддеревьев стали отличаться более чем на 1). При этом допускается использование ссылки на родительский объект.

3) Если такая вершина найдена, то изменим структуру дерева для восстановления баланса с помощью процедур поворотов. Для облегчения балансировки при включении узлов показатель балансировки необходимо хранить в каждом узле:

Удаление из АВЛ-дерева

Очевидно, удаление вершины - процесс намного более сложный, чем добавление. Хотя алгоритм операции балансировки остаётся тем же самым, что и при включении вершины. Балансировка по-прежнему выполняется с помощью одного из четырёх уже рассмотренных поворотов вершин.

Удаление из АВЛ-дерева:

1) Удалим вершину так же, как это делалось для бинарного дерева поиска.

2) Двигаясь назад от удалённой вершины к корню дерева, будем восстанавливать баланс в каждой вершине (с помощью поворотов). При этом нарушение баланса возможно в нескольких вершинах, в отличие от операции включения вершины в дерево.

Для балансировки используются две симметричные процедуры балансировки, одна из которых восстанавливает (уменьшает) высоту левого поддерева, а вторая – высоту правого поддерева.

В качестве примера рассмотрим последовательное исключение узлов 4, 8, 6, 5, 2, 1, 7 из следующего дерева:

Построение АВЛ-дерева (код дан на языке Паскаль, но где-то ошибка, на исходных данных 10 20 25 60 50 35 21 6 4 2 5 7 не делает поворот после добавления 4.)

program buildtree;

type

ref = ^node;

node = record key: integer;

bal: -1..1;

left, right: ref;

end;

var

x: integer; root, p: ref;

t1, t2: text;

h: boolean;

procedure turn_right_small(var t, q: ref);

begin

t^.left := q^.right;

q^.right := t;

t^.bal := 0;

q^.bal := 0;

t := q;

end;

procedure turn_right_big(var t, q: ref);

var

r: ref;

begin

r := q^.right;

q^.right := r^.left;

r^.left := q;

t^.left := r^.right;

r^.right := t;

if r^.bal = -1 then t^.bal := +1 else t^.bal := 0;

if r^.bal = +1 then q^.bal := -1 else t^.bal := 0;

r^.bal := 0;

t := r

end;

procedure turn_left_small(var t, q: ref);

begin

t^.right := q^.left;

q^.left := t;

t^.bal := 0;

q^.bal := 0;

t := q;

end;

procedure turn_left_big(var t, q: ref);

var

r: ref;

begin

r := q^.left;

q^.left := r^.right;

r^.right := q;

t^.right := r^.left;

r^.left := t;

if r^.bal = +1 then t^.bal := -1 else t^.bal := 0;

if r^.bal = -1 then q^.bal := +1 else q^.bal := 0;

r^.bal := 0;

t := r;

end;

procedure printtree(t: ref; h: integer);

var

i: integer;

begin

if t <> nil then begin

printtree(t^.right, h + 1);

for i := 1 to h do write(t2, ' ');

writeln(t2, t^.key);

printtree(t^.left, h + 1);

end;

end;

procedure search(x: integer; var p: ref; var h: boolean);

var

p1: ref; {h=false}

begin

if p = nil then begin{слова в дереве нет, включить его}

new(p);

h := true;

p^.key := x;

p^.left := nil;

p^.right := nil;

p^.bal := 0;

end

else

if x < p^.key then begin

search(x, p^.left, h);

if h then {выросла левая ветвь}

case p^.bal of

1:

begin

p^.bal := 0;

h := false

end;

0: p^.bal := -1;

-1:

begin{балансировка}

p1 := p^.left;

if p1^.bal = -1 then {однократный LL-поворот}

turn_right_small(p, p1)

else {двукратный LR-поворот}

turn_right_big(p, p1);

p^.bal := 0;

h := false;

end

end;

end

else

if x > p^.key then

begin

search(x, p^.right, h);

if h then {выросла правая ветвь}

case p^.bal of

-1:

begin

p^.bal := 0;

h := false

end;

0: p^.bal := +1;

1:

begin{балансировка}

p1 := p^.right;

if p1^.bal = +1 then {однократный RR-поворот}

turn_left_small(p, p1)

else {двукратный RL-поворот}

begin

turn_left_big(p, p1);

end;

p^.bal := 0; h := false;

end;

end;

end

else

begin

h := false end;

end;

begin

assign(t1, 'dan1.dat');

assign(t2, 'dan2.dat');

reset(t1);

rewrite(t2);

while not eof(t1) do

begin

read(t1, x);

h:=false;

search(x, root, h);

printtree(root, 1);

writeln(t2, '---------------------');

end;

printtree(root, 1);

writeln(t2, '---------------------');

close(t1);

close(t2);