Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
branch:= 1 to node.NumKeys do(value<=node.Key[branch]) then:=(value=node.Key[branch]);;;;(match) then('Узел с ключом '+Form1.Edit1.Text+' есть в базе');:=true;;:= node.Child[branch - 1]; //(match)(child = nil) and (not fl)('Узел с ключом '+Form1.Edit1.Text+' есть в базе');SearchFromNode(child, value, search);;
TBTree.SplitNode(node: TBtreeNode; spot: Integer;up_key: Integer; var up_node: TBtreeNode);i,return_key: integer;_node,right_child0:TBTreeNode;_node:=TBTreeNode.Create; //создаем новый сегмент
if (spot<=ORDER+1) //смотрим куда нам надо вставлять новый ключ//проверяем место вставки по отношению к середине сенмента(spot=ORDER+1) //вставлять надо на место сегмента, где
ключ=середина+1//объявляем тогда новый узел - корнем
return_key:=up_key;_child0:=up_node;
end//иначе нам необходимо добавление в начало старого сегмента_key:=node.Key[ORDER]; //сохраняем ключ последнего эл-та в
первой половине сегмента
right_child0:=node.Child[ORDER]; //сохраняем ссылку.Key[ORDER]:=0; //обнуляем ключ.Child[ORDER]:=nil; //и сбрасываем ссылкуi:=ORDER downto spot+1 do //вставляем нов.узел в сегмент.Key[i]:=node.Key[i-1]; //переписываем.Child[i]:=node.Child[i-1];;.Key[spot]:=up_key;.Child[spot]:=up_node;;i:=1 to ORDER do
begin //заносим вторую половину старого сегмента в первую нового
return_node.Key[i]:=node.Key[i+ORDER];_node.Child[i]:=node.Child[i+ORDER];
node.Key[i+ORDER]:=0; //вторую половину старого сегмента обнуляем
node.Child[i+ORDER]:=nil; //и сбрасываем ссылки;
else //иначе наш новый ключ должен быть самым правым:=spot-ORDER-1; //ставим тогда ветвь для нового сегмента в начало_key:=node.Key[ORDER+1]; //сохраняем ключ и левуюот него
ссылку
right_child0:=node.Child[ORDER+1];.Key[ORDER+1]:=0; //обнуляем ключ и скидываем ссылку.Child[ORDER+1]:=nil;i:=1 to spot-1 do
begin //если надо - переносим узлы второй половины дробимого
сегмента
return_node.Key[i]:=node.Key[i+ORDER+1];_node.Child[i]:=node.Child[i+ORDER+1];.Key[i+ORDER+1]:=0; //обнуляем эти узлы.Child[i+ORDER+1]:=nil;;_node.Key[spot]:=up_key; //вставляем новый ключ_node.Child[spot]:=up_node; //и ссылкуi:=spot+1 to ORDER do
begin //освобождаем вторую половину старого сегмента, переносим в
новый
return_node.Key[i]:=node.Key[i+ORDER];_node.Child[i]:=node.Child[i+ORDER];.Key[i+ORDER]:=0;.Child[i+ORDER]:=nil;
end;;.NumKeys:=ORDER; //задаем для новых сегментов кол-во ключей_node.NumKeys:=ORDER;_node.Child[0]:=right_child0; //определяем ссылку нового
сегмента, как ту что сохранена в буфере
up_node:=return_node;_key:=return_key;;
TBTree.SwapNode(node: TBtreeNode; key_num: Integer;_node: TBtreeNode; var too_small: Boolean);rightmost_child:TBtreeNode;:integer;:= down_node.NumKeys; //проверяем самый правый элемент_child := down_node.Child[num];(rightmost_child = nil)//элемент найден, меняем
node.Key[key_num] := down_node.Key[num]; //ставим последний
элемент на место удаляемого_node.Key[num] := 0; //сам элемент обнуляем_node.NumKeys := num - 1; //кол-во ключей стало меньше_small := (down_node.NumKeys < ORDER); //проверяем кол-во
ключей//иначе мы еще не в листе, продолжаем спускаться
SwapNode(node, key_num, rightmost_child, too_small);
if (too_small) then // если сегмент слишком маленький
TooSmall(down_node,rightmost_child,down_node.NumKeys,too_small);;;
TBTree.TooSmall(parent,child:TBtreeNode; child_num:Integer;
var too_small:Boolean);num_in_parent,num_in_sibling:integer;_to_move,i:integer;:TBtreeNode;_in_parent := parent.NumKeys;
if (child_num < num_in_parent) //смотрим количество ключей у смежных
сегментов//проверяем смежный сегмент справа, хватит ли ему ключей
child_num := child_num + 1;:= parent.Child[child_num];_in_sibling := sibling.NumKeys;_to_move := (num_in_sibling - ORDER + 1) div 2;.Key[ORDER] := parent.Key[child_num];.Child[ORDER] := sibling.Child[0];.Child[0] := nil;(num_to_move > 0) //ключей хватает?i := 1 to num_to_move - 1 do//тогда переносим.Key[i + ORDER] := sibling.Key[i];.Child[i + ORDER] := sibling.Child[i];.Key[i] := 0;.Child[i] := nil;;.Key[child_num] := sibling.Key[num_to_move]; //определяем
родителя.Child[child_num] := sibling;.Child[0] := sibling.Child[num_to_move];//начинаем заполнять
пустое место_in_sibling := num_in_sibling - num_to_move;i := 1 to num_in_sibling do
begin //переносим элементы в смежном сегменте
sibling.Key[i] := sibling.Key[i + num_to_move];.Child[i] := sibling.Child[i + num_to_move];.Key[i + num_to_move] := 0; //те что перенесли обнуляем.Child[i + num_to_move] := nil;;.NumKeys := num_in_sibling; //обновляем кол-во ключей в брате.NumKeys := ORDER - 1 + num_to_move; //в сегме//обнуляемпоследний элемент.Child[num_in_parent] := nil;
child.NumKeys := KEYS; //кол-во ключей обновляем
parent.NumKeys := num_in_parent - 1;.Free; //удаляем брата_small := (parent.NumKeys < ORDER); //проверяем кол-во ключей
родителя
end;else begin //справа правильных смежных нет, проверяем левого
sibling := parent.Child[child_num - 1];_in_sibling := sibling.NumKeys + 1;_to_move := (num_in_sibling - ORDER) div 2;
if (num_to_move > 0) then//подходит, освобождаем место в ребенке
for i := ORDER - 1 downto 1 do//сдвигаем вправо.Key[i + num_to_move] := child.Key[i];.Child[i + num_to_move] := child.Child[i];
end; //забираем элемент из родителя, заполняем
child.Key[num_to_move] := parent.Key[child_num];.Child[num_to_move] := child.Child[0];_in_sibling := num_in_sibling - num_to_move; //смотрим сколько
отдавать ребенку от смежногоi := num_to_move - 1 downto 1 do//переносим элементы.Key[i] := sibling.Key[i + num_in_sibling];.Child[i] := sibling.Child[i + num_in_sibling];.Key[i + num_in_sibling] := 0;.Child[i + num_in_sibling] := nil;;.Child[0] := sibling.Child[num_in_sibling]; //определяем ссылки на
детей от ребенка.Child[num_in_sibling] := nil;.Key[child_num] := sibling.Key[num_in_sibling]; //обновляем
ссылку от родителя к смежному
sibling.NumKeys := num_in_sibling - 1; //кол-во ключей обновляем.NumKeys := ORDER - 1 + num_to_move;_small := False;else begin //если недостаточно ключей - сливаем.Key[num_in_sibling] := parent.Key[child_num]; //переносим
элемент родителя к смежному.Child[num_in_sibling] := child.Child[0];
child.Child[0] := nil;i := 1 to ORDERn //если недостаточно ключей - сливаем.Key[num_in_sibling] := parent.Key[child_num]; //переносим
элемент родителя к смежному.Child[num_in_sibling] := child.Child[0];
child.Child[0] := nil;i := 1 to ORDER - 1 do //перемещаем значения из ребенка в брата
begin.Key[i + num_in_sibling] := child.Key[i];.Child[i + num_in_sibling] := child.Child[i];.Key[i] := 0;.Child[i] := nil;;.NumKeys := KEYS; //обновляем кол-во ключей
parent.NumKeys := num_in_parent - 1;.Key[child_num] := 0;.Child[child_num] := nil;.NumKeys := 0;.Free; //удаляем пустой сегмент
too_small := (parent.NumKeys < ORDER); //проверяем кол-во ключей
родителя
end;;;
{ TBTreeNode }
TBTreeNode.Create;
begin //создание нового сегмента, кол-во узлов +1
inherited Create;:=NodesAllocated+1;;
TBTreeNode.Destroy;:integer;
begin //удаление сегмента, кол-во сегментов -1
NodesAllocated:=NodesAllocated-1;i:=0 to NumKeys do //освобож?/p>