Размещено на http://www.allbest.ru/

2

Курсовая работа

по дисциплине

Базы данных

тема:

Организация файла в виде B-дерева. Добавление, удаление, поиск. B-l дерево



Содержание

• Введение
• 1. Представление файлов в виде В-дерева
• 2. Программная реализация
• 2.1 Типы данных
• 2.2 Добавление элемента в В-дерево
• 2.3 Поиск элемента
• 2.3 Удаление элемента
• 3. Пример работы программы
• Заключение
• Список литературы
• Приложение А Листинг программы



Введение

В наше время люди повсюду работают с данными. Естественно, возникает необходимость управления этими данными: запись, хранение, обработка и удаление являются инструментами в наших руках. А в условиях нашей жизни при рыночной экономике мы тем более задумываемся над надежностью, целесообразностью и скоростью работы выбранных методов. Все данные, в большинстве случаев, располагаются в базах данных. Здесь вопрос заключается лишь в том, как будет организована эта самая база данных.

Перед реализацией какой-либо операции над записями базы данных необходимо учитывать, что нам все-таки будет нужно, ведь от этого и надо отталкиваться. Но базы данных создаются для того, чтобы впоследствии эти данные можно было найти и использовать. Поэтому основной задачей ставиться эффективная реализация поиска записей в базе данных, который также потребуется и при вставке, и при удалении записей.

В этом плане очень удобно использовать так называемые В-деревья, так как эти деревья сбалансированы и упорядочены, следовательно и доступ к необходимому узлу получается довольно быстро.

Целью данной курсовой работы является организация файла в виде В-дерева, с возможностями вставки, поиска и удаления записи. Для достижения этой цели были поставлены следующие задачи:

- написание процедуры, реализующей добавление записи в базу данных;

- написание процедуры, производящей разбиение блоков записей;

- написание процедуры поиска и удаления элементов по ключу;

- написание процедуры, производящей балансировку и слияние записей в блоке;

- создание приложения, способного производить вышеперечисленные действия.

1. Представление файлов в виде В-дерева

Очевидно, что физическое упорядочение записей индекса имеет те же недостатки, что и физическое упорядочение самих записей основного файла: необходимость реорганизации файла при операциях вставки, удаления, модификации. Следовательно, для организации индекса должен использоваться некоторый вариант кучи. Однако при этом недостаточно иметь простую структуру типа двунаправленного списка, поскольку придется при каждой модификации индекса выполнять сортировку. При этом также следует иметь ввиду, что количество записей в индексе может быть очень велико (размеры файла могут во много раз превышать доступную оперативную память), таким образом, применение обычных методов сортировки, которые ориентируются на размещение всех сортируемых элементов, может быть невозможно.

В оперативной памяти упорядоченные структуры, допускающие эффективную вставку, удаление и модификацию данных обычно организуются в виде сбалансированных деревьев (AVL-деревьев). Сбалансированные деревья - это двоичные деревья, для которых постоянно поддерживается равномерное распределение вершин между поддеревьями. При этом достигается близкая к теоретической (для двоичного поиска) эффективность поиска (порядка шагов, где - общее количество элементов, среди которых происходит поиск) при приемлемых затратах на балансировку.

Однако использование таких структур для организации индексов во внешней памяти оказывается крайне неэффективным из-за больших затрат на ввод вывод. Действительно, поскольку теперь вершины располагаются не в оперативной памяти, а на внешних устройствах, то каждое обращение к вершине (при поиске или в ходе балансировки) требует отдельной операции чтения или записи. Таким образом, если дерево содержит, например 1000000 вершин, то в среднем может потребоваться около 20 операций обращения к внешней памяти. Количество таких обращений будет больше, если происходит балансировка.

Естественным подходом к преодолению данной проблемы является группировка нескольких вершин дерева в один блок ввода-вывода. При этом в древовидную структуру организуются блоки, а не отдельные вершины. Несмотря на то, что возникает необходимость производить поиск внутри блока, количество обращений к устройству внешней памяти сокращается.

Весьма распространенный в настоящее время подход к организации упорядоченных индексов был предложен в 1970г. Р. Бэйером и Э. Мак-Kрейтом. Предложенные ими структуры получили название В-деревьев. В-дерево представляет собой сильно ветвящееся дерево, обладающее следующими свойствами:

