11. Сбалансированные деревья

Поиск по дереву является эффективным только в том случае, если дерево будет идеально сбалансированным, так как среднее число сравнений, необходимых для обнаружения ключа, в идеально сбалансированном дереве равно log₂n. Если дерево вырождается в список, то эта величина примерно равнаn/2. Анализ показывает, что процедура балансировки, восстанавливающая после каждого случайного включения идеально сбалансированное дерево, не всегда является выгодной, так как реализуется довольно сложно.

Возможным выходом из положения является введение менее строгого понятия сбалансированности. Это может привести к более простой процедуре балансировки за счет незначительного увеличения времени поиска. Одно из таких определений сбалансированного дерева было предложено Г.М. Адельсон-Вельским и Е.М. Ландисом. Их критерий сбалансированности сформулирован следующим образом.

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

Деревья, удовлетворяющие такому условию, часто называют АВЛ-деревьями (по имени их открывателей). Мы их будем называть сбалансированными деревьями. В таких деревьях, как доказали их авторы, операция поиска выполняется за время, пропорциональное log₂n.

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

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

Предположим, включение в Lнового узла приведет к увеличению на 1 его высоты; тогда возможны три ситуации:

1) h_L=h_R: после включенияLиRстанут разной высоты, но критерий сбалансированности не будет нарушен;

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

3) h_L>h_R: после включения критерий сбалансированности нарушится и дерево необходимо перестраивать.

Например, в сбалансированное дерево, приведенное ниже, узлы с ключами 9 и 11 можно включить, не нарушая его сбалансированности. Включение узлов 1, 3, 5 или 7 потребует последующей балансировки.

Существуют лишь 2 различные возможности устранения несбалансированности, возникшей из-за включения, требующие индивидуального подхода (оставшиеся могут быть выведены из них на основе симметрии). Эти случаи показаны ниже. Прямоугольниками обозначены поддеревья, причем «добавленная» при включении высота заштрихована.

Первый случай возникает, когда в дерево на числовом примере включаются узлы с ключами 1 или 3. Ситуация, характерная для второго случая, возникает при включении узлов с ключами 5 или 7. Простые преобразования восстанавливают желанную сбалансированность. Заметим, что допускаются лишь вертикальные перемещения, относительное горизонтальное расположение узлов и поддеревьев должно оставаться без изменения. Результат балансировки показан ниже.

Алгоритм включения и балансировки существенно зависит от того, каким образом хранится информация о сбалансированности дерева. Удобно хранить в каждом узле показатель сбалансированности как разность между высотами правого и левого поддеревьев этого узла:

type

TBalance= -1..+1; // тип показателя сбалансированности

tItem = record// тип элемента дерева

Value: tValue; // содержательная часть элемента дерева

Left, Right: pItem; // указатели на левое и правое поддеревья

Bal: TBalance; // показатель сбалансированности - разность между

// высотами правого и левого поддеревьев узла

end;// tItem

Процесс включения узла в сбалансированное дерево состоит из трех последовательно выполняемых частей.

1. Проход по пути поиска, пока не убедимся, что ключа нет.

2. Включение нового узла и определение результирующего показателя сбалансированности.

3. «Отступления» по пути поиска и проверка в каждом узле показателя сбалансированности. Если необходимо – балансировка.

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

Дополнительная информация, которую нужно передавать на каждом шаге, – изменение высоты поддерева в том месте, где произошло включение. Её можно передавать в виде булевской переменной H, означающей «высота дерева увеличилась».

Рассмотрим процесс возвращения к узлу Itemпосле включения в его левое поддерево, причем известно, что высотаItemувеличилась.

В зависимости от высоты поддеревьев перед включением мы должны различать три возможные ситуации:

1) h_L<h_R,Item^.Bal = +1, предыдущая несбалансированность вItemуравновешивается;

2) h_L=h_R, Item^.Bal = 0, левое поддерево стало «перевешивать», но балансировка не нужна;

3) h_L>h_R, Item^.Bal = –1, необходима балансировка;

В третьей ситуации по показателю сбалансированности корня p1 левого поддерева можно определить, с каким из случаев балансировки мы имеем дело. Еслиp1^.Bal= –1 (левое поддерево этого узла также выше правого), то имеем дело со случаем 1, иначе – со случаем 2.

Операция балансировки состоит только из последовательных переприсваиваний ссылок. Фактически ссылки циклически меняются местами, что приводит к однократному или двукратному повороту двух или трех участвующих в процессе узлов. Кроме вращения ссылок нужно должным образом поправить и показатели сбалансированности соответствующих узлов.

Случай 1называется однократнымLL-поворотом (в левом дереве выросло левое поддерево):

Для реализации LL-поворота необходимо выполнить однократный поворот двух узловItemиp1:

Item^.Left:=p1^.Right; p1^.Right:=Item; Item:=p1;

Случай 2называется двойнымLR-поворотом (в левом дереве выросло правое поддерево):

Для реализации LR-поворота необходимо выполнить двукратный поворот трех узловp1,p2иItem:

p1^.Right:=p2^.Left; p2^.Left:=p1;

Item^.Left:=p2^.Right; p2^.Right:=Item;

Item:=p2;

Процедура, выполняющая все необходимые действия по балансировке, если высота левого поддерева узла Itemувеличилась (Н=True), имеет вид:

procedure LeftBalance(var Item: pItem; var H: Boolean);

// Высота левого поддерева узла Item увеличилась, входное значение Н=True

var

p1, p2:pItem;

begin

case Item^.Bal of

+1:begin

// Правое поддерево было выше, увеличение высоты левого

// поддерева не увеличило высоту дерева, балансировка не нужна

