bplus_tree.cpp

  #include<stdio.h>

    #include<conio.h>

    #include<iostream>

    using namespace std;

    struct B+TreeNode

    {

        int *data;

        B+TreeNode **child_ptr;

        bool leaf;

        int n;

    }*root = NULL, *np = NULL, *x = NULL;

    B+TreeNode * init()

    {

        int i;

        np = new B+TreeNode;

        np->data = new int[5];

        np->child_ptr = new B+TreeNode *[6];

        np->leaf = true;

        np->n = 0;

        for (i = 0; i < 6; i++)

        {

            np->child_ptr[i] = NULL;

        }

        return np;

    }

    void traverse(B+TreeNode *p)

    {

        cout<<endl;

        int i;

        for (i = 0; i < p->n; i++)

        {

            if (p->leaf == false)

            {

                traverse(p->child_ptr[i]);

            }

            cout << " " << p->data[i];

        } 

        if (p->leaf == false)

        {

            traverse(p->child_ptr[i]);

        }

        cout<<endl;

    }

    void sort(int *p, int n)

    {

        int i, j, temp;

        for (i = 0; i < n; i++)

        {

            for (j = i; j <= n; j++)

            {

                if (p[i] > p[j])

                {

                    temp = p[i];

                    p[i] = p[j];

                    p[j] = temp;

                }

            }

        }

    }

    int split_child(B+TreeNode *x, int i)

    {

        int j, mid;

        B+TreeNode *np1, *np3, *y;

        np3 = init();

        np3->leaf = true;

        if (i == -1)

        {

            mid = x->data[2];

            x->data[2] = 0;

            x->n--;

            np1 = init();

            np1->leaf = false;

            x->leaf = true;

            for (j = 3; j < 5; j++)

            {

                np3->data[j - 3] = x->data[j];

                np3->child_ptr[j - 3] = x->child_ptr[j];

                np3->n++;

                x->data[j] = 0;

                x->n--;

            }

            for(j = 0; j < 6; j++)

            {

                x->child_ptr[j] = NULL;

            }

            np1->data[0] = mid;

            np1->child_ptr[np1->n] = x;

            np1->child_ptr[np1->n + 1] = np3;

            np1->n++;

            root = np1;

        }

        else

        {

            y = x->child_ptr[i];

            mid = y->data[2];

            y->data[2] = 0;

            y->n--;

            for (j = 3; j < 5; j++)

            {

                np3->data[j - 3] = y->data[j];

                np3->n++;

                y->data[j] = 0;

                y->n--;

            }

            x->child_ptr[i + 1] = y;

            x->child_ptr[i + 1] = np3; 

        }

        return mid;

    }

    void insert(int a)

    {

        int i, temp;

        x = root;

        if (x == NULL)

        {

            root = init();

            x = root;

        }

        else

        {

            if (x->leaf == true && x->n == 5)

            {

                temp = split_child(x, -1);

                x = root;

                for (i = 0; i < (x->n); i++)

                {

                    if ((a > x->data[i]) && (a < x->data[i + 1]))

                    {

                        i++;

                        break;

                    }

                    else if (a < x->data[0])

                    {

                        break;

                    }

                    else

                    {

                        continue;

                    }

                }

                x = x->child_ptr[i];

            }

            else

            {

                while (x->leaf == false)

                {

                for (i = 0; i < (x->n); i++)

                {

                    if ((a > x->data[i]) && (a < x->data[i + 1]))

                    {

                        i++;

                        break;

                    }

                    else if (a < x->data[0])

                    {

                        break;

                    }

                    else

                    {

                        continue;

                    }

                }

                    if ((x->child_ptr[i])->n == 5)

                    {

                        temp = split_child(x, i);

                        x->data[x->n] = temp;

                        x->n++;

                        continue;

                    }

                    else

                    {

                        x = x->child_ptr[i];

                    }

                }

            }

        }

        x->data[x->n] = a;

        sort(x->data, x->n);

        x->n++;

    }

    int main()

    {

        int i, n, t;

        cout<<"enter the no of elements to be inserted\n";

        cin>>n;

        for(i = 0; i < n; i++)

        {

            cout<<"enter the element\n";

            cin>>t;

            insert(t);

        }

        cout<<"traversal of constructed tree\n";

        traverse(root);

        getch();

    }