Теоретически, удалить элемент из так же просто, как и добавить. На
практике все гораздо сложнее.
Если удаляемый элемент находится не в листе, вы должны заменить его дру-
гим элементом, чтобы сохранить соответствующий порядок расположения. Это
похоже на случай удаления элемента из сортированного дерева или 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 Комментариев ·
12072 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
MOZGoEZIK June 17 2011 22:20:15
По моему на рисунке 7.17 есть ошибка. Там после удаления постоено неправильное дерево...ошибка в полученном корне.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
