Структуры и алгоритмы обработки данных. Ключарев А.А - 71 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

71
Учитывая то, что время обработки вершины есть величина постоян-
ная, пропорциональная размеру вершины, временная сложность T(n)
алгоритма поиска в B-дереве будет пропорциональна O(h), где h – глу-
бина дерева.
Теперь рассмотрим добавление элемента в B-дерево
Для того чтобы B-дерево можно было считать эффективной структурой
данных для хранения множества значений, необходимо, чтобы каждая вер-
шина заполнялась хотя бы наполовину. Дерево строится снизу. Это означа-
ет, что любой новый элемент добавляется в лист. Если при этом произой-
дет переполнение (на этот случай в каждой вершине зарезервирован лиш-
ний элемент), т. е. число элементов в вершине превысит NumberOfItems,
то надо будет разделить вершину на две вершины и вынести средний эле-
мент на верхний уровень. Может случиться, что при этой операции на
верхнем уровне тоже получится переполнение, что вызовет еще одно деле-
ние. В худшем случае эта волна делений докатится до корня дерева.
В общем виде алгоритм добавления элемента Item в B-дерево мож-
но описать следующей последовательностью действий:
1. Поиск среди листьев вершины Node, в которую следует произве-
сти добавление элемента Item.
2. Добавление элемента Item в вершину Node.
3. Если Node содержит больше, чем NumberOfItems элементов
(произошло переполнение), то:
– делим Node на две вершины, не включая в них средний элемент;
– Item := средний элемент Node;
– Node := Node.PreviousNode;
– переходим к пункту 2.
Заметим, что при обработке переполнения надо отдельно обрабо-
тать случай, когда Node – корень, так как в этом случае
Node.PreviousNode = nil.
Рассмотрим пример. Возьмем дерево (рис. 21, а) и добавим в него
элемент 13.
Двигаясь от корня, найдем лист, в который следует добавить иско-
мый элемент. Таким узлом в нашем случае окажется лист, содержащий
элементы 11 и 12. Добавим в него элемент 13 (рис. 21, б).
Понятно, что при этом получается переполнение. При его обработке
вершина, содержащая элементы 11, 12 и 13, разделится на две части:
вершину с элементом 11 и вершину с элементом 13, – а средний эле-
мент 12 будет вынесен на верхний уровень (рис. 21, в).

Страницы