H := False; Item^.Bal := 0; end;

0:begin

Item^.Bal := -1; end;

// Поддеревья были одинаковой высоты, увеличение высоты левого

// поддерева увеличило высоту дерева, но балансировка не нужна

-1: begin

// Левое поддерево было выше, увеличение его высоты

// привело к разбалансировке дерева, нужна балансировка:

p1 := Item^.Left;

if p1^.Bal = -1

then begin // однократный LL-поворот

Item^.Left := p1^.Right; p1^.Right := Item; Item^.Bal := 0; Item := p1; end

else begin // двойной LR-поворот

p2 := p1^.Right; p1^.Right := p2^.Left; p2^.Left := p1;

Item^.Left := p2^.Right; p2^.Right := Item;

if p2^.Bal = -1 then Item^.Bal := +1 else Item^.Bal := 0;

if p2^.Bal = +1 then p1^.Bal := -1 else p1^.Bal := 0;

Item:=p2;

end;

// после балансировки показатель сбалансированности равен 0:

Item^.Bal := 0;

// в результате балансировки высота дерева не увеличилась:

H := False;

end; // конец балансировки

end; // case

end;// procedure LeftBalance

Мы рассмотрели ситуации, возникающие при включении в левое поддерево узла. При включении в правое поддерево все ситуации будут зеркальным отображением рассмотренных ситуаций. Так, если при включении в правое поддерево выросло его правое поддерево, то получим однократный RR-поворот, если выросло левое поддерево, то двойнойRL-поворот. При реализации процедурыRightBalance, работающей, если высота правого поддерева узлаItemувеличилась, все левые указатели узлов меняются на правые и наоборот; все показатели сбалансированности узлов также меняются на противоположные (–1 на +1 и наоборот).

Класс tBalanceTree может быть наследником классаtSearchTreeс учетом изменения типаtItemэлемента дерева:

type

tValue = Char; // тип элемента дерева - символьный

tBalance = -1..+1;// тип показателя сбалансированности

pItem = ^tItem; // тип - указатель на элемент дерева

tItem = record// тип - элемент дерева

Value: tValue; // содержательная часть элемента дерева

Left, Right: pItem; // указатели на левое и правое поддеревья

Bal: TBalance; // показатель сбалансированности в узле

end; // tItem

// Класс tSearchTree - дерево поиска

tSearchTree = class(tBinaryTree)

function Addr(Key : tValue): pItem; // поиск элемента с ключом Key

function Search(Key : tValue): pItem; virtual; // поиск с включением

procedure Delete(Key : tValue); // поиск с исключением

procedure Build(var f : Text); // построение дерева поиска

end; // tSearchTree

// Класс tBalanceTree - сбалансированное дерево поиска

tBalanceTree = class(tSearchTree)

function Search(Key : tValue): pItem; override; // поиск с включением

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

procedureDelete(Key : tValue); // поиск с исключением и перебалансировкой

end;// tBalanceTree

Методы AddrиBuildклассtBalanceTree наследует у классаtSearchTree. МетодыSearchиDeleteклассаtBalanceTree перекрывают одноименные методы классаtSearchTree, так как реализуются иначе. МетодSearchу классовtSearchTree,tBalanceTree должен быть виртуальным, так как наследуемая процедураBuildиспользует его при построении дерева (процедураBuildдолжна вызывать методSearchтого класса, для которого она вызывается).

Функция поиска элемента с заданным ключом Key с включениемв сбалансированное дерево имеет вид

functionTBalanceTree.Search(Key: tValue):pItem;

// поиск элемента с ключом Key с включением в сбалансированное дерево

var

Addr: pItem; // вспомогательный указатель

H: Boolean; // True, если высота дерева увеличилась

procedure LeftBalance(var Item:pItem; var H:Boolean);

// Высота левого поддерева узла Item увеличилась, входное значение Н=True

… // текст процедуры см. выше

end; // procedure LeftBalance

procedure RightBalance(var Item:pItem; var H:Boolean);

// Высота правого поддерева узла Item увеличилась

…

end; // procedure RightBalance

procedure IncKey(var Item: pItem; var H:Boolean);// рекурсивная процедура включения

begin

if Item=nil

then begin // элемента с ключом Key нет -> включение

Item := New(pItem); H := True;

Item^.Value := Key; Item^.Bal := 0;

Item^.Left := nil; Item^.Right := nil;

Addr := Item; Inc(fSize);

end

else

if Key < Item^.Value

then begin // поиск слева

IncKey(Item^.Left, H);

if H then LeftBalance(Item,H); // выросла левая ветвь

end

else

if Key > Item^.Value

then begin //поиск справа

IncKey(Item^.Right, H);

if H then RightBalance(Item,H); // выросла правая ветвь

end

else Addr := Item; // элемент найден

end; // procedure IncKey

begin

H := False;

IncKey(fRoot,H);

Search := Addr;

end;// function tBalanceTree.Search

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

Сложность операции балансировки предполагает, что сбалансированные деревья следует использовать только тогда, когда поиск информации происходит значительно чаще, чем её включение.

Рассмотрим работу процедуры поиска с включением на примере дерева (a). Включение 7 приводит к несбалансированному дереву (b), а его балансировка достигаетсяRR-поворотом (c). Последующее включение узлов с ключами 2 и 1 приводит к несбалансированному дереву (d) с корнем 4, которое балансируетсяLL-поворотом (e).

Включение ключа 3 нарушает критерий сбалансированности в узле 5 (f), и балансировка достигается двойнымLR-поворотом (g). Включение узла с ключом 6 (h) приводит к четвертому типу балансировки – двойномуRL-повороту. Результат – дерево (i).