C++ program to implement B-tree

Here is C++ program to implement B-tree of order 5.

C++ program to implement B-tree of order 5

#include<iostream>
using namespace std;
#define MAX 5
struct tree_node
{
    int count;
    int data[MAX];
    tree_node *pt[MAX+1];
};
class b_tree
{
    int item;
    tree_node *root,*suc;
    void split(tree_node *,tree_node *);
    tree_node* create();
    void put_data(tree_node*,int);
    void replace_left(tree_node*,tree_node*);
    void replace_right(tree_node*,tree_node*);
    void merge(tree_node *,tree_node *);
public:
    b_tree()
    {
        root=NULL;
        suc=NULL;
    }
    void getdata();
    void insert(tree_node *,tree_node *);
    void delete_node(tree_node**,tree_node*);
    void search();
    void display(tree_node *);
    tree_node* getroot()
    {
        return root;
    }
};
tree_node* b_tree::create()
{
    tree_node *ne;
    ne=new tree_node;
    ne->count=0;
    for(int i=0;i<=MAX;i++)
        ne->pt[i]=NULL;
    return ne;
}
void b_tree::getdata()
{
    cout<<"Enter the element ";
    cin>>item;
}
void b_tree::put_data(tree_node *temp,int item)
{
    if(item>temp->data[temp->count-1])
        temp->data[temp->count]=item;
    else
    {
        for(int i=0;i<temp->count;i++)
        {
            if(item<temp->data[i])
            {
                for(int j=temp->count;j>i;j--)
                    temp->data[j]=temp->data[j-1];
                temp->data[i]=item;
                i=6;
                break;
            }
        }
    }
    ++temp->count;
}
void b_tree::split(tree_node *parent,tree_node *temp)
{
    int flag=1;
    if(temp==root)
    {
        root=create();
        root->data[0]=temp->data[2];
        root->count++;
        parent=root;
        parent->pt[0]=temp;
        flag=0;
    }
    for(int y=0;y<=parent->count;y++)
    {
            if(parent->pt[y]==temp)
            {
                for(int i=parent->count+1;i>y+1;i--)
                     parent->pt[i]=parent->pt[i-1];
                parent->pt[y+1]=create();
                for(int z=0;z<3;z++)
                    (parent->pt[y+1])->pt[z]=temp->pt[z+3];
                for(int z=3;z<6;z++)
                    temp->pt[z]=NULL;
                temp->count=(parent->pt[y+1])->count=2;
                (parent->pt[y+1])->data[0]=temp->data[3];
                (parent->pt[y+1])->data[1]=temp->data[4];
                if(flag)
                    put_data(parent,temp->data[2]);
            }
        }
}
void b_tree::replace_left(tree_node *parent,tree_node *temp)
{
    tree_node *temp1;
    for(int i=0;i<parent->count+1;i++)
    {
        if(parent->pt[i]==temp)
        {
            temp1=parent->pt[i-1];
            temp->data[1]=temp->data[0];
            temp->data[0]=parent->data[i-1];
            parent->data[i-1]=temp1->data[temp1->count-1];
            temp->pt[2]=temp->pt[1];
            temp->pt[1]=temp->pt[0];
            temp->pt[0]=temp1->pt[temp1->count];
            temp1->count--;
            temp->count++;
            break;
        }
    }
}
void b_tree::replace_right(tree_node *parent,tree_node *temp)
{
    tree_node *temp1;
    for(int i=0;i<parent->count+1;i++)
    {
        if(parent->pt[i]==temp)
        {
            temp1=parent->pt[i+1];
            temp->data[0]=parent->data[i];
            parent->data[i]=temp1->data[0];
            temp->pt[2]=temp1->pt[0];
            for(int y=0;y<temp->count-1;y++)
            {
                temp1->data[y]=temp1->data[y+1];
                temp1->pt[y]=temp1->pt[y+1];
            }
            temp1->pt[temp1->count-1]=temp1->pt[temp1->count];
            temp1->count--;
            temp->count++;
            break;
        }
    }
}
void b_tree::merge(tree_node *parent,tree_node *temp)
{
    tree_node *temp1;
    for(int i=0;i<=parent->count;i++)
    {
        if(parent->pt[i]==temp)
        {
            if(i>0)
            {
                temp1=parent->pt[i-1];
                temp1->data[2]=parent->data[i-1];
                temp1->data[3]=temp->data[0];
                temp1->pt[3]=temp->pt[0];
                temp1->pt[4]=temp->pt[1];
                for(int y=i-1;y<parent->count;y++)
                {
                    parent->data[y]=parent->data[y+1];
                    parent->pt[y+1]=parent->pt[y+2];
                }
                delete temp;
                parent->count--;
                temp1->count=4;
            }
            else
            {
                parent->count--;
                temp1=parent->pt[i+1];
                temp->data[1]=parent->data[i];
                temp->data[2]=temp1->data[0];
                temp->data[3]=temp1->data[1];
                temp->pt[2]=temp1->pt[0];
                temp->pt[3]=temp1->pt[1];
                temp->pt[4]=temp1->pt[2];
                delete temp1;
                for(int y=i;y<parent->count;y++)
                {
                    parent->data[y]=parent->data[y+1];
                    parent->pt[y+1]=parent->pt[y+2];
                }
                temp->count=4;
            }
            break;
        }
    }
}
void b_tree::insert(tree_node *parent,tree_node *temp)
{
    if(temp==NULL)
    {
        temp=root=create();
        temp->data[0]=item;
        temp->count++;
    }
    else if(temp->pt[0]==NULL)
    {
        for(int i=0;i<temp->count;i++)
        {
            if(temp->data[i]==item)
            {
                cout<<"Duplicate values cannot be inserted\n";
                return;
            }
        }
        put_data(temp,item);
    }
    else if(item>temp->data[temp->count-1])
        insert(temp,temp->pt[temp->count]);
    else
    {
        for(int i=0;i<temp->count;i++)
            if(item<temp->data[i])
            {
                insert(temp,temp->pt[i]);
                break;
            }
    }
    if(temp->count>MAX-1)
        split(parent,temp);
}
void b_tree::delete_node(tree_node **parent,tree_node *temp)
{
    if(temp==NULL)
    {
         cout<<"Element not found\n";
         return;
    }
    if(item>temp->data[temp->count-1])
        delete_node(&temp,temp->pt[temp->count]);
    else if(temp->pt[0]==NULL&&suc!=NULL)
    {
        for(int i=0;i<suc->count;i++)
        {
            if(suc->data[i]==item)
            {
                suc->data[i]=temp->data[0];
                temp->count--;
                for(int z=i;z<temp->count;z++)
                        temp->data[z]=temp->data[z+1];
                suc=NULL;
                break;
            }
        }
    }
    else if(suc!=NULL)
        delete_node(&temp,temp->pt[0]);
    else
    {
        for(int i=0;i<temp->count;i++)
        {
            if(temp->data[i]==item)
            {
                if(temp->pt[0]!=NULL)
                {
                    suc=temp;
                    delete_node(&temp,temp->pt[i+1]);
                }
                else
                {
                    temp->count--;
                    for(int z=i;z<temp->count;z++)
                        temp->data[z]=temp->data[z+1];
                }
                cout<<"Element successfully deleted\n";
                break;
            }
            else if(item<temp->data[i])
            {
                delete_node(&temp,temp->pt[i]);
                break;
            }
        }
    }
    if(temp==NULL)
        return;
    if(temp!=root&&temp->count<2)
    {
        for(int i=0;i<=(*parent)->count;i++)
        {
            if((*parent)->pt[i]==temp)
            {

                if(i>0&&((*parent)->pt[i-1])->count>2)
                    replace_left(*parent,temp);
                else if(i<(*parent)->count&&((*parent)->pt[i+1])->count>2)
                    replace_right((*parent),temp);
                else if((*parent)==root&&(*parent)->count==1)
                {
                    cout<<"root3";
                    merge(*parent,temp);
                    root=(*parent)->pt[0];
                    cout<<"teri";
                    delete *parent;
                    *parent=NULL;

                }
                else
                   merge(*parent,temp);
                break;

            }
        }

    }
}
void b_tree::search()
{
    tree_node *temp=root;
    int i=0;
    while(temp!=NULL)
    {
        if(i==temp->count||item<temp->data[i])
        {
            temp=temp->pt[i];
            i=0;
        }
        else if(temp->data[i]==item)
        {
            cout<<"Element is present "<<endl;
            return;
        }
        else if(item>temp->data[i])
            i++;
    }
    cout<<"Element is not present "<<i<<"\n";
}
void b_tree::display(tree_node *temp)
{
    if(temp==NULL)
        return;
    for(int i=0;i<temp->count;i++)
    {
        display(temp->pt[i]);
        cout<<temp->data[i]<<" ";
    }
    display(temp->pt[temp->count]);
}
int main()
{
    b_tree tree;
    int a,flag=1;
    while(flag)
    {
        cout<<"Main Menu\n\t1.) Insertion\n\t2.) Deletion\n\t3.) Search\n\t4.) Display\n\t5.) Exit";
        cout<<"\nEnter your choice ";
        cin>>a;
        switch(a)
        {
        case 1:
            tree.getdata();
            tree.insert(tree.getroot(),tree.getroot());
            break;
        case 2:
            tree.getdata();
            tree.delete_node(NULL,tree.getroot());
            break;
        case 3:
            tree.getdata();
            tree.search();
            break;
        case 4:
            tree.display(tree.getroot());
            cout<<endl;
            break;
        case 5:
            flag=0;
            break;
        default:
            cout<<"Wrong choice "<<endl;
        }
    }
}