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

UptoLike

ВУЗ: 

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

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

Рубрика: 

73
Опять получилось переполнение, при обработке которого вершина,
содержащая элементы 8, 10 и 12 разделится на две вершины: вершину с
элементом 8 и вершину с элементом 12, – а средний элемент 10 будет
вынесен на верхний уровень (рис. 21, г).
Получилось переполнение в корне дерева. Как оговаривалось ранее,
этот случай надо обработать отдельно. Это связано с тем, что здесь
необходимо создать новый корень, в который во время деления будет
вынесен средний элемент. Теперь полученное дерево не имеет пере-
полнения (рис. 21, д).
В этом случае, как и при поиске, время обработки вершины есть
величина постоянная, пропорциональная размеру вершины, а значит,
временная сложность T(n) алгоритма добавления в B-дерево будет так-
же пропорциональна O(h), где h – глубина дерева.
Удаление элемента из B-дерева предполагает успешный предвари-
тельный поиск вершины, содержащей искомый элемент. Если такая вер-
шина не найдена, то удаление не производится.
При удалении, так же как и при добавлении, необходимо делать так,
чтобы число элементов в вершине лежало между NumberOfItems/2
и NumberOfItems. Если при добавлении могла возникнуть ситуация
переполнения вершины, то при удалении можно получить порожнюю
вершину. Это означает, что число элементов в вершине оказалось мень-
ше NumberOfItems/2. В этом случае надо посмотреть, нельзя ли за-
нять у соседней вершины слева или справа («перелить» часть элемен-
тов от нее) некоторое количество элементов так, чтобы их (элементов)
стало поровну и не было порожних вершин. Такое переливание воз-
можно, если суммарное число элементов у данной вершины и соседней
больше или равно NumberOfItems.
Если переливание невозможно, то объединяем данную вершину с
соседней. При этом число элементов в родительской вершине умень-
шится на единицу и может статься, что опять получаем порожнюю вер-
шину. В худшем случае волна объединений дойдет до корня. Случай
корня надо обрабатывать особо, потому что в корне не может быть ме-
нее одного элемента. Поэтому, если в корне не осталось ни одного эле-
мента, надо сделать корнем ту единственную вершину, на который ссыла-
ется корень через ссылку Node.Items[0].NextNode, а старый ко-
рень удалить.
Приведем алгоритм удаления элемента Item из B-дерева:

Страницы