Программная реализация B+-дерева

}

//---------------------------------------------------------------------------

 

void __fastcall TFormMain::ScrollBarVertScroll(TObject *Sender,

  TScrollCode ScrollCode, int &ScrollPos)

{

Y0 = - ScrollPos + 20;

PaintBox->Refresh();

}

//--------------------------------------------------------------------------- 

Приложение Б

Листинг файла BTree.h

 

 

#pragma once

 

#ifndef BTREE

#define BTREE

 

#define NULL 0

 

typedef enum{

SUCCESS,

NOT_FOUND,

NO_FREE_SPACE,

KEY_ALREADY_EXISTS,

NOT_ENOUGH_KEYS

} RESULT;

 

template <class Data>

class CB_PLUS_Tree

{

public:

static short T;

struct Node{

Data* item;           // массив записей. В узле находятся сами записи, а не указатели

Node** ptr;           // массив указателей на другие узлы

Node* parent;         // родитель узла

short keys_count;     // количество занятых мест в узле

bool leaf;            // является ли узел листом

short index;          // индекс узла

static short T;       // порядок  дерева

short level;          // уровень в иерархии, глубина. 0 у корня

short width;          // ширина (количество листьев, родственных узлу). Для листьев = 1

short indent;         // количество неродственных узлу листьев, висящих слева. У листьев - число левых соседей

 

 

void Reset()

{

T = CB_PLUS_Tree<Data>::T;

item = new Data[2*T+1];       

ptr = new Node*[2*T+2]; 

for (short i=0; i<2*T+1; ++i){

ptr[i] = NULL;

item[i] = NULL;

}

ptr[2*T+1] = NULL;

level = width = indent = 0;

}

 

Node(Data data, Node* p, short i, bool l): keys_count(0), index(i), leaf(l), parent(p)

{

Reset();

if (&data != NULL){

                            if (leaf){

        item[0] = data;

                            } else {

                                item[0].key = data.key;

                            }

    keys_count = 1;

}

}

 

Node(Data * data, Node** pointers, short count, Node* p, short i, bool l):keys_count(count), index(i), leaf(l), parent(p)

{

Reset();

for (short i=0; i<count; ++i){

                                if (leaf){

item[i] = data[i];

                                }else{

                                        item[i].key = data[i].key;

                                }

ptr[i] = pointers[i];

if (ptr[i]!=NULL){

ptr[i]->index = i;

ptr[i]->parent = this;

}

}

ptr[count] = pointers[count];

if (ptr[i]!=NULL){

ptr[count]->index = count;

ptr[count]->parent = this;

}

}

 

 

 

~Node()

{

delete [] item;

delete [] ptr;

parent = NULL;

item = NULL;

ptr = NULL;

keys_count = index = 0;

leaf = true;

}

};

 

Node* root;

 

public:

CB_PLUS_Tree(void);

CB_PLUS_Tree(short t);                      // t - порядок дерева

void SetOrder(short t);               // установка порядка

 

RESULT AddKey(Data);                  // добавление записи в дерево

Node* SearchKey(Data d, Node* node, short & index);  // поиск  записи d в поддереве node. Возвращает узел, в котором завершился поиск. index - возвращаемая позиция ключа в найденном узле. Если поиск неудачный, то index = -1

RESULT  DeleteKey(Data d);

void AssignLevels(Node* node);                            // проход по дереву и установка значений level для каждого узла;

short AssignWidths(Node* node);                           // установка ширины узлов (количества родственных листьев);

    void AssignIndents(Node* node);                           // установка отступов (числа листьев, родственных левым соседям);

~CB_PLUS_Tree(void);

private:

void SplitNode(Node* node);                // разбиение узла

void InsertPointer(Node* node, short index, Node* pointer);     // Вставка указателя

void InsertKey(Node* node, Data d);        // вставка ключа d в узел node

void EraseKeys(Node* node,short start, short count);

void ErasePointers(Node* node,short start, short count);

void Balancing(Node* node);

Node* ReplaceKey(Node* node, short & index);

void ConcatNodes(Node* left, Node* right);

bool TransferFromLeftNode(Node* dest);

bool TransferFromRightNode(Node* dest);

 

};

 

 

template <class Data>

short CB_PLUS_Tree<Data>::T = 3;

 

template <class Data>

