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

UptoLike

ВУЗ: 

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

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

Рубрика: 

70
Если бы в примере осуществлялся поиск, допустим, элемента 18, то,
просмотрев три вершины (последняя с элементом 17), было бы обнару-
жено, что от элемента 17 нет ссылки на поддерево с элементами, боль-
шими, чем 17, и на основании этого сделали бы вывод, что элемента 18
в дереве нет.
Теперь приведем точно сформулированный алгоритм поиска элемента
Item в B-дереве, предположив, что функция LookFor возвращает но-
мер первого большего или равного элемента вершины (фактически про-
изводит поиск в вершине).
function BTree_Search(Item: ItemType, BTree: PBTreeNode): boolean;
var
CurrentNode: PBTreeNode;
Position: integer;
begin
BTree_Search := False;
CurrentNode := BTree;
repeat
{Ищем в текущей вершине}
Position := LookFor(CurrentNode, Item);
if (CurrentNode.Count >= Position) and
(CurrentNode.Items[Position].Value = Item) then begin
{Элемент найден}
BTree_Search := True;
Exit;
end;
if CurrentNode.Items[Position-1].NextNode = nil then
{Элемент не найден и дальше искать негде}
break
else
{Элемент не найден, но продолжаем поиск дальше}
CurrentNode := CurrentNode.Items[Position-1].NextNode;
until False;
end;
Здесь пользуемся тем, что, если ключ лежит между Items[i].Value
и Items[i+1].Value, то во внутреннюю память надо подкачать вер-
шину, на которую указывает Items[i].NextNode.
Заметим, что для ускорения поиска ключа внутри вершины (функ-
ция LookFor), можно воспользоваться бинарным поиском (см. 2.3.1.2).

Страницы