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

UptoLike

ВУЗ: 

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

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

Рубрика: 

68
В каждой вершине будем хранить не более NumberOfItems запи-
сей. Также необходимо будет хранить текущее количество записей в
вершине. Для удобства возврата назад к корню дерева будем запоми-
нать для каждой вершины указатель на ее предка.
Type
PBTreeNode = ^TBTreeNode;
TBTreeNode = record {вершина дерева}
Count: integer; {количество записей в вершине}
PreviousNode: PBTreeNode; {указатель на предка}
Items: array[0..m+1] of record {массив записей}
Value: ItemType;
NextNode: PBTreeNode;
end;
end;
TBTree = PBTreeNode;
У элемента Items[0] будет использоваться только поле NextNode.
Дополнительный элемент Items[NumberOfItems+1] предназна-
чен для обработки переполнения, о чем будет рассказано ниже, при
описании алгоритма добавления элемента в B-дерево.
Поскольку дерево упорядочено, то
Items[1].Value<Items[2].Value<…<Items[Count].Value.
Указатель Items[i].NextNode указывает на поддерево элемен-
тов, больших Items[i].Value и меньших Items[i+1].Value.
Понятно, что указатель Items[0].NextNode будет указывать на
поддерево элементов, меньших Items[1].Value, а указатель
Указатель
на В-дерево
1 18
1 10 2 22 28
2 4 2 12 16 2 23 24
1 27
2 28 30
Рис. 19. B-дерево и его организация

Страницы