- Каждая вершина может содержать не более 2n ключей.

- Каждая вершина за исключением, может быть, корневой содержит не менее n ключей (корневая вершина, если она не является листом, содержит не менее двух потомков).

- Каждая вершина либо представляет собой лист и не имеет потомков, либо имеет в точности m+1 потомка, где m - количество ключей в вершине.

- Все листовые вершины располагаются на одном уровне.

В-дерево может быть построено следующим образом. Последовательность записей, соответствующая записям исходной таблицы, упорядочивается по значениям первичного ключа. Логические записи объединяются в блоки. Значением ключа блока является минимальное значение ключа у записей, входящих в блок. Последовательность блоков представляет собой последний уровень В-дерева. Строится индекс предыдущего уровня. Записи этого уровня содержат значение ключа блока следующего уровня и указатель - адрес связи соответствующего блока ; записи этого уровня также объединяются в блоки. Затем аналогично строится индекс более высокого уровня и т.д., пока количество записей индекса на определенном уровне будет не более установленного числа записей в блоках.

В В-дереве не должно быть блоков, заполненных меньше, чем наполовину. Значение ключа первой записи индексного блока пропускается.

Каждая нелистовая вершина Б-дерева имеет вид:

<p₀, k₁, p₁, k₂, p₂, . . ., p_m-1, k_m, p_m>

Здесь p_i представляет собой указатель на i -го потомка, а k_i - значение ключа поиска (указатели на записи основного файла ради простоты не указаны). Для любого i в диапазоне [1, m-1] все ключи, расположенные в поддереве, на которое указывает указатель p_i, находятся в диапазоне [k_i, k_i+1]. Соответственно, все ключи поддерева p₀ будут меньше k₁, а все ключи поддерева p_m- больше k_m.

Поиск некоторого k ключа в Б-дереве происходит следующим образом. Начиная с корневой вершины выполняется следующая последовательность действий:

Просматриваются ключи k₁, k₂, , k_m, Если искомый ключ k найден, то по соответствующему указателю извлекается запись основного файла. Для поиска ключа в вершине может использоваться либо простой последовательный поиск, если m невелико, или двоичный поиск, для достаточно больших m.

Если k_i< k< k_i+1 для i в диапазоне [1, m-1], то поиск продолжается на странице p_i.

Если k< k₁, то поиск продолжается на странице p₀.

Если k>k_m, то поиск продолжается на странице p_m.

При вставке ключа сначала происходит поиск соответствующей вершины (очевидно, что это будет листовая вершина). Затем происходит следующие операции:

Если найденная вершина содержит менее 2*n ключей, то ключ просто добавляется к данной вершине.

Если страница уже заполнена, то она разделяется на две. При этом 2*n из 2*n+1 ключей пополам (с учетом порядка) распределяются между получившимися вершинами. Центральный ключ (по значению) помещается в родительскую вершину. При этом может произойти ее разделение.

Когда происходит разделение корневой вершины, Б-дерево вырастает на один уровень.

При удалении из Б-дерева происходит балансировка и слияние страниц. Процедуру удаления можно описать следующим образом:

Если удаляемый ключ находится на листовой вершине, то он просто удаляется.

Если удаляемый ключ находится на промежуточной вершине, то он заменяется на смежный элемент, который расположен на листовой вершине.

Если в результате удаления количество ключей вершины стало меньше n, то выполняется балансировка - ключи поровну распределяются между данной, родительской и смежной вершинами.

Если количество ключей на смежной вершине равно n, то балансировка невозможна, но можно слить данную и смежную вершины, заняв один ключ из родительской. Это может привести в свою очередь к балансировке или слиянию на следующем уровне.

Обычно В-дерево храниться в файле по вершинам - каждая вершина занимает виртуальный блок файла, а значит, требует одной операции ввода/вывода. Порядок дерева зависит от размера блока и от размера ключа поиска. Чем больше количество ключей располагается в блоке, тем меньше будет операции ввода/вывода, однако больше операций потребуется для обработки отдельного блока (например, при поиске). Уменьшение количества ключей в блоке приводит к увеличению операций ввода/вывода. На практике критическим местом обычно является именно ввод/вывод, соответственно стремятся увеличивать количество ключей в блоке. Это тем более важно, потому, что доступ к блокам происходит в порядке близком к случайному.

