реализация B-дерва

// b-tree.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdarg.h>




class B_tree
{
        public:
                B_tree ();                             //Конструктор "пустого" B-дерева
                B_tree (int amount,...);       //Конструктор B-дерева, состоящего из amount элементов
                //B_tree (const B_tree& b_tree);    //Конструктор копирования
                ~B_tree ();                          //Деструктор B-дерева
                void Add (int key,char fio[25],char dolgnost[30],int room,char grafic[15]);               //Добавление ключа key в структуру B-дерева
                bool Search (int key);          //Поиск ключа в B-дереве (true - найден, false - не найден)
                void Delete (int key);          //Удаление всех экземпляров ключа key в B-дереве, при отсутствии данного ключа структура остается без изменений
                void Print ();                       //Обход и вывод B-дерева на печать способом, используемым при составлении оглавления книг
       
        private:
                struct Page
                {
                        int RAmount;            //Фактическое число элементов на странице
                        Page *p0;               //Указатель на самого левого потомка страницы
                        struct Item
                        {
                                 char fio[25];
                                 char dolgnost[30];
                                 int room;
                                 char grafic[15];
                                int key;           //Значение одного ключа страницы
                                Page *p;        //Указатель на страницу-потомок
                                int count;        //Число экземпляров данного ключа, хранимых на странице
                        } key_pt[4];           //Массив, хранящий значения ключей страницы и указатели на потомков страницы
                } *root;                         //Указатель на корень B-дерева

                void search_add_key (char fio[25],char dolgnost[30],int room,char grafic[15],int key, Page *a, bool& grow, Page::Item& v);
                                                //Рекурсивная функция, выполняющая добавление ключа key в структуру B-дерева; a - указатель на страницу, grow - "B-дерево стало выше", v - передаваемый вверх элемент
                void print_b_tree (Page *a, int level);
                                                //Рекурсивная фунцкия, выполняющая печать B-дерева с уровня level
                bool search_key (int key, Page *a);
                                                //Рекурсивная функция, выполняющая поиск ключа в B-дереве (true - ключ найден, false - не найден)
                void delete_key (int key, Page *a, bool& smallsize);
                                                //Рекурсивная функция, выполняющая удаление ключа key из структуры B-дерева, a - указатель на страницу, smallsize - "страница a мала", требуется слияние страниц
                void del (int R, Page *a, Page *q, bool& smallsize);
                                                //Рекурсивная функция, выполняющая балансировку B-дерева после удаления ключа key из его структуры, при необходимости производит слияние страниц
                void fusion (Page *father, Page *son, int R, bool& smallsize);
                                                //Функция, выполняющая слияние страниц B-дерева, father - "страница отец", son - "страница-сын отца", на которой число элементов меньше допустимого, R - индек удаляемого из страницы-отца элемента, smallsize - "страница-отец мала"
                void destroy (Page *a);            //"Деструктор" вершины a B-дерева
                void copy (Page *a, Page *b);    //Рекурсивная функция, создающая копию b страницы B-дерева a
};

B_tree::B_tree()
{
        root = NULL;
}