short CB_PLUS_Tree<Data>::Node::T = 3;

 

template <class Data>

CB_PLUS_Tree<Data>::CB_PLUS_Tree(void)

{

T = 3;

root = NULL;

}

 

 

 

template <class Data>

CB_PLUS_Tree<Data>::CB_PLUS_Tree(short t)

{

T = t;

root = NULL;

}

 

 

 

template <class Data>

CB_PLUS_Tree<Data>::~CB_PLUS_Tree(void)

{

}

 

 

 

template <class Data>

void  CB_PLUS_Tree<Data>::SetOrder(short t)

{

T = t;

}

 

 

template <class Data>

typename CB_PLUS_Tree<Data>::Node* CB_PLUS_Tree<Data>::SearchKey(Data d, Node* node, short & index)

{

index = -1;

Node* found = NULL;

if (node->leaf){

for (short i=0; i<node->keys_count; ++i){

if (d.key == node->item[i].key){

index = i;

return node;

}

}

return node;

}

for (short i=0; i<node->keys_count; ++i){

if (d.key <= node->item[i].key){

found = SearchKey(d,node->ptr[i],index);

return found;

}

}

found = SearchKey(d,node->ptr[node->keys_count],index);

return found;

}

 

 

 

template <class Data>

void CB_PLUS_Tree<Data>::InsertKey(Node* node, Data d)

{

for (short i = node->keys_count-1; i>=0; --i){

if (d.key > node->item[i].key){

                        if (node->leaf){

        node->item[i+1] = d;

        break;

                        } else {

                                node->item[i+1].key = d.key;

        break;

                        }

}

else{

                        node->item[i+1] = node->item[i];

                        if (i == 0){

                                if (node->leaf){

                                        node->item[i] = d;

                break;

                                } else{

                                        node->item[i].key = d.key;

                break;

                                }

                        }

}

}

}

 

 

 

template <class Data>

void CB_PLUS_Tree<Data>::InsertPointer(Node* node, short index, Node* pointer)

{

for (short i = node->keys_count; i>=index; --i){

node->ptr[i+1] = node->ptr[i];

if (node->ptr[i+1]!=NULL)

node->ptr[i+1]->index = i+1;

}

node->ptr[index] = pointer;

}

 

 

 

template <class Data>

RESULT  CB_PLUS_Tree<Data>::AddKey(Data d)

{

if (root == NULL){                    // если корня нет, то создаем его

root = new Node(d,NULL,0,true);   // с одной записью d

return SUCCESS;

}

short index = -1;

Node* dest = SearchKey(d,root,index);

if (index != -1)                      // запись уже есть в узле

return KEY_ALREADY_EXISTS;

InsertKey(dest,d);

dest->keys_count++;

if (dest->keys_count == 2*T+1)

SplitNode(dest);

return SUCCESS;

}

 

 

 

template <class Data>

void CB_PLUS_Tree<Data>::SplitNode(Node* node)

{

Node * left = NULL;

Node * right = NULL;

        if (!node->leaf){

                left = new Node(&node->item[0],&node->ptr[0],T,node->parent,node->index,node->leaf);

        right = new Node(&node->item[T+1],&node->ptr[T+1],T,node->parent,node->index+1,node->leaf);

        } else{

                left = new Node(&node->item[0],&node->ptr[0],T+1,node->parent,node->index,node->leaf);

        right = new Node(&node->item[T+1],&node->ptr[T+1],T,node->parent,node->index+1,node->leaf);

        }

if (node == root){

                Node* new_root = NULL;

                if (node->leaf){

        new_root = new Node(node->item[T],NULL,0,false);

                }else{

                        new_root = new Node(node->item[T],NULL,0,false);

                }

new_root->ptr[0] = left;

left->index = 0;

new_root->ptr[1] = right;

right->index = 1;

left->parent = right->parent = root = new_root;

}

else{

Node* Parent = node->parent;

Parent->ptr[node->index] = left;

InsertPointer(Parent,node->index+1,right);

                if (node->leaf){

        InsertKey(Parent,node->item[T]);

                } else {

                        InsertKey(Parent,node->item[T]);

                }

Parent->keys_count++;

if (Parent->keys_count == 2*T+1)

SplitNode(Parent);

}

delete node;

}

 

 

 

template <class Data>