2. Программная реализация

2.1 Типы данных

Данная программа реализована на объектно-ориентированном языке Delphi. Состоит из 2-x модулей и одной формы.

В программе использованы следующие типы данных:

- Key: array [1..KEYS] of integer - массив, хранящий ключи записей.

- Child: array [0..KEYS] of TBTreeNode - массив указателей на другие записи.

Сразу можно заметить, что массив Key можно сделать типом record и задать ему тем самым любую структуру. В виду острой нехватки времени был выбран именно просто массив ключей, с которым работать намного быстрее. В соответствующих местах в коде программы, при изменении типа массива Key и соблюдении соответствующих индексов, остается лишь необходимым прописать заполнение и обработку соответствующих полей.

2.2 Добавление элемента в В-дерево

Вставка элемента производится вызовом процедуры TBTree.Add(new_key: integer), которая со вспомогательными параметрами вызывает процедуру TBTree.AddNode(var node: TBtreeNode; new_key: Integer;

var up_node: TBtreeNode; var up_key: Integer; var split: Boolean). Именно эта процедура является основной. Сначала проверяем не пуст ли корень, если пуст - вставляем первый ключ, иначе мы проверяем наш сегмент дальше.

Если мы находим что ключ не в этом сегменте, то рекурсивно вызываем процедуру AddNode для узла потомка. Если же наш узел должен находиться в этом сегменте, то проверяем место в сегменте, при условии что он уже полон вызываем процедуру для дробления нашего блока SplitNode, иначе у нас еще есть место и вставка производиться через процедуру AddWithRoom (рисунок 1).

Размещено на http://www.allbest.ru/

2

Рисунок 1 - Алгоритм добавления элемента

Процедура AddWithRoom при необходимости сдвигает элементы в блоке вправо и ставит новый элемент на освободившееся место.

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;

SplitNode сначала создает новый сегмент и проверяет в какой части сегмента должен находится новый ключ. Если он должен быть первым из второй половины, то этот элемент будет предком по отношению к ним, а элементы второй половины переносятся в новый сегмент. Если же в первой половине должна произойти вставка, то последний элемент первой половины становиться предком, остальные элементы сдвигаются вправо в освободившееся место ставится новый ключ. Если же требуется вставка в сегмент, начиная от (порядок дерева+2), то ключ на месте (порядок+1) будет предком, а остальные элементы переходят в новый сегмент. В конце определяем количество ключей каждого сегмента, указываем новые ссылки.

2.3 Поиск элемента

Для поиска элемента в В-дереве используются процедуры Search(value:integer) и SearchFromNode(node:TBTreeNode; value:integer, var search:Boolean). Поиск ведется от корня к листьям. Проверяеться корень, если элемент найден, то выводим сообщение что такой элемент найден, иначе смотрим по какой ссылке нам идти. Вызываем рекурсивно SearchFromNode для потомка. Если ссылка равно nil, то такого элемента нет, иначе проверяем далее (рисунок 2).

Размещено на http://www.allbest.ru/

2

Рисунок 2 - Алгоритм выполнения поиска

2.3 Удаление элемента

В теории удалить элемент так же, как и добавить, но на практике это оказалось намного сложнее. Все из-за того, что при удалении у нас может оказаться, что количество ключей в сегменте меньше половины, тогда приходиться либо перераспределять элементы, любо объединять сегменты.

Удаление начинается также с поиска необходимого элемента. Если мы дошли до листа и дальше идти некуда, то значит такого элемента в дереве нет. Если элемент найден в сегменте, но этот сегмент не является листом, значит нам надо взять последний элемент из левого потомка.

if (rightmost_child = nil)

then

begin //элемент найден, меняем

node.Key[key_num] := down_node.Key[num]; //ставим последний элемент на место удаляемого

down_node.Key[num] := 0; //сам элемент обнуляем

down_node.NumKeys := num - 1; //кол-во ключей стало меньше

too_small := (down_node.NumKeys < ORDER); //проверяем кол-во ключей.

Количество ключей не меньше половины - это одно из основополагающих сбалансированности, а распределение элементов между сегментами пополам - это для того, что бы не каждый раз при вставке/удалении производить дробление/слияние.

После того как мы взяли элемент из потомка, необходимо проверить количество ключей, если больше половины - удаление закончилось, если нет - проверяем смежный сегмент справа.

