Навигация
Главная
Поиск
Форум
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
Реклама
Сейчас на сайте
Гостей: 7
На сайте нет зарегистрированных пользователей

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

Моделирование работы обрабатывающего участка цеха в GPSS
Моделирование работы аэропорта на GPSS + Пояснительная записка
моделирование процесса поступления заявок в ЭВМ на GPSS + Пояснительная ...

Удаление элементов из Б-дерева
Теоретически, удалить элемент из так же просто, как и добавить. На
практике все гораздо сложнее.
Если удаляемый элемент находится не в листе, вы должны заменить его дру-
гим элементом, чтобы сохранить соответствующий порядок расположения. Это
похоже на случай удаления элемента из сортированного дерева или AVL-дерева,
поэтому можно обрабатывать этот случай подобным образом. Замените элемент
крайним правым элементом из левой ветки. Этот элемент будет всегда находиться
в листе. После замены элемента можно считать, что вместо него просто удален заменивший его лист.
Чтобы удалить элемент из листа, сначала нужно сдвинуть все Другие элемен-
ты влево, чтобы заполнить оставшееся место. Помните, что каждый узел в Б-дере-
ве порядка К должен содержать от К до 2 * К элементов. После того как вы удаля-
ете элемент из листа, он может содержать всего К - 1 элементов.
В этом случае попробуйте взять несколько элементов из узлов на том же уровне.
Затем перераспределите элементы в этих двух узлах так, чтобы они имели не менее
К элементов. На рис. 7.17 элемент был удален из крайнего левого листа в дереве,
при этом узел остался всего с одним элементом. Перераспределение элементов меж-
ду узлом и его правым сестринским дает обоим узлам, по крайней мере, по два клю-
ча. Обратите внимание, что средний элемент J сдвинут в родительский узел.
Перераспределение узлов после удаления одного из них
Рис. 7.17. Перераспределение узлов после удаления одного из них
При попытке сбалансировать дерево таким образом может оказаться, что со-
седний узел на том же уровне содержит всего К элементов. Между искомым уз-
лом и его сестринским имеется всего 2 * К - 1 элементов, поэтому недостаточно ис-
пользовать эти два узла. В этом случае все элементы в обоих узлах могут поместиться
в пределах одного узла, поэтому вы можете объединить их. Удалите ключ, который
отделяет эти два узла от родительского. Поместите этот элемент и 2 * К - 1 элемен-
тов этих двух узлов в один общий. Процесс объединения двух узлов называется
слиянием сегментов, или объединением сегментов (bucket merge, или bucket join).
На рис. 7.18 показано, как объединять Два узла.
Объединение после удаления узла
Рис. 7.18. Объединение после удаления узла
При слиянии двух узлов из родительского удаляется ключ, и там остается
К - 1 элементов. В этом случае необходимо перебалансировать или объединить
его с одним из сестринских узлов. Но если после этого в узле на более высоком
уровне все равно останется К - 1 элементов, процесс
повторится. В наихудшем случае удаление вызовет
«цепную реакцию» слияния сегментов узлов вплоть
до корня.
Если вы удаляете последний элемент из корне-
вого узла, объедините два оставшихся дочерних узла
корня в новый корень и сократите дерево на один
уровень. Единственный способ уменьшения глуби-
ны дерева - это объединение дочерних узлов корня,
при котором образуется новый корень.









Опубликовал Kest October 29 2009 10:06:33 · 1 Комментариев · 11868 Прочтений · Для печати

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


Комментарии
MOZGoEZIK June 17 2011 22:20:15
По моему на рисунке 7.17 есть ошибка. Там после удаления постоено неправильное дерево...ошибка в полученном корне.
Добавить комментарий
Имя:



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

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

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

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

Пароль



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

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

Случайные загрузки
Swat [Исходник на...
PHP: настольная к...
Converter AMR<->W...
Gold Submitter II...
EditButton
Песочные часы
Фундаментальные а...
Visual Basic for ...
Панель случайной ...
Цветной Grid
Популярные загрузки
TrayComp
FreeNet
Пример OpenGL гра...
Мод "проверочный ...
Assistant
Borland Delphi 8 ...
Swing. Эффектные...
Язык программиров...
Клавиатурный трен...

Топ загрузок
Приложение Клие... 100774
Delphi 7 Enterp... 97863
Converter AMR<-... 20273
GPSS World Stud... 17024
Borland C++Buil... 14197
Borland Delphi ... 10309
Turbo Pascal fo... 7376
Калькулятор [Ис... 5997
Visual Studio 2... 5208
Microsoft SQL S... 3661
Случайные статьи
10.2. Пример
Особенности знаний
Игровые автоматы В...
Игнорирование отри...
Стандартные числов...
Ввод-вывод: заголо...
Источник данных
Идея регулярных вы...
Определения риска
СПОСОБЫ РАСПОЗНАВА...
Базы данных и базы...
POD-типы
Широкие строковые ...
Моделирование непр...
Google, Yahoo и Mi...
Проверка достоверн...
СТАТИЧЕСКИЙ ИЛИ ВИ...
Возможные структур...
План проведения те...
Микроконтроллер Ad...
Построение списка
Встроенные элементы
Вулкан Россия казино
Обычный режим UNICAST
Чтение файлов MS W...
Статистика



Друзья сайта
Программы, игры
Error: Incorrect password!
Error: Incorrect password!


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