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-дереве
1...,41,42,43,44,45,46,47,48,49,50 52,53,54,55,56,57,58,59,60,61,...106