Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

ВКЛЮЧЕНИЕ В СБАЛАНСИРОВАННОЕ ДЕРЕВО

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

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

)hL = hR. после включения Lw R станут разной высоты, но критерий сбалансированности не будет нарушен;

  • 2) И[ < кк: после включения I и Я станут равной высоты, т.е. сбалансированность улучшится;
  • 3) Иь > Ия: после включения критерий сбалансированности нарушится и дерево необходимо перестраивать.

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

Сбалансированное дерево

Рис. 3.8. Сбалансированное дерево

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

Ситуации, возникающие при включении в сбалансированное дерево

Рис. 3.9. Ситуации, возникающие при включении в сбалансированное дерево

Первый случай возникает, когда в дерево на рис. 3.8 включаются узлы с ключами 1 или 3.

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

Заметим, что допускаются лишь вертикальные перемещения, относительное горизонтальное расположение узлов и поддеревьев должно оставаться без изменения. Результат балансировки показан на рис. 3.10.

Устранение несбалансированности при включении

Рис. 3.10. Устранение несбалансированности при включении

в сбалансированное дерево

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

type

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

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

Left, Right: pltem; //указатели на левое и правое поддеревья Bal: TBalance; //показатель сбалансированности

end; //tltem

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

  • 1. Проход по пути поиска, пока не убедимся, что ключа нет.
  • 2. Включение нового узла и определение результирующего показателя сбалансированности.
  • 3. «Отступления» по пути поиска и проверка в каждом узле показателя сбалансированности. Если необходимо — балансировка.

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

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

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

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

  • 1) hL < hR, ItemA.Bal = +1, предыдущая несбалансированность в Item уравновешивается;
  • 2) /?у = hR, ItemA.Bal = 0, левое поддерево стало «перевешивать», но балансировка не нужна;
  • 3) hL > hR, ВетЛ.Ва1 = — 1, необходима балансировка.

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

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

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

Однократный LL-поворот

Рис. 3.11. Однократный LL-поворот

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

ltemA.Left:=p1Л.Right;

p1A.Right:=ltem;

Item:=p1;

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

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

p1 A.Right:=p2A.Left; p2A.Left:=p1; ltemA.Left:=p2A.Right; p2A.Right:=ltem; Item:=p2;

Двойной LR-поворот

Рис. 3.12. Двойной LR-поворот

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

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

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

var

p1, p2:pltem;

begin

case ltemA.Bal of

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

// балансировка не нужна Н := False; ltemA.Bal := 0;

end;

0: begin // Поддеревья были одинаковой высоты,

//увеличение высоты левого поддерева увеличило // высоту дерева, но балансировка не нужна ltemA.Bal := -1;

end;

-1: begin //Левое поддерево было выше, увеличение его высоты // привело к разбалансировке, нужна балансировка: р1 := ltemA.Left; if p1A.Bal = -1

then begin //однократный LL-noeopom ltemA.Left := р1л.Right; р1л.Right := Item; ltemA.Bal := 0;

Item := p1; end

else begin // двукратный LR-поворот p2 := р1л.Right;

р1л Right := p2A.Left; p2A.Left := p1; ltemA.Left := p2A.Right; p2A.Right := Item;

if p2A.Bal = -1 then ltemA.Bal := +1 else ltemA.Bal := 0; if p2A.Bal = +1 then p1A.Bal := -1 else p1A.Bal := 0; Item := p2; end;

// показатель сбалансированности стал равен 0: ltemA.Bal := 0;

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

Н := False;

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

end; //procedure LeftBalance

Мы рассмотрели ситуации, возникающие при включении в левое поддерево узла. При включении в правое поддерево все ситуации будут зеркальным отображением рассмотренных ситуаций. Так, если при включении в правое поддерево выросло его правое поддерево, то получим однократный RR-поворот, если выросло левое поддерево, то двойной RL-поворот.

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

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

type

tValue = Char; //тип элемента дерева - символьный tBalance = -1 ..+1; //тип показателя сбалансированности pltem = Atltem; //тип - указатель на элемент дерева

tltem = record Value: tValue;

Left, Right: pltem; Bal: TBalance; end; //tltem

// тип - элемент дерева // содержательная часть элемента дерева //указатели на левое и правое поддеревья //показатель сбалансированности в узле

//Класс tSearchTree - дерево поиска tSearchTree = class(tBinaryTree)

function Addr(Key : tValue): pltem;//адрес элемента с ключом Key function Search(Key : tValue): pltem; virtual;//поиск с включением procedure Delete(Key : tValue); //поиск с исключением

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

end; //tSearchTree //Класс tBalanceTree - сбалансированное дерево поиска tBalanceTree = class(tSearchTree)

// Поиск с включением и перебалансировкой function Search(Key : tValue): pltem; override;

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

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

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

function TBalanceTree.Search(Key: tValue):pltem;

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

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

var

Addr: pltem; // вспомогательный указатель Н: Boolean; // True, если высота дерева увеличилась procedure LeftBalance(var ltem:pltem; var H:Boolean);

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

// текст процедуры см. выше end; //procedure LeftBalance

procedure RightBalance(var ltem:pltem; var H:Boolean);

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

end; //procedure RightBalance

procedure lncKey(var Item: pltem; var H:Boolean);

// Рекурсивная процедура включения

begin if ltem=nil

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

Item := New(pltem);

H := True;

ltemA.Value := Key; ltemA.Bal := 0; ltemA.Left := nil; ltemA.Right := nil;

Addr := Item; Inc(fSize);

end

else

if Key < ltemA.Value then begin // поиск слева

lncKey(ltemA.l_eft, H);

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

end

else

if Key > ltemA.Value

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

lncKey(ltemA.Right, H);

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

end

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

end; //procedure IncKey

begin

H := False;

lncKey(fRoot,H);

Search := Addr;

end; //function tBalanceTree.Search

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

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

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

Включение 7, 2 и 1 в сбалансированное дерево (а)

Рис. 3.13. Включение 7, 2 и 1 в сбалансированное дерево (а)

Включение ключа 3 (рис. 3.14) нарушает критерий сбалансированности в узле 5 (/), и балансировка достигается двойным ЬВ-пово-ротом ^). Включение узла с ключом 6 (И) приводит к четвертому типу балансировки — двойному ВЬ-повороту. Результат — дерево (/).

Включение 3 и 6 в сбалансированное дерево (е) на рис. 3.13

Рис. 3.14. Включение 3 и 6 в сбалансированное дерево (е) на рис. 3.13

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы