Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
: 1, 3, 4, 5, 6, 9, 10, 11, 12, 14, 15, 16, 17. При другой попытке заполнения после 15 затем сразу следовало 17 сегментов. Можно сделать вывод, что от значения ключа зависит все, как уже говорилось ранее, в самом худшем случае может получиться наравне с рекурсивным объединением, рекурсивное дробление.
Заключение
В ходе данной курсовой работы были подробно рассмотрены варианты работы с организацией базы данных с помощью сбалансированных деревьев, а именно с помощью В-деревьев. Были рассмотрены только принципы такой организации, методы добавления, поиска и удаления элементов из нашей структуры. При подготовке к реализации поставленной задачи были изучены и рассмотрены материалы Всемирной сети Интернет и Научной библиотеки ОрелГТУ.
Кроме того, была реализована программа, осуществляющая добавление, поиск и удаление записей из В-дерева.
Данная тема может быть более подробно изучена. Дальнейшая работа с программой подразумевает реализацию изученных методов для хранения полученной базы на жестком диске, так как были использованы только лишь, так называемые, псевдоуказатели, с которыми можно легко работать в оперативной памяти, но для записи в файл такие указатели не подходят.
Таким образом, все поставленные задачи были успешно выполнены.
Список литературы
1.Род Стивенс, Delphi. Готовые алгоритмы: Переводс англ.- М.: ДМК Пресс, 2001.-384с: ил.
2.Карпатов Д.С. Базы данных в Delphi 7.Самоучитель . СПб.-Наука и техника, 2006.
Приложение А (обязательное)
Листинг программы
unit BTree;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, BTreeClass;
= class(TForm): TEdit;: TButton;: TButton;: TButton;: TLabel;: TLabel;: TMemo;: TEdit;AddButtonClick(Sender: TObject);FormCreate(Sender: TObject);FormClose(Sender: TObject; var Action: TCloseAction);Edit1Change(Sender: TObject);RemoveButtonClick(Sender: TObject);SearchButtonClick(Sender: TObject);
{ Private declarations }
{ Public declarations };
: TForm1;:TBTree;
{$R *.dfm}
TForm1.AddButtonClick(Sender: TObject);.Add(StrToInt(Edit1.Text){,Edit2.Text});.Lines.Add(Edit1.Text);.Caption:=IntToStr(TBTreeNode.NumAllocated);.Text:='';;
TForm1.FormCreate(Sender: TObject);.Clear;:=TBTree.Create;;
TForm1.FormClose(Sender: TObject; var Action: TCloseAction);.Free;;TForm1.Edit1Change(Sender: TObject);.Enabled:=(Edit1.Text<>'');.Enabled:=(AddButton.Enabled and Tree.NotEmty);.Enabled:=(AddButton.Enabled and Tree.NotEmty);;
TForm1.RemoveButtonClick(Sender: TObject);.Remove(StrToInt(Edit1.Text));.Caption:=IntToStr(TBTreeNode.NumAllocated);.Text:='';;
TForm1.SearchButtonClick(Sender: TObject);.Search(StrToInt(Edit1.Text));.Text:='';;
.
BTreeClass;
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;= 2; //порядок дерева
KEYS = 2*ORDER; //max кол-во ключей соотв. порядку
type
{ TNode = record:integer;:string[508];; }
= class(TObject) //класс узла дерева
NumKeys:integer; //кол-во ключей в сегменте
Key: array [1..KEYS] of integer; //сегмент: array [0..KEYS] of TBTreeNode; //ссылки на дочерние сегментыCreate;Destroy;override;function NumAllocated:integer;;
= class(TObject):TBTreeNode;Destroy; override;Add(new_key:integer{; new_text:string});AddNode(var node:TBtreeNode; new_key:Integer; var
up_node:TBtreeNode; var up_key:Integer; var
split:Boolean{;new_text,up_text:string});AddWithRoom(node,new_child:TBtreeNode;
spot,new_key:Integer{,new_text:string});SplitNode(node:TBtreeNode; spot:Integer; var up_key:Integer;
var up_node:TBtreeNode);Remove(Value:integer);RemoveFromNode(node:TBTreeNode; value:integer; var
too_small:Boolean);SwapNode(node:TBtreeNode; key_num:Integer;
down_node:TBtreeNode; var too_small:Boolean);TooSmall(parent, child:TBtreeNode; child_num:Integer; var
too_small:Boolean);NotEmty:Boolean;Search(value:integer);SearchFromNode(node:TBTreeNode; value:integer; var
search:Boolean);;
BTree;
:integer;
{ TBTree }
TBTree.Add(new_key: integer{; new_text:string});up_node,old_root:TBTreeNode;_key:integer;:boolean;(Root,new_key,up_node,up_key,split{,new_text,up_text});Split_root:=Root;:=TBtreeNode.Create;.Key[1]:=up_key;
// Root.Key[1].text:=up_text;.Child[0]:=old_root;.Child[1]:=up_node;.NumKeys:=1;;
TBTree.AddNode(var node: TBtreeNode; new_key: Integer;up_node: TBtreeNode; var up_key: Integer; var split: Boolean{;
new_text:string});branch:integer;(node=nil) //если узел пуст, присваиваем ключ_node:=nil;_key:=new_key;
// up_text:=new_text;
split:=true; //теперь мы можем добавить узел
exit;;branch:=0 to node.NumKeys-1 do //смотрим по какой ветке нам идти(node.Key[branch+1]>new_key) then break;(node.Child[branch],new_key,up_node,up_key,split); //идем далее
по ветке
if split(node.NumKeys<KEYS) //если сегмент не полон, хотя бы одна ячейка
пуста
then//добавляем(node,up_node,branch+1,up_key);
split:=False; //это чтобы не создавать корень
end//иначе разбиваем сегмент(node,branch+1,up_key,up_node);;;
TBTree.AddWithRoom(node, new_child: TBtreeNode;
spot,new_key: Integer);i:integer;.NumKeys:=node.NumKeys+1; //добавляем ключ в сегментi:=node.NumKeys downto spot+1 do //сдвигаем элементы сегмента.Key[i]:=node.Key[i-1];
// node.Key[i].text:=node.Key[i-1].text;.Child[i]:=node.Child[i-1];;.Key[spot]:=new_key; //вставляем наш новый элемент
node.Child[spot]:=new_child;;TBTree.Destroy;.Free;;;
TBTree.NotEmty: Boolean;:=(Root<>nil);;
TBTree.Remove(Value: integer);old_root:TBTreeNode;_small:Boolean;(Root,value,too_small);
if Root.NumKeys<1 //если корень пуст - удалить уровень
then_root:=Root;
Root:=Root.Child[0]; //спускаемся по ссылке к сегменту - это новый
корень
old_root.Child[0]:=nil;_root.Free; //удаляем старый корень;;
TBTree.RemoveFromNode(node: TBTreeNode; value: integer;too_small: Boolean);branch,i:integer;:TBTreeNode;:Boolean;(node = nil) //узел пуст - такого ключа нет('Узла с таким ключом в базе нет');
too_small:=False;;;:=False;branch:= 1 to node.NumKeys do //просматриваем сегмент, ищем
ветку(value<=node.Key[branch]) then:=(value=node.Key[branch]); //нашли?;;;:= node.Child[branch - 1]; //(match) then(child = nil) then //элемент в этом узле//удаляем его.NumKeys := node.NumKeys - 1;_small := (node.NumKeys < ORDER); //сегмент маленький?i := branch to node.NumKeys do.Key[i] := node.Key[i + 1];
node.Key[node.NumKeys + 1] := 0;else begin //это не лист, значит надо взять элемент слева из листа
SwapNode(node, branch, child, too_small);
if (too_small) then //если теперь лист оказался маленьким - слить
сегменты
TooSmall(node, child, branch - 1, too_small);
end;else begin //рекурсивно ищем удаляемый ключ для ребенка
RemoveFromNode(child, value, too_small);
if (too_small) then //если сегмент меленький - перестроить его
TooSmall(node, child, branch - 1, too_small);;;
TBTree.Search(value: integer);search:Boolean;(Root,value,search);
{ if (fl<>False)ShowMessage('Узел с ключом '+Form1.Edit1.Text+' есть в базе'); };
TBTree.SearchFromNode(node: TBTreeNode; value: integer; var
search:Boolean);branch,i:integer;:TBTreeNode;,fl:Boolean;(node = nil) //узел пуст - такого ключа нет('Узла с таким ключом в базе нет');
search:=False;;;:=False;:=False;