num_in_sibling := sibling.NumKeys;

num_to_move := (num_in_sibling - ORDER + 1) div 2;

child.Key[ORDER] := parent.Key[child_num];

child.Child[ORDER] := sibling.Child[0];

sibling.Child[0] := nil;

if (num_to_move > 0) //ключей хватает?

Если у него хватает элементов для перераспределения, то выполняем, если нет - сливаем эти сегменты. Если же этого выполнить не может - проверяем смежный сегмент слева. Если есть элементы, которые можем забрать, то смотрим, сколько есть таких элементов (рисунок 3). После переноса определяем ссылки для ребенка и для родителя:

num_in_sibling := num_in_sibling - num_to_move; //смотрим сколько отдавать ребенку от смежного

for i := num_to_move - 1 downto 1 do

begin //переносим элементы

child.Key[i] := sibling.Key[i + num_in_sibling];

child.Child[i] := sibling.Child[i + num_in_sibling];

sibling.Key[i + num_in_sibling] := 0;

sibling.Child[i + num_in_sibling] := nil;

end;

child.Child[0] := sibling.Child[num_in_sibling]; //определяем ссылки на детей от ребенка

sibling.Child[num_in_sibling] := nil;

parent.Key[child_num] := sibling.Key[num_in_sibling]; //обновляем ссылку от родителя к смежному

sibling.NumKeys := num_in_sibling - 1; //кол-во ключей обновляем

child.NumKeys := ORDER - 1 + num_to_move;

Затем проверяем количество ключей, которое получилось в родителе. В самом худшем случае удаление элемента вызовет рекурсивно слияние вплоть до корня, также как и при добавлении будет происходить дробление.



Размещено на http://www.allbest.ru/

2

Рисунок 3 - Алгоритм удаления элемента

3. Пример работы программы

Разработанное приложение имеет удобный интерфейс. На форме имеются следующие объекты:

- Edit - для ввода ключа, с которым следует произвести операции добавления/поиска/удаления;

- 3 кнопки для соответствующих операций добавления/поиска/удаления;

- Memo - для отображения ключей, которые были введены в базу (что бы не забыть какие ключи мы добавляли, а какие нет);

- Объекты Label для подсчета количества сегментов в В-дереве, так как визуально мы не можем их рассмотреть. За это количество следить переменная NodesAllocated.

Порядок В-дерева определен как ORDER=2, соответственно ключей в сегменте может быть от 2 до 4, а ключей от 3 до 5.

Испытание начинается с добавления. Первоначально, количество сегментов равно 0. При добавлении ключа 3 появился один сегмент (рисунок 4).

Рисунок 4 - Добавление элемента

После добавления ключей со значениями 2, 5, 7 - количество сегментов не изменилось. Теперь количество ключей максимально, следовательно при добавления любого ключа произойдет дробление сегмента. Добавили ключ со значением 4, количество сегментов стало равным 3. Ввели значение ключа равное 3 и нажали кнопку «Поиск». Программа выдала сообщение «Узел с таким элементом есть в базу» (рисунок 5).

Рисунок 5 - Поиск записи по ключу

Тут же удалили запись под 5 ключом - количество сегментов вновь уменьшилось до 1. При удалении остальных элементов количество сегментов достигло 0 (рисунок 6).

Рисунок 6 - Результат после удаления всех элементов

При постоянном добавлении ключей наблюдалось следующее количество сегментов: 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,

Dialogs, StdCtrls, BTreeClass;

type

TForm1 = class(TForm)

Edit1: TEdit;

AddButton: TButton;

RemoveButton: TButton;

SearchButton: TButton;

Label1: TLabel;

Label2: TLabel;

Memo1: TMemo;

Edit2: TEdit;