B_tree::B_tree (int amount, ...)
{
        short i = 0;
        root = NULL;
        va_list key_vl;
        va_start (key_vl, amount);
        while ((key_vl != NULL) && (++i <= amount))
                Add (va_arg (key_vl, int),"","",0,"");
        va_end (key_vl);
}
/*
B_tree::B_tree (const B_tree& b_tree)
{
        root = new Page;
        if (b_tree.root != NULL)
                copy (b_tree.root, root);
        else
            root = NULL;
}
*/
void B_tree::copy (Page *a, Page *b)
{
        Page *p1, *p2, *p3, *p4, *p5;

        if (a != NULL)
        {
            b->RAmount = a->RAmount;
            for (int i=0; i < a->RAmount; i++)
            {
                    b->key_pt.key = a->key_pt.key;
                    b->key_pt.count = a->key_pt.count;
            }
            if ((a->RAmount >= 1) && (a->p0 != NULL))
            {
                    p1 = new Page;
                    p2 = new Page;
            }
            else
            {    
                    p1 = NULL;
                    p2 = NULL;
            }
            if ((a->RAmount >= 2) && (a->p0 != NULL))
                    p3 = new Page;
            else
                    p3 = NULL;
            if ((a->RAmount >= 3) && (a->p0 != NULL))
                    p4 = new Page;
            else
                    p4 = NULL;
            if ((a->RAmount == 4) && (a->p0 != NULL))
                    p5 = new Page;
            else
                    p5 = NULL;
            b->p0 = p1;
            b->key_pt[0].p = p2;
            b->key_pt[1].p = p3;
            b->key_pt[2].p = p4;
            b->key_pt[3].p = p5;

            if (a->RAmount >= 1)
            {
                    copy (a->p0, p1);
                    copy (a->key_pt[0].p, p2);
            }
            if (a->RAmount >= 2)
                    copy (a->key_pt[1].p, p3);
            if (a->RAmount == 3)
                    copy (a->key_pt[2].p, p4);
            if (a->RAmount == 4)
                    copy (a->key_pt[3].p, p5);
        }
}

B_tree::~B_tree()
{
        destroy (root);
        root = NULL;
}

void B_tree::destroy (Page *a)
{
        Page *p1, *p2, *p3, *p4, *p5;

        if (a != NULL)
        {
            if (a->RAmount >= 1)
            {
                    p1 = a->p0;
                    p2 = a->key_pt[0].p;
            }
            else
            {
                    p1 = NULL;
                    p2 = NULL;
            }
            if (a->RAmount >= 2)
                    p3 = a->key_pt[1].p;
            else
                    p3 = NULL;
            if (a->RAmount >= 3)
                    p4 = a->key_pt[2].p;
            else
                    p4 = NULL;
            if (a->RAmount == 4)
                 p5 = a->key_pt[3].p;
            else
                    p5 = NULL;
            delete a;
       
        destroy (p1);
        destroy (p2);
        destroy (p3);
        destroy (p4);
        destroy (p5);
        }
}

void B_tree::Add (int key,char fio[25],char dolgnost[30],int room,char grafic[15])
{
        bool grow;
        Page::Item u;
        Page *bufer_root;
        search_add_key (fio,dolgnost,room,grafic,key, root, grow, u);
        if (grow == true)
        {
                bufer_root = root;
                root = new Page;
                root->p0 = NULL;
                root->key_pt[0].p = NULL;
                root->key_pt[1].p = NULL;
                root->key_pt[2].p = NULL;
                root->key_pt[3].p = NULL;
                root->RAmount = 1;
                root->p0 = bufer_root;
                root->key_pt[0] = u;
        }
}

