Стр. 51 - Основы алгоритмов и структур данных

Содержание 49
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.5.3. Алгоритм исключения
Начинаем с поиска. Если исключаемый z находится в листовой странице
(z = 7), то удаляем его оттуда. Если исключаемый z находится не в листовой
странице (z = 10), то заменяем его предшественником или последователем.
Очевидно, и предшественник и последователь могут находиться только в листе.
Таким образом, при удалении всегда одна из листовых страниц теряет ключ.
Если до этого она содержала m > n ключей, то и после удаления она содержит
m >= n ключей. Если же перед удалением страница имела всего n ключей, то в
результате удаления происходит ее переопустошение. Тогда, если у страницы
есть богатый брат, у которого больше чем n ключей, то заимствуем оттуда 1
ключ.
…….8……
4 5 9 11
Рис. 49. Перенос ключей в B-дереве
Если же брат содержит всего n ключей, то объединяем ее с этим братом в
одну страницу, добавляем туда также ключ из отцовской страницы.
(удаляем ключ = 13 )
8 15 20
13 14 16 18
8 20
14 15 16 18
Рис. 50. Удаление ключа в B-дереве