procedure AddButtonClick(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

procedure Edit1Change(Sender: TObject);

procedure RemoveButtonClick(Sender: TObject);

procedure SearchButtonClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

Tree:TBTree;

implementation

{$R *.dfm}

procedure TForm1.AddButtonClick(Sender: TObject);

begin

Tree.Add(StrToInt(Edit1.Text){,Edit2.Text});

Memo1.Lines.Add(Edit1.Text);

Label2.Caption:=IntToStr(TBTreeNode.NumAllocated);

Edit1.Text:='';

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Memo1.Clear;

Tree:=TBTree.Create;

end;

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

begin

Tree.Free;

end;

procedure TForm1.Edit1Change(Sender: TObject);

begin

AddButton.Enabled:=(Edit1.Text<>'');

RemoveButton.Enabled:=(AddButton.Enabled and Tree.NotEmty);

SearchButton.Enabled:=(AddButton.Enabled and Tree.NotEmty);

end;

procedure TForm1.RemoveButtonClick(Sender: TObject);

begin

Tree.Remove(StrToInt(Edit1.Text));

Label2.Caption:=IntToStr(TBTreeNode.NumAllocated);

Edit1.Text:='';

end;

procedure TForm1.SearchButtonClick(Sender: TObject);

begin

Tree.Search(StrToInt(Edit1.Text));

Edit1.Text:='';

end;

end.

unit BTreeClass;

interface

uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

const

ORDER = 2; //порядок дерева

KEYS = 2*ORDER; //max кол-во ключей соотв. порядку

type

{ TNode = record

Key:integer;

text:string[508];

end; }

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);

procedure Remove(Value:integer);

procedure RemoveFromNode(node:TBTreeNode; value:integer; var

too_small:Boolean);

procedure SwapNode(node:TBtreeNode; key_num:Integer;

down_node:TBtreeNode; var too_small:Boolean);

procedure TooSmall(parent, child:TBtreeNode; child_num:Integer; var

too_small:Boolean);

function NotEmty:Boolean;

procedure Search(value:integer);

procedure SearchFromNode(node:TBTreeNode; value:integer; var

search:Boolean);

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.Key[1].text:=up_text;

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;

// up_text:=new_text;

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.Key[i].text:=node.Key[i-1].text;

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 < ORDER); //сегмент маленький?

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;

procedure TBTree.SearchFromNode(node: TBTreeNode; value: integer; var

search:Boolean);

var branch,i:integer;

child:TBTreeNode;

match,fl:Boolean;

begin

if (node = nil) //узел пуст - такого ключа нет

then

begin

ShowMessage('Узла с таким ключом в базе нет');

search:=False;

exit;

end;

match:=False;

fl:=False;

for branch:= 1 to node.NumKeys do

begin

if (value<=node.Key[branch]) then

begin

match:=(value=node.Key[branch]);

break;

end;

end;

if (match) then

begin

ShowMessage('Узел с ключом '+Form1.Edit1.Text+' есть в базе');

fl:=true;

end;

child := node.Child[branch - 1]; //

if (match)

then

begin

if (child = nil) and (not fl)

then

begin

ShowMessage('Узел с ключом '+Form1.Edit1.Text+' есть в базе')

end;

end

else SearchFromNode(child, value, search);

end;

procedure TBTree.SplitNode(node: TBtreeNode; spot: Integer;

var up_key: Integer; var up_node: TBtreeNode);

var i,return_key: integer;

return_node,right_child0:TBTreeNode;

begin

return_node:=TBTreeNode.Create; //создаем новый сегмент

if (spot<=ORDER+1) //смотрим куда нам надо вставлять новый ключ

then //проверяем место вставки по отношению к середине сенмента

begin

if (spot=ORDER+1) //вставлять надо на место сегмента, где

ключ=середина+1

then

begin //объявляем тогда новый узел - корнем

return_key:=up_key;

right_child0:=up_node;

end

else

begin //иначе нам необходимо добавление в начало старого сегмента

return_key:=node.Key[ORDER]; //сохраняем ключ последнего эл-та в

первой половине сегмента

right_child0:=node.Child[ORDER]; //сохраняем ссылку

node.Key[ORDER]:=0; //обнуляем ключ

node.Child[ORDER]:=nil; //и сбрасываем ссылку

for i:=ORDER downto spot+1 do //вставляем нов.узел в сегмент

begin

node.Key[i]:=node.Key[i-1]; //переписываем

node.Child[i]:=node.Child[i-1];

end;

node.Key[spot]:=up_key;

node.Child[spot]:=up_node;

end;

for i:=1 to ORDER do

begin //заносим вторую половину старого сегмента в первую нового

return_node.Key[i]:=node.Key[i+ORDER];

return_node.Child[i]:=node.Child[i+ORDER];

node.Key[i+ORDER]:=0; //вторую половину старого сегмента обнуляем

