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

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

Изменения контуров и сортировка в двумерном массиве чисел на Turbo Pasca...
База данных - рабочее место кассира на Delphi + бд Access
Моделирование ЭВМ на GPSS (три класса заданий) + Пояснительная записка

Реклама



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

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


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

Случайные загрузки
Простой текстовый...
Программирование ...
Иллюстрированный ...
TrayComp
PBFoldder
Разработка клиент...
Программирование ...
De Knop
MxProtector
Adapter (пример D...
HtmlLerz PRO
Еext Editor
ИНТЕРНЕТ ПРОГРАММ...
Рисование PopupMenu
Дешифратор содерж...
Создание меню на ...
Программирование ...
3D Тетрис [Исходн...
Шейдеры в Delphi
Visual Basic for ...

Топ загрузок
Приложение Клие... 100469
Delphi 7 Enterp... 87052
Converter AMR<-... 20078
GPSS World Stud... 12819
Borland C++Buil... 11831
Borland Delphi ... 8603
Turbo Pascal fo... 7039
Visual Studio 2... 4999
Калькулятор [Ис... 4799
FreeSMS v1.3.1 3542
Случайные статьи
Кто пишет тесты?
Решение для случая...
будут соединяться ...
— только на объект...
• Почта со специфи...
Установка встроенн...
Создание значка ко...
Ремонт планшетов
Геотермальная энер...
Программирование: ...
Ручная разметка
Переменные объекты
Организация информ...
Отправка и получен...
Исследование модел...
Тонкости дизассемб...
Сканирование фотог...
Введение в язык XSLT
В задаче строим сл...
Разборка приставки...
Получить адреса и ...
Cannot Read or Wri...
Поиск документов в...
Многопользовательс...
ПРЕДИСЛОВИЕ К ПЕРВ...
Статистика



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


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