Навигация
Главная
Поиск
Форум
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
Модуль Forms 62832
Создание отчето... 62825
ТЕХНОЛОГИИ ДОСТ... 59358
Пример работы с... 58083
Имитационное мо... 54756
Реклама
Детальная информация дозатор локтевой тут.
Сейчас на сайте
Гостей: 11
На сайте нет зарегистрированных пользователей

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

Обучающая и тестирующая программа по здаче экзамена ПДД на Turbo Pascal ...
Изменения контуров и сортировка в двумерном массиве чисел на Turbo Pasca...
База данных электронного документооборота на Delphi + бд Intebase

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
Удаление элементов из Б-дерева
Теоретически, удалить элемент из так же просто, как и добавить. На
практике все гораздо сложнее.
Если удаляемый элемент находится не в листе, вы должны заменить его дру-
гим элементом, чтобы сохранить соответствующий порядок расположения. Это
похоже на случай удаления элемента из сортированного дерева или 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 13:06:33 · 1 Комментариев · 9008 Прочтений · Для печати

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


Комментарии
MOZGoEZIK June 18 2011 02: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...
Шаблон для новост...

Случайные загрузки
Интерактивный инт...
Измерение тактово...
База каталогов ( ...
Пишем программы и...
Borland C++Builde...
AID антивирус
Размещение элемен...
32 урока по Delphi
Scrrlcaptoin
PHP5. Профессиона...
TmxOutlookBarPro
Х. М. Дейтел, П. ...
FileFind
PHP 5
Мод "register.php...
iComm v.6.1 - выв...
Использование Lis...
Последние загруж...
Пользовательская...
Фильтры изображений

Топ загрузок
Приложение Клие... 100422
Delphi 7 Enterp... 84985
Converter AMR<-... 20062
GPSS World Stud... 11985
Borland C++Buil... 11408
Borland Delphi ... 8388
Turbo Pascal fo... 7008
Visual Studio 2... 4985
Калькулятор [Ис... 4631
FreeSMS v1.3.1 3530
Случайные статьи
Представления дере...
Чистка монитора, п...
Игры. Интернет-пон...
Network File System
Где мы находимся?
Триггеры событий, ...
СТАТИЧЕСКИЙ ИЛИ ВИ...
Коммутаторы локаль...
Навигация по данны...
Подводные камни вн...
Filles kazakh
Подсчет атомов и ч...
Эмулятор микропроц...
Случайные объекты
Текстовое наполнен...
Глава 21. Жизне...
Что нужно для двои...
Балансировка деревьев
безопасные динамич...
Лунтик аниматор
Пример приложения ...
Блокировка сна
Измените громкость...
Маршалер свободной...
4. Закрытый ключ в...
Статистика



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


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