node.Child[i+ORDER]:=nil; //и сбрасываем ссылки

end;

end

else //иначе наш новый ключ должен быть самым правым

begin

spot:=spot-ORDER-1; //ставим тогда ветвь для нового сегмента в начало

return_key:=node.Key[ORDER+1]; //сохраняем ключ и левуюот него

ссылку

right_child0:=node.Child[ORDER+1];

node.Key[ORDER+1]:=0; //обнуляем ключ и скидываем ссылку

node.Child[ORDER+1]:=nil;

for i:=1 to spot-1 do

begin //если надо - переносим узлы второй половины дробимого

сегмента

return_node.Key[i]:=node.Key[i+ORDER+1];

return_node.Child[i]:=node.Child[i+ORDER+1];

node.Key[i+ORDER+1]:=0; //обнуляем эти узлы

node.Child[i+ORDER+1]:=nil;

end;

return_node.Key[spot]:=up_key; //вставляем новый ключ

return_node.Child[spot]:=up_node; //и ссылку

for i:=spot+1 to ORDER do

begin //освобождаем вторую половину старого сегмента, переносим в

новый

return_node.Key[i]:=node.Key[i+ORDER];

return_node.Child[i]:=node.Child[i+ORDER];

node.Key[i+ORDER]:=0;

node.Child[i+ORDER]:=nil;

end;

end;

node.NumKeys:=ORDER; //задаем для новых сегментов кол-во ключей

return_node.NumKeys:=ORDER;

return_node.Child[0]:=right_child0; //определяем ссылку нового

сегмента, как ту что сохранена в буфере

up_node:=return_node;

up_key:=return_key;

end;

procedure TBTree.SwapNode(node: TBtreeNode; key_num: Integer;

down_node: TBtreeNode; var too_small: Boolean);

var rightmost_child:TBtreeNode;

num:integer;

begin

num := down_node.NumKeys; //проверяем самый правый элемент

rightmost_child := down_node.Child[num];

if (rightmost_child = nil)

then

begin //элемент найден, меняем

node.Key[key_num] := down_node.Key[num]; //ставим последний

элемент на место удаляемого

down_node.Key[num] := 0; //сам элемент обнуляем

down_node.NumKeys := num - 1; //кол-во ключей стало меньше

too_small := (down_node.NumKeys < ORDER); //проверяем кол-во

ключей

end

else

begin //иначе мы еще не в листе, продолжаем спускаться

SwapNode(node, key_num, rightmost_child, too_small);

if (too_small) then // если сегмент слишком маленький

TooSmall(down_node,rightmost_child,down_node.NumKeys,too_small);

end;

end;

procedure TBTree.TooSmall(parent,child:TBtreeNode; child_num:Integer;

var too_small:Boolean);

var num_in_parent,num_in_sibling:integer;

num_to_move,i:integer;

sibling:TBtreeNode;

begin

num_in_parent := parent.NumKeys;

if (child_num < num_in_parent) //смотрим количество ключей у смежных

сегментов

then

begin //проверяем смежный сегмент справа, хватит ли ему ключей

child_num := child_num + 1;

sibling := parent.Child[child_num];

num_in_sibling := sibling.NumKeys;

num_to_move := (num_in_sibling - ORDER + 1) div 2;

child.Key[ORDER] := parent.Key[child_num];

child.Child[ORDER] := sibling.Child[0];

sibling.Child[0] := nil;

if (num_to_move > 0) //ключей хватает?

then

begin

for i := 1 to num_to_move - 1 do

begin //тогда переносим

child.Key[i + ORDER] := sibling.Key[i];

child.Child[i + ORDER] := sibling.Child[i];

sibling.Key[i] := 0;

sibling.Child[i] := nil;

end;

parent.Key[child_num] := sibling.Key[num_to_move]; //определяем

родителя

parent.Child[child_num] := sibling;

sibling.Child[0] := sibling.Child[num_to_move];//начинаем заполнять

пустое место

num_in_sibling := num_in_sibling - num_to_move;

for i := 1 to num_in_sibling do

begin //переносим элементы в смежном сегменте

sibling.Key[i] := sibling.Key[i + num_to_move];

sibling.Child[i] := sibling.Child[i + num_to_move];

sibling.Key[i + num_to_move] := 0; //те что перенесли обнуляем

