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; // поиск с включением

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

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

end; // tBalanceTree

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

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

function TBalanceTree.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.Sear ch

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

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

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

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

Лабораторная работа 3.
Бинарные деревья