Добавление вершины в Б-дерево

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

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

При этом возможны следующие две ситуации:

· текущая страница, в которую должен быть вставлен новый элемент, заполнена не полностью (pCurrent^.nPage < 2m); в этом случае новый элемент просто вставляется в данную страницу в нужное место, с увеличением счетчика числа элементов на странице

· пусть текущая страница заполнена полностью, т.е. pCurrent^.nPage = 2m; добавление элемента на полностью заполненную страницу реализуется за счет разделения этой страницы на две страницы; создается новая страница, и после этого старая и новые страницы заполняются равномерно:

Ø левые m элементов передаются на новую страницу

Ø правые m элементов остаются на старой странице

Ø центральный (серединный) элемент передается наверх на родительскую страницу

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

Пример. Пусть в Б-дерево порядка 2 надо добавить вершину с ключом х = 32

Страница, на которую надо добавить ключ 32, заполнена полностью, поэтому создается новая страница с элементами 32 и 35, на старой остаются ключи 42 и 46, а элемент 40 выталкивается на родительскую страницу, занимая в ней крайнее правое место

Такой алгоритм добавления сохраняет структуру Б-дерева, т.к. синхронно на 1 увеличивается число элементов на родительской странице и число ее страниц-потомков.

Если в данном примере добавить еще элементы 36 и 38, то при попытке добавления элемента 33 опять придем к необходимости расщепления страницы:

Поскольку корневая страница заполнена полностью, происходит ее расщепление на две страницы, выталкивание наверх элемента 30 и создание новой корневой страницы

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

Для рекурсивной реализации надо ввести подпрограмму Add, которая должна использовать три параметра:

· адрес новой текущей страницы, используемый как в процессе движения от корневой страницы к терминальной, так и обратно; поскольку этот адрес автоматически должен запоминаться и восстанавливаться, ссылочный параметр надо объявить как параметр-значение

· выходной логический параметр, который определяет факт расщепления текущей страницы и, следовательно, необходимость добавления выталкиваемого элемента на родительскую страницу

· выходной параметр-переменная, через который на родительскую страницу передается сам выталкиваемый элемент.

Схематично подпрограмма Add описывается следующим образом

procedure Add ( pCurrent : pPage; var IsUp : boolean; var Item : TItem);

Begin

if pCurrent = nil then {элемента в дереве нет}

Begin

“формирование полей нового элемента Item”;

IsUp := true;

End

else begin {продолжаем поиск на странице pCurrent}

“загрузка новой страницы”;

“поиск на странице элемента с заданным ключом”;

if “элемент найден” then “обработка элемента”

Else begin

“определение адреса страницы для продолжения поиска”;

Add ( “адрес страницы”, IsUp, Item);

if IsUp then {добавить элемент на текущую страницу }

if pCurrent^.nPage < 2m then

Begin

pCurrent^.nPage := pCurrent^.nPage + 1;

IsUp := false;

“добавление элемента Item в страничный массив”

End

Else begin

“создание новой страницы”;

“формирование полей новой страницы”;

“корректировка полей старой страницы”;

“формирование выталкиваемого наверх элемента”

end;

end;

end;

end;

Как обычно, начальный вызов подпрограммы Add выполняется из главной программы, причем после возврата обратно в главную программу, возможно, придется создавать новую корневую страницу:

Begin

Add (pRoot, IsUp, Item);

if IsUp then

Begin

pTemp := pRoot; New(pRoot);

pRoot^.nPage := 1; pRoot^.LeftPage := pTemp;

pRoot^.mas[1] := Item;

end;

end;