Навигация
Главная
Поиск
Форум
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
21 ошибка прогр... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Имитационное мо... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Реклама
Сейчас на сайте
Гостей: 63
На сайте нет зарегистрированных пользователей

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

Метод конечных разностей для интерполяции/экстраполяции на Delphi
Моделирование ЭВМ на GPSS (три класса заданий) + Пояснительная записка
Диплом RSA, ЭЦП, сертификаты, шифрование на C#

Удаление узлов в Delphi
Процедура RemoveFromNode/ удаляет элемент из дерева. Она рекурсивно об-
ращается к дереву и когда находит искомый узел, удаляет его. Если у него нет до-
черних узлов, то процедура заканчивается. Если имеется один дочерний узел, то
удаляемый узел заменяется его потомком.
Если узел имеет двух потомков, то процедура RemoveFromNode вызывает про-
цедуру ReplaceRightmost, чтобы заменить удаляемый узел крайним правым уз-
лом в его левой ветви. Выполнение процедуры ReplaceRightmost описано ранее, где
.
Основное отличие возникает при возврате из процедуры и рекурсивном
проходе вверх по дереву. При этом процедура ReplaceRightmost использует
восходящую рекурсию, чтобы проверить баланс в каждом узле дерева.
Когда вызов процедуры завершается, вызывающая ReplaceRightmost под-
программа использует процедуру RebalanceRightShrunk для проверки балан-
са во всех точках дерева. Так как ReplaceRightmost исследует правые ветви де-
рева, она всегда использует процедуру RebalanceRightShrunk.
Процедура RemoveFromNode первый раз вызывает ReplaceRightmost, зас-
тавляя ее двигаться влево вниз от удаляемого узла. Когда первый вызов процеду-
ры ReplaceRightmost завершается, RemoveFromNode вызывает процедуру
RebalanceLef tShrunk, чтобы проверить баланс во всех точках дерева.
После этого рекурсивные обращения к RemoveFromNode завершаются и про-
цедура выполняется обычным способом снизу вверх. Как и ReplaceRightmost,
RemoveFromNode использует восходящую рекурсию для проверки баланса дерева.
После каждого вызова этой процедуры следует вызов процедуры Rebalance-
RightShrunk или RebalanceLefShrunk в зависимости от того, по какому пути
происходит спуск по дереву.
Процедура RebalanceLef tShrunk аналогична RebalanceRightShrunk,
поэтому она не приведена в следующем коде.
// Удаление значения ниже выделенного узла.
procedure TAVLTree.RemoveFromNode(var node : TAVLNode;
target_id : Integer; var shrunk : Boolean);
var
target : TAVLNode;
begin
//X Если мы у основания дерева, то искомый узел находится не здесь.
if (node = nil) then
begin
shrunk := False;
expend;
if (target_id begin
// Поиск левого поддерева.
RemoveFromNode(node.LeftChiId,target_id,shrunk);
if (shrunk) then RebalanceLeftShrunk(node,shrunk) ;
end else if (target_id>node.Id) then
begin
// Поиск правого поддерева.
RemoveFromNode(node.RightChild,target_id,shrunk);
if (shrunk) then RebalanceRightShrunk(node,shrunk);
end else begin
// Это искомый узел.
target : = node ;
if (node.RightChild = nil) then
begin
// Узел или не имеет дочерних, или имеет только левый.
node := node.LeftChild;
shrunk := True;
end else if (node. Lef tChild=ii) then
begin
// Узел имеет только правый дочерний.
node := node.RightChild;
shrunk := True;
end else begin
// Узел имеет два дочерних.
ReplaceRightmost(node,node.LeftChiId,shrunk);
if (shrunk) then RebalanceLeftShrunk(node,shrunk);
end; // Завершение удаления искомого узла.
// Удаление искомого узла.
target.LeftChild := nil;
target.Rightchild := nil;
target.Free;
end;
end;
// Замена искомого узла крайним правым потомком слева.
procedure TAVLTree.ReplaceRightmost(var target, repi : TAVLNode;
var shrunk : Boolean);
var
old_repl : TAVLNode;
begin
if (repl.RightChild = nil) then
begin
// repl - это узел, которым заменят искомый.
// Запоминание положения узла.
old_repl := repl;
// Замена repl его левым дочерним узлом.
repl := repl.LeftChild;
// Заменить искомый узел переменной old_repl.
old_repl.LeftChild := target.LeftChild;
old_repl.RightChild := target.RightChild;
old_repl.Balance := target.Balance;
target := old_repl;
shrunk := True;
end else begin
// Рассмотрение правых ветвей.
ReplaceRightmost(target,repl.RightChild,shrunk) ;
if (shrunk) then RebalanceRightShrunk(repl,shrunk);
end;
end;
// Выполнение вращения вправо или влево-вправо после сокращения
// правой ветви.
procedure TAVLTree.RebalanceRightShrunk(var node : TAVLNode;
var shrunk : Boolean);
var
child, grandchild :T AVLNode;
child_bal, grandchild_bal : TBalance;
begin
if (node.Balance = RightHeavy) then
begin
// Правое поддерево было длиннее. Теперь сбалансировано.
node.Balance := Balanced;
end else if (node.Balance=Balanced) then
begin
// Был баланс. Теперь левое поддерево длиннее.
node.Balance := LeftHeavy;
shrunk := False;
end else begin
// Левое поддерево было длиннее. Теперь разбалансировано.
Child := node.LeftChild;
child_bal := child.Balance;
if (child_bal<>RightHeavy) then
begin
// Вращение вправо.
node.LeftChild := child.RightChild;
child.RightChild := node;
if (child_bal = Balanced) then
begin
node.Balance := LeftHeavy;
child.Balance := RightHeavy;
shrunk := False;
end else begin
node.Balance := Balanced;
child.Balance := Balanced;
end;
node := child;
end else begin
// Вращение влево-вправо.
grandchild := child. RightChild;
grandchild_bal := grandchild.Balance;
child.RightChild := grandchild.LeftChild;
grandchild.LeftChild := child;
node.LeftChild := grandchild.RightChild;
grandchild.RightChild := node;
if (grandchild_bal = LeftHeavy) then
node.Balance := RightHeavy
else
node.Balance := Balanced;
if (grandchild_bal = RightHeavy) then
child.Balance := LeftHeavy
else
child.Balance := Balanced;
node := grandchild;
grandchild.Balance := Balanced;
end; // Конец if ... else .. .
end; // Конец if balanced/left heavy/left unbalanced
end;








http://ugabuga.ru/myphology.php славится своими богами, такими как Посейдон и Зевс
Опубликовал Kest October 26 2009 08:57:36 · 0 Комментариев · 5970 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Разработка распре...
Род Стивенс. Delp...
AVIwriter
Искусство програм...
ADVstatusbar
Иллюстрированный ...
AdBlaster v2.5 - ...
Программирование ...
Java 2 - Эффектив...
oTextrackBar
Модифицированная ...
Image Browser [Ис...
Программирование ...
Длинный заголовок...
С/C++ Программиро...
Error mod
iChat v.7.0 Final...
AboutSystem
3d Tank [Исходник...
Tetris 2002

Топ загрузок
Приложение Клие... 100772
Delphi 7 Enterp... 97809
Converter AMR<-... 20261
GPSS World Stud... 17014
Borland C++Buil... 14189
Borland Delphi ... 10267
Turbo Pascal fo... 7372
Калькулятор [Ис... 5972
Visual Studio 2... 5206
Microsoft SQL S... 3661
Случайные статьи
Блоки работы с при...
Основы архитектуры VM
В случае атаки сис...
Последний вариант ...
Сколько по времени...
О возможностях игр...
Модные кроссовки 2017
Содержание
Щедрые игровые авт...
Введение
Взаимодействие або...
Блочная верстка в css
Где купить полноте...
Множество данных м...
Обмен данными межд...
Безопасный и удобн...
Разобрать список н...
Программа Ghostvie...
Пример: решение си...
ИСПОЛЬЗОВАНИЕ ПРЕД...
Всплывающие сообще...
Исходя из сценария...
Стратегии по испол...
Наш метод queueSound
Визуальные эффекты
Статистика



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


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