RESULT  CB_PLUS_Tree<Data>::DeleteKey(Data d)

{

short index = -1;

Node* node = SearchKey(d,root,index);

if (index==-1)

return NOT_FOUND;

if (node->leaf == false){

node = ReplaceKey(node,index);

}

EraseKeys(node,index,1);

node->keys_count--;

if (node == root && node->keys_count == 0){

root = NULL;

}

else{

Balancing(node);

}

return SUCCESS;

}

 

 

 

template <class Data>

void CB_PLUS_Tree<Data>::Balancing(Node* node)

{

if (node == root)

return;

Node* Parent = node->parent;

bool flag = false;

if (Parent == root)

flag = true;

Node* left = NULL;

Node* right = NULL;

if (node->index != 0)

left = Parent->ptr[node->index-1]; 

if (node->index != Parent->keys_count) 

right = Parent->ptr[node->index+1];

if (node->keys_count < T){

if (left != NULL){

if (!TransferFromLeftNode(node)){

ConcatNodes(left,node);

if ((flag && Parent == root) || !flag)

Balancing(Parent);

}

}

else if (right != NULL){

if (!TransferFromRightNode(node)){

ConcatNodes(node,right);

if ((flag && Parent == root) || !flag)

Balancing(Parent);

}

}

}

}

 

 

template <class Data>

void CB_PLUS_Tree<Data>::ConcatNodes(Node* left, Node* right)

{

Data* items = new Data[2*T+1];

Node** ptrs = new Node*[2*T+2];

        for (short i=0; i<2*T+1; ++i){

            items[i] = NULL;

            ptrs[i] = NULL;

        }

        ptrs[2*T+1]=NULL;

short length;

if (!left->leaf){

length = left->keys_count + right->keys_count + 1;

for (short i=0; i<length; ++i){

if (i < left->keys_count){

items[i] = left->item[i];

ptrs[i] = left->ptr[i];

}

else if (i == left->keys_count){

items[i] = left->parent->item[left->index];

ptrs[i] = left->ptr[i];

}

else if (i < length){

items[i] = right->item[i-left->keys_count-1];

ptrs[i] = right->ptr[i-left->keys_count-1];

}

}

ptrs[length] = right->ptr[right->keys_count];

 

if (left->parent == root && root->keys_count == 1){

Node* new_root = new Node(items,ptrs,length,NULL,0,left->leaf);

root = new_root;

delete left->parent;

}

else{

Node* new_node = new Node(items,ptrs,length,left->parent,left->index,left->leaf);

EraseKeys(left->parent,left->index,1);

                        ErasePointers(left->parent,right->index,1);

left->parent->ptr[left->index] = new_node;

left->parent->keys_count--;

}

 

}

else{

length = left->keys_count + right->keys_count;

for (short i=0; i<length; ++i){

if (i < left->keys_count){

items[i] = left->item[i];

ptrs[i] = left->ptr[i];

}

else {

items[i] = right->item[i-left->keys_count];

ptrs[i] = right->ptr[i-left->keys_count];

}

}

ptrs[length] = right->ptr[right->keys_count];

if (left->parent == root && root->keys_count == 1){

Node* new_root = new Node(items,ptrs,length,NULL,0,left->leaf);

root = new_root;

delete left->parent;

}

else{

Node* new_node = new Node(items,ptrs,length,left->parent,left->index,left->leaf);

EraseKeys(left->parent,left->index,1);

ErasePointers(left->parent,right->index,1);

left->parent->ptr[left->index] = new_node;

left->parent->keys_count--;

}

}

delete left;

delete right;

delete [] items;

delete [] ptrs;

left = right = NULL;

items = NULL;

ptrs = NULL;

 

}

 

 

 

 

template <class Data>

bool CB_PLUS_Tree<Data>::TransferFromLeftNode(Node* dest)

