(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

Добавление узлов в Delphi

Источник: codingrus
Kest

 Перед рассмотрением способов удаления узлов из AVL-деревьев в этом разде-
ле обсуждаются некоторые детали добавления узлов к AVL-дереву с помощью
Delphi.
Кроме обычных полей Lef tChild и RightChild класс TAVLNode содержит
также поле Balance, которое указывает, какое поддерево в узле длиннее. Пере-
менная Balance принимает значение Lef tHeavy, если левое поддерево длиннее,
RightHeavy, если правое поддерево длиннее, и Balanced, если оба поддерева
имеют одинаковую глубину.
 

type
TBalance = (LeftHeavy, Balanced, RightHeavy) ;
TAVLNode = class(TObject)
private
public
Id : Integer;
LeftChild, RightChild : TAVLNode;
Balance : TBalance;
Position : TPoint;
// Код опущен...
end;


 

Процедура AddNode, показанная ниже, рекурсивно обращается к дереву в по-
исках места для нового элемента. Дойдя до нижнего уровня дерева, процедура со-
здает новый узел и добавляет его к дереву.
Затем AddNode использует восходящую рекурсию, чтобы перебалансировать
дерево. Когда заканчивается рекурсивное обращение, процедура перемещается на-
зад по дереву. При каждом возврате она устанавливает параметр grew в значение
True, если поддерево, которое она покидает, стало глубже. Процедура использует
этот параметр, чтобы определить, сбалансировано ли рассматриваемое поддерево.
Если это не так, применяется соответствующее вращение, чтобы перебалансировать
поддерево.
Различные виды вращения в AVL-деревьях
Рис. 7.11. Различные виды вращения в AVL-деревьях
Предположим, процедура в настоящее время исследует узел X. Допустим, что
она только что возвратилась из правого поддерева ниже узла X и параметр grew
установлен в True, указывая на то, что правое поддерево стало глубже. Если подде-
ревья ниже узла X до этого имели одинаковую глубину, то правое поддерево теперь
длиннее левого. Дерево сбалансировано в этой точке, но поддерево с корнем в узле
X также выросло, так как его правое поддерево стало длиннее.
Если левое поддерево ниже узла X было длиннее правого, то сейчас левое и пра-
вое поддеревья имеют одинаковую глубину. Глубина поддерева с корнем в узле X
не изменилась - она также равна глубине левого поддерева плюс единица. В этом
случае процедура AddNode установит переменную grew в значение False, указы-
вая, что дерево сбалансировано.
И наконец, если правое поддерево ниже узла X было до этого длиннее левого,
новый узел разбалансирует дерево в узле X. Процедура AddNode вызывает проце-
дуру RebalanceRightGrew, чтобы перебалансировать дерево. Данная процедура
выполняет левое вращение или вращение вправо-влево, в зависимости от конкрет-
ной ситуации.
Процедура AddNode работает по такому же сценарию, если новый элемент до-
бавляется в левое поддерево. Следующий код показывает выполнение процедур
AddNode и RebalanceRightGrew. Процедура RebalanceLef tGrew аналогич-
на процедуре RebalanceRightGrew.
 
procedure TAVLTree.AddNode(var parent : TAVLNode; new_id : Integer;
var grew : Boolean);
begin
// Если это основание дерева, то создаем новый узел и заставляем
// родительский_узел указывать на новый.
if (parent = nil) then
begin
parent := TAVLNode.Create;
parent.Id := new_id;
parent.Balance := Balanced;
grew := True;
expend;
// Продолжаем двигаться вниз по соответствующему поддереву.
if (new_id<=parent.Id) then
begin
// Вставка дочернего узла в левое поддерево.
AddNode(parent.LeftChiId,new_id,grew);
// Нужна ли перебалансировка?
if (not grew) then exit;
if (parent.Balance = RightHeavy) then
begin
// Правое поддерево было длиннее. Левое поддерево выросло,
// поэтому дерево сбалансировано.
parent.Balance := Balanced;
grew := False;
end else if (parent.Balance = Balanced) then
begin
// Был баланс. Левое поддерево выросло,
// поэтому левое поддерево длиннее. Дерево все еще
// сбалансировано, но оно выросло, поэтому необходимо
// продолжить проверку баланса еще выше.
parent.Balance := LeftHeavy;
end else begin
// Левое поддерево длиннее. Оно выросло, поэтому имеем
// разбалансированное дерево слева. Необходимо выполнить
// соответствующее вращение для перебалансирования.
RebalanceLeftGrew(parent);
grew := False;
end; // Конец проверки баланса родительского узла.
end else begin
// Вставка дочернего узла в правое поддерево.
AddNode(parent.RightChild,new_id,grew);
// Нужна ли перебалансировка?
if (not grew) then exit;
if (parent.Balance = LeftHeavy) then
begin
// Левое поддерево было длиннее. Правое поддерево выросло,
// поэтому дерево сбалансировано.
parent.Balance := Balanced;
grew := False;
end else if (parent.Balance = Balanced) then
begin
// Был баланс. Правое поддерево выросло,
// поэтому оно длиннее. Дерево все еще сбалансировано,
// но оно выросло, поэтому необходимо продолжить проверку
// баланса еще выше.
parent.Balance := RightHeavy;
end else begin
// Правое поддерево длиннее. Оно выросло, поэтому имеем
// разбалансированное дерево справа. Необходимо выполнить
// соответствующий сдвиг для перебалансирования.
RebalanceRightGrew(parent);
grew := false;
end; // Конец проверки баланса родительского узла.
end; // Конец if (левое поддерево) ... else (правое поддерево) ..
end;
// Выполнение левого вращения или вращения вправо-влево
// для перебалансирования дерева в данном узле.
/procedure TAVLTree.RebalanceRightGrew(var parent : TAVLNode);
var
child, grandchild : TAVLNode;
begin
child := parent.RightChild;
if (child.Balance= RightHeavy) then
begin
// Вращение влево.
parent.RightChild := child.LeftChild;
child.LeftChild := parent;
parent.Balance := Balanced;
parent := child;
end else begin
// Вращение вправо-влево.
Grandchild := child.LeftChild;
child.LeftChild := grandchild.RightChild;
grandchild.RightChild := child;
parent.RightChild := grandchild.LeftChild;
grandchild.LeftChild := parent;
if (grandchild.Balance=RightHeavy) then
parent.Balance := LeftHeavy
else ,
parent.Balance := Balanced;
if (grandchild.Balance=LeftHeavy) then
child.Balance := RightHeavy
else
child.Balance := Balanced;
parent := grandchild;
end; // Конец if ... else ...
parent.Balance := Balanced;
end;

Ссылки по теме


 Распечатать »
 Правила публикации »
  Обсудить материал в конференции Embarcadero »
Написать редактору 
 Рекомендовать » Дата публикации: 03.08.2012 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Enterprise Connectors (1 Year term)
Delphi Professional Named User
VideoStudio Pro X10 ML. Электронный ключ
Nero Basic Burning ROM 2018 VL Maintenance VL 5 - 9 License corporate
Microsoft SQL CAL 2017 Sngl OLP 1License NoLevel DvcCAL
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
CASE-технологии
Программирование в AutoCAD
СУБД Oracle "с нуля"
Работа в Windows и новости компании Microsoft
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Ставки на спорт через зеркало БК Пинакл (1)
Актуальное зеркало букмекерской конторы Пинакл https://superbet.guru/pinacle-mirror/ всегда...
 
Ищу программиста для написания программы (57)
Ищу программиста ,владеющего Вижуал Бэйсик и программированием в Экселе, для написания...
 
Разработка программ базы данных (48)
Написание прикладных компьютерных программ (базы данных) на заказ. Разработка корпоративных...
 
Пишу программы на заказ для студентов (241)
Пишу для студентов на с, с++, паскаль в средах ms visual studio, qt, builder, borland c, delphi....
 
Программы Delphi на заказ (240)
Пишу программы в среде Delphi на заказ http://bddelphi.ucoz.ru/
 
 
 



    
rambler's top100 Rambler's Top100