void B_tree::search_add_key (char fio[25],char dolgnost[30],int room,char grafic[15],int key, Page *a, bool& grow, Page::Item& v)
{
        short i, L, R;
        Page *b;
        Page::Item u;
       
        if (a == NULL)
        {
                grow = true;
                v.key = key;
                strcpy(v.fio,fio);
                strcpy(v.dolgnost,dolgnost);
                strcpy(v.grafic,grafic);
                v.room=room;
                strcpy(v.dolgnost,dolgnost);
               
                v.p = NULL;
                v.count = 1;
        }
        else
        {
                L = 0;
                R = a->RAmount;
                while (L < R)
                {
                        i = (L+R)/2;
                        if (a->key_pt.key <= key)
                                L = i+1;
                        else
                                R = i;
                }
                R = R-1;
                if ((R >= 0) && (a->key_pt[R].key == key))
                        a->key_pt[R].count++;
                else
                {
                        if (R == -1)
                                search_add_key (fio,dolgnost,room,grafic,key, a->p0, grow, u);
                        else
                                search_add_key (fio,dolgnost,room,grafic,key, a->key_pt[R].p, grow, u);
                        if (grow == true)
                        {
                                if (a->RAmount < 4)
                                {
                                        grow = false;
                                        a->RAmount++;
                                        for (i = a->RAmount-1; i >= R+2; i--)
                                                a->key_pt = a->key_pt[i-1];
                                        a->key_pt[R+1] = u;
                                }
                                else
                                {
                                        b = new Page;
                                        b->p0 = NULL;
                                        b->key_pt[0].p = NULL;
                                        b->key_pt[1].p = NULL;
                                        b->key_pt[2].p = NULL;
                                        b->key_pt[3].p = NULL;
                                        if (R <= 1)
                                        {
                                                if (R == 1)
                                                        v = u;
                                                else
                                                {
                                                        v = a->key_pt[1];
                                                        for (i=1; i>=R+1; i--)
                                                                a->key_pt = a->key_pt[i-1];
                                                        a->key_pt[R+1] = u;
                                                }
                                                for (i=0; i<=1; i++)
                                                        b->key_pt = a->key_pt[i+2];
                                        }
                                        else
                                        {
                                                R = R-2;
                                                v = a->key_pt[2];
                                                for (i=0; i<=R-1; i++)
                                                        b->key_pt = a->key_pt[i+3];
                                                b->key_pt[R] = u;
                                                for (i=R+1; i<=1; i++)
                                                        b->key_pt = a->key_pt[i+2];
                                        }
                                        a->RAmount = 2;
                                        b->RAmount = 2;
                                        b->p0 = v.p;
                                        v.p = b;
                                }
                        }
                }
        }
}

bool B_tree::Search (int key)
{
        return (search_key (key, root));
}

bool B_tree::search_key (int key, Page *a)
{
        short i, L, R;
   
        if (a == NULL)
                return (false);
        else
        {
                L = 0;
                R = a->RAmount;
                while (L < R)
                {
                        i = (L+R)/2;
                        if (a->key_pt.key <= key)
                                L = i+1;
                        else
                                R = i;
                }
                R = R-1;
                if ((R >= 0) && (a->key_pt[R].key == key))
                        return (true);
                else
                        if (R == -1)
                                search_key (key, a->p0);
                        else
                                search_key (key, a->key_pt[R].p);
        }                        
return true;
}

void B_tree::Delete (int key)
{        
        bool smallsize;
        Page *bufer_root;
        delete_key (key, root, smallsize);
        if (smallsize == true)
        {
                if (root->RAmount == 0)
                {
                        bufer_root = root;
                        root = bufer_root->p0;
                        delete bufer_root;
                }
        }
}

void B_tree::delete_key (int key, Page *a, bool& smallsize)
{
        short i, L, R;
        Page *q;

        if (a == NULL)
                smallsize = false;
        else
        {
                L = 0;
                R = a->RAmount;
                while (L < R)
                {
                        i = (L+R)/2;
                        if (a->key_pt.key < key)
                                L = i+1;
                        else
                                R = i;
                }
                if (R == 0)
                        q = a->p0;
                else
                        q = a->key_pt[R-1].p;
                if ((R <= a->RAmount-1) && (a->key_pt[R].key == key))  
                {
                        if (q == NULL)
                        {
                            a->RAmount--;
                            smallsize = (a->RAmount < 2);
                            for (i=R; i<a->RAmount; i++)
                                    a->key_pt = a->key_pt[i+1];
                        }
                        else
                        {
                                del(R, a, q, smallsize);
                                if (smallsize == true)
                                        fusion (a, q, R-1, smallsize);
                        }
                }
                else
                {
                        delete_key (key, q, smallsize);
                        if (smallsize == true)
                                fusion (a, q, R-1, smallsize);
                }
        }
}

void B_tree::del (int R, Page *a, Page *q, bool& smallsize)
{
        Page *b;

        b = q->key_pt[q->RAmount-1].p;
        if (b != NULL)
        {
                del (R, a, b, smallsize);
                if (smallsize == true)
                        fusion (q, b, q->RAmount-1, smallsize);
        }
        else
        {
            q->key_pt[q->RAmount-1].p = a->key_pt[R].p;
            a->key_pt[R] = q->key_pt[q->RAmount-1];
            q->RAmount--;
            smallsize = (q->RAmount < 2);
        }
}