sibling.Child[i + num_to_move] := nil;

end;

sibling.NumKeys := num_in_sibling; //обновляем кол-во ключей в брате

child.NumKeys := ORDER - 1 + num_to_move; //в сегменте, где удаляли

too_small := False; //говорим что здесь уже все в порядке

end

else //иначе не хватает ключей для перерасперделения - необходимо

слияние

begin

for i := 1 to ORDER do

begin //переносим из брата в сегмент, из которого удаляли

child.Key[i + ORDER] := sibling.Key[i];

child.Child[i + ORDER] := sibling.Child[i];

sibling.Key[i] := 0;

sibling.Child[i] := nil;

end;

for i := child_num to num_in_parent - 1 do

begin //аполняем пустое место в родителе

parent.Key[i] := parent.Key[i + 1];

parent.Child[i] := parent.Child[i + 1];

end;

parent.Key[num_in_parent] := 0; //обнуляемпоследний элемент

parent.Child[num_in_parent] := nil;

child.NumKeys := KEYS; //кол-во ключей обновляем

parent.NumKeys := num_in_parent - 1;

sibling.Free; //удаляем брата

too_small := (parent.NumKeys < ORDER); //проверяем кол-во ключей

родителя

end;

end else begin //справа правильных смежных нет, проверяем левого

sibling := parent.Child[child_num - 1];

num_in_sibling := sibling.NumKeys + 1;

num_to_move := (num_in_sibling - ORDER) div 2;

if (num_to_move > 0) then

begin //подходит, освобождаем место в ребенке

for i := ORDER - 1 downto 1 do

begin //сдвигаем вправо

child.Key[i + num_to_move] := child.Key[i];

child.Child[i + num_to_move] := child.Child[i];

end; //забираем элемент из родителя, заполняем

child.Key[num_to_move] := parent.Key[child_num];

child.Child[num_to_move] := child.Child[0];

num_in_sibling := num_in_sibling - num_to_move; //смотрим сколько

отдавать ребенку от смежного

for i := num_to_move - 1 downto 1 do

begin //переносим элементы

child.Key[i] := sibling.Key[i + num_in_sibling];

child.Child[i] := sibling.Child[i + num_in_sibling];

sibling.Key[i + num_in_sibling] := 0;

sibling.Child[i + num_in_sibling] := nil;

end;

child.Child[0] := sibling.Child[num_in_sibling]; //определяем ссылки на

детей от ребенка

sibling.Child[num_in_sibling] := nil;

parent.Key[child_num] := sibling.Key[num_in_sibling]; //обновляем

ссылку от родителя к смежному

sibling.NumKeys := num_in_sibling - 1; //кол-во ключей обновляем

child.NumKeys := ORDER - 1 + num_to_move;

too_small := False;

end else begin //если недостаточно ключей - сливаем

sibling.Key[num_in_sibling] := parent.Key[child_num]; //переносим

элемент родителя к смежному

sibling.Child[num_in_sibling] := child.Child[0];

child.Child[0] := nil;

for i := 1 to ORDER - 1 do //перемещаем значения из ребенка в брата

begin

sibling.Key[i + num_in_sibling] := child.Key[i];

sibling.Child[i + num_in_sibling] := child.Child[i];

child.Key[i] := 0;

child.Child[i] := nil;

end;

sibling.NumKeys := KEYS; //обновляем кол-во ключей

parent.NumKeys := num_in_parent - 1;

parent.Key[child_num] := 0;

parent.Child[child_num] := nil;

child.NumKeys := 0;

child.Free; //удаляем пустой сегмент

too_small := (parent.NumKeys < ORDER); //проверяем кол-во ключей

родителя

end;

end;

end;

{ TBTreeNode }

constructor TBTreeNode.Create;

begin //создание нового сегмента, кол-во узлов +1

inherited Create;

NodesAllocated:=NodesAllocated+1;

end;

destructor TBTreeNode.Destroy;

var

i:integer;

begin //удаление сегмента, кол-во сегментов -1

NodesAllocated:=NodesAllocated-1;

for i:=0 to NumKeys do //освобождение ссылок от ключей

Child[i].Free;

inherited;

end;

class function TBTreeNode.NumAllocated: integer;

begin //получение кол-ва сегментов

Result:=NodesAllocated;

end;

end.

Размещено на Allbest.ru