{

Node* left = NULL;

if (dest->index !=0)

left = dest->parent->ptr[dest->index-1];

else

return false;

if (left->keys_count < T+1)

if (TransferFromLeftNode(left)!=true)

return false;

        if (!dest->leaf){

         InsertPointer(dest,0,left->ptr[left->keys_count]);

          ErasePointers(left,left->keys_count,1);

         if (dest->ptr[0] != NULL){

          dest->ptr[0]->parent = dest;

          dest->ptr[0]->index = 0;

        }

        InsertKey(dest,left->parent->item[left->index]);

        dest->keys_count++;

        left->parent->item[left->index] = left->item[left->keys_count-1];

        EraseKeys(left,left->keys_count-1,1);

        left->keys_count--;

        }else{

                dest->parent->item[left->index] = left->item[left->keys_count-2];

                InsertKey(dest,left->item[left->keys_count-1]);

                dest->keys_count++;

                EraseKeys(left,left->keys_count-1,1);

                left->keys_count--;

        }

return true;

}

 

 

 

template <class Data>

bool CB_PLUS_Tree<Data>::TransferFromRightNode(Node* dest)

{

Node* right = NULL;

if (dest->index != dest->parent->keys_count)

right = dest->parent->ptr[dest->index+1];

else

return false;

if (right->keys_count < T+1)

if (TransferFromRightNode(right)!=true)

return false;

        if (!dest->leaf){

        InsertPointer(dest,dest->keys_count+1,right->ptr[0]);

         ErasePointers(right,0,1);

        if (dest->ptr[dest->keys_count+1] != NULL){

          dest->ptr[dest->keys_count+1]->parent = dest;

          dest->ptr[dest->keys_count+1]->index = dest->keys_count+1;

         }

         InsertKey(dest,dest->parent->item[dest->index]);

         dest->keys_count++;

         right->parent->item[dest->index] = right->item[0];

        EraseKeys(right,0,1);

         right->keys_count--;

        } else{

                InsertKey(dest,right->item[0]);

        dest->keys_count++;

        right->parent->item[dest->index] = right->item[0];

        EraseKeys(right,0,1);

        right->keys_count--;

        }

return true;

}

 

 

template <class Data>

void CB_PLUS_Tree<Data>::EraseKeys(Node* node,short start, short count)

{

for (short i = start; i<node->keys_count; ++i){

if (i+count < node->keys_count)

node->item[i] = node->item[i+count];

else

node->item[i] = NULL;

}

}

 

 

 

template <class Data>

void CB_PLUS_Tree<Data>::ErasePointers(Node* node,short start, short count)

{

for (short i = start; i<node->keys_count+1; ++i){

if (i+count < node->keys_count+1){

node->ptr[i] = node->ptr[i+count];

if (node->ptr[i]!=NULL){

node->ptr[i]->index = i;

}

}

else

node->ptr[i] = NULL;

}

}

 

 

 

template <class Data>

typename CB_PLUS_Tree<Data>::Node* CB_PLUS_Tree<Data>::ReplaceKey(Node* node, short & index)

{

if (node->leaf == true){

return node;

}

Node* left = node->ptr[index];

Node* right = node->ptr[index+1];

Node* leaf = NULL;

if (left->keys_count > right->keys_count){

node->item[index] = left->item[left->keys_count-1];

index = left->keys_count-1;

leaf = ReplaceKey(left,index);

}

else{

node->item[index] = right->item[0];

index = 0;

leaf = ReplaceKey(right,index);

}

return leaf;

}

 

 

 

template <class Data>

void CB_PLUS_Tree<Data>::AssignLevels(Node* node)

{

if (node->parent != NULL)

node->level = node->parent->level + 1;

    else

        node->level = 0;

if (node->leaf == true)

return;

for (short i=0; i<=node->keys_count; ++i){

AssignLevels(node->ptr[i]);

}

}

//------------------------------------------------------------------------------

 

template <class Data>

short CB_PLUS_Tree<Data>::AssignWidths(Node* node)

{

node->width = 0;

if (node->leaf == true){

node->width = 1;

return 1;

}

for (short i=0; i<=node->keys_count; ++i){

node->width += AssignWidths(node->ptr[i]);

}

return node->width;

}

//------------------------------------------------------------------------------

 

template <class Data>

void CB_PLUS_Tree<Data>::AssignIndents(Node* node)

{

if (node->index == 0)

if (node == root)

node->indent = 0;

else

node->indent = node->parent->indent;

else

node->indent = node->parent->ptr[node->index-1]->indent + node->parent->ptr[node->index-1]->width;

if (node->leaf == true)

return;

for (short i=0; i<=node->keys_count; ++i){

AssignIndents(node->ptr[i]);

}

}

//------------------------------------------------------------------------------

 

 

#pragma hdrstop

 

#endif