Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 65080
Модуль Forms 64856
Пример работы с... 63286
ТЕХНОЛОГИИ ДОСТ... 61564
Имитационное мо... 57410
Реклама
Сейчас на сайте
Гостей: 7
На сайте нет зарегистрированных пользователей

Пользователей: 13,081
новичок: Abdukarimov A
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Компьютерный магазин на Turbo Pascal (База данных) + Пояснительная записка
Принадлежит ли точка пересечению двух окружностей на Turbo Pascal + Отче...
Моделирование работы ЭВМ на GPSS + Пояснительная записка

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
Добавление узлов в Delphi
Перед рассмотрением способов в этом разде-
ле обсуждаются некоторые детали добавления узлов к 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;













Опубликовал Kest October 24 2009 16:20:28 · 0 Комментариев · 8205 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
DragMe [Исходник ...
DelphiX
Карта сайта
Apollovcl61
Print Grid
Введение в станда...
DeleteEdit
Приемы программир...
Профессиональное ...
Пользовательская...
Обучение Borland ...
PDF
PHP 5 в подлинник...
С# для профессион...
ScreenSaver [Исхо...
RSS Feeds
PHP/MySQL для нач...
Пример создания W...
начисление процен...
Генетический алго...

Топ загрузок
Приложение Клие... 100466
Delphi 7 Enterp... 86634
Converter AMR<-... 20077
GPSS World Stud... 12647
Borland C++Buil... 11758
Borland Delphi ... 8556
Turbo Pascal fo... 7037
Visual Studio 2... 4998
Калькулятор [Ис... 4760
FreeSMS v1.3.1 3541
Случайные статьи
Unit expected
Лексикографическая...
Описание константы...
Справка панели инф...
скриптов в нетради...
Раннее закрытие пр...
Глава 5
Добавление IPERSIS...
Классы ORM.
Функции GetX и Get...
Создание Meta-тегов
Простейший алгорит...
Списковая форма за...
Когда локализация ...
Базовая структура ...
Каковы правила пои...
Как я обращался в ...
ЛюбойЛюбой2
High Secure — это ...
Ассоциативные конт...
Самая простая вещь...
8.1. Задача и прос...
Терминальные устро...
Произвольный доступ
Простые свойства
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?