void B_tree::fusion (Page *father, Page *son, int R, bool& smallsize)
{
        Page *b;
        int i, k, RAb, RAfather;

        RAfather = father->RAmount;
        if (R < RAfather-1)
        {
                R++;
                b = father->key_pt[R].p;
                RAb = b->RAmount;
                k = (RAb-2+1)/2;
                son->key_pt[1] = father->key_pt[R];
                son->key_pt[1].p = b->p0;
                if (k > 0)
                {
                        for (i=0; i <= k-1; i++)
                                son->key_pt[i+2] = b->key_pt;
                        father->key_pt[R] = b->key_pt[k];
                        father->key_pt[R].p = b;
                        b->p0 = b->key_pt[k].p;
                        RAb = RAb-k-1;
                        for (i=0; i < RAb; i++)
                                b->key_pt = b->key_pt[i+k+1];
                        b->RAmount = RAb;
                        son->RAmount = 2-1+(k+1);
                        smallsize = false;
                }
                else    
                {
                        for (i=0; i < 2; i++)
                                son->key_pt[i+2] = b->key_pt;
                        for (i=R; i < RAfather-1; i++)
                                father->key_pt = father->key_pt[i+1];
                        son->RAmount = 4;
                        father->RAmount--;
                        smallsize = (father->RAmount < 2);
                        delete b;
                }
        }
        else
        {
                if (R == 0)
                        b = father->p0;
                else
                        b = father->key_pt[R-1].p;
                RAb = b->RAmount+1;
                k = (RAb-2)/2;
                if (k > 0)
                {
                        son->key_pt[k] = son->key_pt[0];
                        son->key_pt[k-1] = father->key_pt[R];
                        son->key_pt[k-1].p = son->p0;
                        RAb = RAb-k-1;
                        son->p0 = b->key_pt[RAb].p;
                        father->key_pt[R] = b->key_pt[RAb];
                        father->key_pt[R].p = son;
                        b->RAmount--;
                        son->RAmount = 2-1+k;
                        smallsize = false;
                }
                else    
                {
                    b->key_pt[RAb-1] = father->key_pt[R];
                    b->key_pt[RAb-1].p = son->p0;
                    b->key_pt[RAb] = son->key_pt[0];
                    b->RAmount = 4;
                    father->RAmount--;        
                    smallsize = (father->RAmount < 2);  
                    delete son;
                }
        }
}
void B_tree::Print ()
{
        print_b_tree (root, 0);        
}


void B_tree::print_b_tree (Page *a, int level)
{
        using namespace std;
        short i;

        if (a != NULL)
        {
                for (i=0; i<level; i++)
                        cout << "---";
                for (i=0; i<a->RAmount; i++)
                {
                        cout << a->key_pt.key; //<< "(" <<a->key_pt.count << ")";
                        if (i != a->RAmount-1)
                                cout << ", ";
                }
                cout << endl;
                print_b_tree (a->p0, level+1);
                for (i=0; i<a->RAmount; i++)
                        print_b_tree (a->key_pt.p, level+1);
        }
}


B_tree *tree;
int _tmain(int argc, _TCHAR* argv[])
{
tree=new (B_tree);
B_tree (2);  

    for(;;)
    {
        int i;
        std::cout<<"MENU: \n 1 - Add list \n 2 - Print tree \n\n";
        std::cin>>i;
        switch(i)
        {
        case 1:
char fio[25],dolgnost[30],grafic[15];
int room;



            std::cout<<"Key:";
            std::cin>>i;
            std::cout<<"FIO:";
            std::cin>>fio;

            std::cout<<"Dolgnost:";
            std::cin>>dolgnost;

            std::cout<<"Grafic:";
            std::cin>>grafic;

            std::cout<<"Room:";
            std::cin>>room;

            tree->Add(i,fio,dolgnost,room,grafic);
            break;

        case 2:
            tree->Print();
            break;
        }
    }

    return 0;
}