Навигация
Главная
Поиск
Форум
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
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65408
ТЕХНОЛОГИИ ДОСТ... 62288
Имитационное мо... 57984
Реклама
Сейчас на сайте
Гостей: 9
На сайте нет зарегистрированных пользователей

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

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

Реклама



Подписывайся на 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 Комментариев · 8267 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Delphi. Разработк...
Экранная лупа
Пятнашки и крести...
Zoom [Исходник на...
Заставка. Изображ...
Фильтры изображений
Модифицированная ...
Распознавание тек...
Counter [Исходник...
Сложный калькулятор
Animated Menus
BDEPack
MP3 Архив v.2.0
XPButtons
SUIPack
Calendar
Tenis [Исходник н...
Защита от спама ...
XPcontrol
Профессиональное ...

Топ загрузок
Приложение Клие... 100471
Delphi 7 Enterp... 87417
Converter AMR<-... 20079
GPSS World Stud... 13047
Borland C++Buil... 11915
Borland Delphi ... 8630
Turbo Pascal fo... 7041
Visual Studio 2... 5000
Калькулятор [Ис... 4849
FreeSMS v1.3.1 3543
Случайные статьи
1.4.4. Параметры к...
Опретор Repeat; Wh...
«Умный» массив
Способ проведения ...
Разделение данных ...
ДЫРЫ В ЧАТАХ
Графический пользо...
1.5. Правила
Draughts на Strawb...
Генератор имен (ге...
Списки с потоками
Формы представлени...
Модемы типа Bell S...
Модули RPR
Наш метод для onTouch
QuickTime
Онлайн казино. Игр...
Шаблоны функций
ВВЕДЕНИЕ В РЕКУРСИЮ
быть применены в д...
Операторы
Система РВМ
В этой главеГруппо...
Сжатие и кодирован...
Что является самым...
Статистика



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


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