Удаление вершины из Б-дерева

Пусть имеется Б-дерево порядка m, из которого требуется удалить элемент с ключом х. Прежде всего, организуется поиск удаляемого элемента последовательным просмотром страниц, начиная с корневой. Пусть удаляемый элемент найден на некоторой странице. При этом возможны следующие две ситуации:

• · если найденная страница является терминальной, то элемент просто удаляется с нее с последующей проверкой количества оставшихся на этой странице элементов; если после удаления на странице остается слишком мало элементов, предпринимаются некоторые дополнительные действия, описываемые немного позже;
• · если страница нетерминальная, то на место удаляемого элемента надо поставить элемент-заменитель, который находится также, как и в обычном дереве: входим в левое (правое) поддерево и спускаемся как можно ниже, придерживаясь максимально правых (левых) поддеревьев; после этого надо проверить страницу, с которой был взят элемент-заменитель и при необходимости предпринять корректирующие действия для восстановления структуры Б-дерева.

Например, пусть в простейшем Б-дереве порядка 2 на рисунке ниже требуется удалить элемент с ключом х = 40. Левое поддерево для ключа 40 определяется ссылкой, связанной с его левым соседом, т. е. элементом 20. Просматриваем новую страницу (26, 35), выбираем самый правый элемент 35 и по его ссылке выходим на страницу (36, 37, 38). На этой странице крайний правый элемент 38 не имеет потомка и поэтому именно он должен быть элементом-заменителем. Ясно, что он является ближайшим меньшим элементом по отношению к удаляемому. Путь к элементу-заменителю показан жирной линией.

В обоих случаях после удаления элемента с некоторой страницы надо эту страницу проверить на число оставшихся элементов. По правилам построения Б-деревьев на каждой странице (кроме корневой) не может быть меньше m элементов. Если это условие после удаления не выполняется, т. е. на странице остается лишь m-1 элемент, необходима ее корректировка за счет привлечения одной из соседних страниц. Для этого с помощью родительской страницы определяется адрес соседней страницы и выполняется ее загрузка в ОП. Совместная обработка двух соседних страниц выполняется следующим образом.

• 1. Если на соседней странице имеется более m элементов (хотя бы m+1), то выполняется перераспределение элементов: с более «богатой» соседней страницы некоторое число элементов передается на «бедную» текущую страницу. В простейшем случае достаточно передать один элемент, но на практике чаще всего передается столько элементов, чтобы на этих двух страницах их было почти поровну. Здесь есть один тонкий момент — элементы с одной страницы на другую передаются не прямо, а через родительскую страницу, т. е. происходит как бы перетекание элементов с дочерней страницы на родительскую с вытеснением с нее элементов на текущую страницу.
• 2. Если соседняя страница сама является «небогатой», т. е. содержит ровно m элементов, используется другой прием. В этом случае происходит объединение двух «бедных» страниц с созданием одной полной страницы. Полная страница создается следующим образом: m-1 элемент берется с текущей страницы, m — с соседней и один элемент — с родительской страницы. Интересно, что этот прием заимствования одного элемента с родительской страницы позволяет сохранить необходимую структуру Б-дерева, т.к. синхронно на 1 уменьшается число элементов на родительской странице и число страниц-потомков.

Поскольку число элементов на родительской странице уменьшилось, то надо и эту страницу проверить на «бедность», и, при необходимости, выполнить ее корректировку. Это, в свою очередь, может привести к заимствованию элемента с еще более верхней страницы и т. д. В худшем случае этот процесс распространится до корневой страницы, что может потребовать корректировки самой корневой страницы. Правда, эта корректировка выполняется чуть по-другому, т.к. корневая страница может содержать и меньше m элементов. Особенность возникает лишь тогда, когда до удаления на корневой странице был лишь один элемент, и после удаления она становится пустой. В этом случае эта пустая страница просто удаляется, и тем самым на 1 уменьшается высота Б-дерева.

Пример. Пусть в простейшем Б-дереве порядка 2 удаляется вершина 12 и страница становится «бедной». Соседняя страница (22, 25, 28) может отдать один элемент, и поэтому ключ 22 передается на родительскую страницу, вытесняя с нее ключ 20.

Если в этом дереве удалить, например, вершину 7, то придется объединять две страницы (5) и (10, 20) вместе и добавлять элемент 8 с родительской страницы для создания одной полной страницы.

Программная реализация удаления имеет те же особенности, что и добавление, т. е. необходимо запоминать траекторию движения от корневой страницы к текущей. Для этого можно ввести рекурсивную подпрограмму Delete с тремя параметрами:

• · x — ключ удаляемого элемента (параметр-значение)
• · pCurrent — ссылка на текущую страницу (параметр-значение)
• · IsPure — признак того, что текущая страница после удаления содержит слишком мало элементов (параметр-переменная).

Псевдокод подпрограммы Delete:

procedure Delete (x:; pCurrent: pPage; var IsPure: boolean);

begin.

if pCurrent = nil then «элемента x в дереве нет» .

else begin.

" поиск x на странице pCurrent" ;

if «x найден» then.

begin.

if «страница pCurrent^ терминальная» .

then begin.

" удалить элемент" ;

" уменьшить счетчик числа элементов" ;

" установить признак IsPure" ;

end.

else begin.

" найти элемент-заменитель" ;

" вставить элемент-заменитель на место удаленного x" ;

" уменьшить счетчик числа элементов" ;

" установить признак IsPure" ;

end.

end.

else begin.

Delete (x, «адрес дочерней страницы», IsPure);

if IsPure then «вызов вспом. подпрограммы Pager ()» ;

end;

end;

end;

Здесь используется вспомогательная подпрограмма Pager, выполняющая корректировку страницы после удаления с нее элемента x в случае ее «обеднения». Эта подпрограмма имеет 4 параметра:

• · адрес текущей «бедной» страницы (pCurrent)
• · адрес родительской страницы (pParent)
• · номер элемента на родительской странице, который является непосредственным предком «бедной» страницы (nParent)
• · логический признак (IsPure).

Псевдокод подпрограммы Pager:

procedure Pager (pCurrent, pParent: pPage; nParent: integer; var IsPure: boolean);

var pTemp: pPage; {адрес соседней страницы}.

begin.

" определение адреса pTemp соседней вершины" ;

" определение числа элементов, удаляемых с соседней страницы" ;

" пересылка одного элемента с родительской страницы на текущую" ;

if «со страницы pTemp пересылается более одного элемента» then.

begin.

" пересылка элементов со страницы pTemp на pCurrent" ;

" пересылка одного элемента на родительскую страницу" ;

" сдвиг влево элементов в массиве на странице pTemp" ;

" установка счетчиков числа элементов на соседних страницах" ;

IsPure:= false;

end.

else begin {объединение страниц}.

" пересылка всех эл-тов со страницы pTemp на страницу pCurrent" ;

" сдвиг влево элементов в массиве на родительской странице" ;

" изменение счетчиков числа эл-тов на тек. странице и ее родителе" ;

" удаление пустой страницы pTemp" ;

" установка признака IsPure для родительской страницы" ;

end;

end;

Главная программа должна вызвать подпрограмму Delete, а после возврата из цепочки рекурсивных вызовов — удалить опустевшую корневую страницу.