Программно построить недвоичное сильноветвящееся В-дерево с помощью алгоритма поиска и включения элемента на страницу(Procedure SearchB). В программе учесть, что при переполнении страницы происходит расщепление страницы и ,соответственно реорганизация структуры В-дерева.
Есть код.Выводит ошибку в строке Result:=(Root<>nil); в функции TBTree.NotEmpty во втором Unite.
Как сделать вывод с помощью компоненты TreeView?
Код:
Код:
...
const n = 2; //поряд. дерева
KEYS = 2*n; //max кол-во ключей соотв. порядку
type
TBTreeNode = class(TObject) //класс узла дерева
NumKeys:integer; //кол-во ключей в сегм
Key: array [1..KEYS] of integer;
Child: array [0..KEYS] of TBTreeNode; //ссылки на дочерние сегменты
constructor Create;
destructor Destroy;override;
class function NumAllocated:integer;
end;
TBTree = class(TObject)
private
Root:TBTreeNode;
public
destructor Destroy; override;
procedure Add(new_key:integer{; new_text:string});
procedure AddNode(var node:TBtreeNode; new_key:Integer; var
up_node:TBtreeNode; var up_key:Integer; var
split:Boolean{;new_text,up_text:string});
procedure AddWithRoom(node,new_child:TBtreeNode;
spot,new_key:Integer{,new_text:string});
procedure SplitNode(node:TBtreeNode; spot:Integer; var up_key:Integer;
var up_node:TBtreeNode);
...
end;
implementation
uses BTree;
var
NodesAllocated:integer;
{ TBTree }
procedure TBTree.Add(new_key: integer{; new_text:string});
var up_node,old_root:TBTreeNode;
up_key:integer;
split:boolean; begin
AddNode(Root,new_key,up_node,up_key,split{,new_text,up_text});
if Split then begin
old_root:=Root;
Root:=TBtreeNode.Create;
Root.Key[1]:=up_key;
Root.Child[0]:=old_root;
Root.Child[1]:=up_node;
Root.NumKeys:=1;
end end;
procedure TBTree.AddNode(var node: TBtreeNode; new_key: Integer;
var up_node: TBtreeNode; var up_key: Integer; var split: Boolean{;
new_text:string});
var branch:integer;
begin
if (node=nil) //если узел пустthen
begin
up_node:=nil;
up_key:=new_key;
split:=true; //можем добавить узел
exit;
end;
for branch:=0 to node.NumKeys-1 do //по какой ветке идти
if (node.Key[branch+1]>new_key) then break; //проверка ключ узла следующий > искомого элемента
AddNode(node.Child[branch],new_key,up_node,up_key,split); //идем далее по ветке
if split then
begin
if (node.NumKeys<KEYS) //если сегмент не полон, хотя бы одна ячейка пуста
then
begin //добавляем
AddWithRoom(node,up_node,branch+1,up_key);
split:=False; //чтобы не создавать корень
end
else //расщипление
SplitNode(node,branch+1,up_key,up_node);
end;
end;
procedure TBTree.AddWithRoom(node, new_child: TBtreeNode;
spot,new_key: Integer);
var i:integer;
begin
node.NumKeys:=node.NumKeys+1; //добавляем ключ в сегм
for i:=node.NumKeys downto spot+1 do //сдвиг. эл-ты сегм
begin
node.Key[i]:=node.Key[i-1];
node.Child[i]:=node.Child[i-1];
end;
node.Key[spot]:=new_key; //вставл. нов. эл-нт
node.Child[spot]:=new_child;
end;
destructor TBTree.Destroy;
begin
Root.Free;
inherited;
end;
function TBTree.NotEmty: Boolean;
begin
Result:=(Root<>nil);
end;
procedure TBTree.Remove(Value: integer);
var old_root:TBTreeNode;
too_small:Boolean;
begin
RemoveFromNode(Root,value,too_small);
if Root.NumKeys<1 //если корень пуст - удалить уровень
then begin
old_root:=Root;
Root:=Root.Child[0]; //спускаемся по ссылке к сегменту - это новый корень
old_root.Child[0]:=nil;
old_root.Free; //удаляем старый корень
end;
end;
procedure TBTree.RemoveFromNode(node: TBTreeNode; value: integer;
var too_small: Boolean);
var branch,i:integer;
child:TBTreeNode;
match:Boolean;
begin
if (node = nil) //узел пуст - такого ключа нет
then begin
ShowMessage('Узла с таким ключом в базе нет');
too_small:=False;
exit;
end;
match:=False;
for branch:= 1 to node.NumKeys do //просматриваем сегмент, ищем ветку
begin
if (value<=node.Key[branch]) then
begin
match:=(value=node.Key[branch]); //нашли?
break;
end;
end;
child := node.Child[branch - 1]; //
if (match) then
begin
if (child = nil) then //элемент в этом узле
begin //удаляем его
node.NumKeys := node.NumKeys - 1;
too_small := (node.NumKeys < n); //сегмент маленький?
for i := branch to node.NumKeys do
node.Key[i] := node.Key[i + 1];
node.Key[node.NumKeys + 1] := 0;
end else begin //это не лист, значит надо взять элемент слева из листа
SwapNode(node, branch, child, too_small);
if (too_small) then //если теперь лист оказался маленьким - слить сегменты
TooSmall(node, child, branch - 1, too_small);
end;
end else begin //рекурсивно ищем удаляемый ключ для ребенка
RemoveFromNode(child, value, too_small);
if (too_small) then //если сегмент меленький - перестроить его
TooSmall(node, child, branch - 1, too_small);
end;
end;
procedure TBTree.Search(value: integer);
var search:Boolean;
begin
SearchFromNode(Root,value,search);
{ if (fl<>False)
then ShowMessage('Узел с ключом '+Form1.Edit1.Text+' есть в базе'); }
end;
...
25.10.2013, 15:22
Построение Б-дерева
Похожие темы
