How To Create B-Tree Of Order M by Using Reactive Method

 ///Order Must Be Odd

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

struct Node

{

    int order;///contains order

    vector<int> key;///to store keys

    vector<Node*> child;///to store child

    bool isLeaf;///flag to indicate whether the node is leaf node or not.if the node is leaf then no key in that node will have child

    ///but if node is not leaf then all the keys will have left and right child

    Node(int order)

    {

        this->order=order;

        isLeaf=false;

    }

    bool isFull()///to check node is full or not

    {

        return(key.size()==(order-1));

    }

};

int divide(Node *root,Node *extra,int *mid_index)///function to divide root by mid value and returns mid value,stores half values in root and half inside extra node

{

    *mid_index=(root->key.size())/2;///storing mid-index

    int median=root->key.at(*mid_index);

    for(int i=(*mid_index+1);i<root->key.size();i++)///copying right half values to extra node

    {

        extra->key.push_back(root->key.at(i));

    }

    for(int i=root->key.size()-1;i>=(*mid_index);i--)///popping right half and mid value from root

    {

        root->key.pop_back();

    }

    return median;

}

Node* split_leaf(Node *root,Node *parent,int key,int order)///function to split leaf node and returns address of root

{

    int i,median,mid_index;

    root->key.push_back(key);///first insert the key then split

    sort(root->key.begin(),root->key.end());

    if(parent==root)///split parent

    {

        Node *ex1=new Node(order),*ex2=new Node(order);///here we will need two node one for parent and one for second child

        median=divide(root,ex1,&mid_index);

        ex2->key.push_back(median);

        ex2->child.push_back(root);

        ex2->child.push_back(ex1);

        if(root->isLeaf==true)

            ex1->isLeaf=true;

        else

            ex1->isLeaf=false;

        ex2->isLeaf=false;

        root=ex2;

    }

    else///if not parent

    {

        Node *ex=new Node(order);///here we will need only one node to store second child

        median=divide(root,ex,&mid_index);

        for(i=0;i<parent->key.size();i++)

        {

            if(median>parent->key.at(i))

                continue;

            else

                break;

        }

        parent->key.insert(parent->key.begin()+i,median);

        parent->child.at(i)=root;

        parent->child.insert(parent->child.begin()+i+1,ex);

        if(root->isLeaf==true)

            ex->isLeaf=true;

        else

            ex->isLeaf=false;

    }

    return root;

}

Node* split_non_leaf(Node *root,Node *parent,int order)///function to split non leaf node

{

    int i,median,mid_index;

    if(parent==root)

    {

        Node *ex1=new Node(order);

        Node *ex2=new Node(order);

        median=divide(root,ex1,&mid_index);

        ex2->key.push_back(median);

        ex2->child.push_back(root);

        ex2->child.push_back(ex1);

        for(int j=mid_index+1;j<root->child.size();j++)

            ex1->child.push_back(root->child.at(j));

        for(int j=root->child.size()-1;j>mid_index;j--)

            root->child.pop_back();

        if(root->isLeaf==true)

            ex1->isLeaf=true;

        else

            ex1->isLeaf=false;

        ex2->isLeaf=false;

        root=ex2;

    }

    else

    {

        Node *ex=new Node(order);

        median=divide(root,ex,&mid_index);

        for(i=0;i<parent->key.size();i++)

        {

            if(median>parent->key.at(i))

                continue;

            else

                break;

        }

        parent->key.insert(parent->key.begin()+i,median);

        parent->child.at(i)=root;

        parent->child.insert(parent->child.begin()+i+1,ex);

        for(int j=mid_index+1;j<root->child.size();j++)

            ex->child.push_back(root->child.at(j));

        for(int j=root->child.size()-1;j>mid_index;j--)

            root->child.pop_back();

        if(root->isLeaf==true)

            ex->isLeaf=true;

        else

            ex->isLeaf=false;

    }

    return root;

}

Node* insert_key(Node *root,int key,int order,Node *parent)///returns address of root of tree in which key is inserted

{

    if(root==NULL)///for empty tree

    {

        root=new Node(order);///creating root of tree...

        root->key.push_back(key);

        root->isLeaf=true;

    }

    else if(root->isLeaf==true)///if current node is leaf then we found out the node in which we have to insert the key.

    {

        if(root->isFull()==false)///if not full then just insert the key

        {

            root->key.push_back(key);

            sort(root->key.begin(),root->key.end());///after inserting we are sorting it by use of sort(),becz of laziness

        }

        else if(root->isFull()==true)///if current node is full and it is leaf then we are calling split_leaf()

        {

            root=split_leaf(root,parent,key,order);///it will return address of root

        }

    }

    else///here we are searching the node where we have to go next...

    {

        int i=0;

        while(i<root->key.size())///finding correct position

        {

            if(key<=root->key.at(i))///here we are going on left subtree of key[i]

            {

                root->child.at(i)=insert_key(root->child.at(i),key,order,root);///inserting key in left sub-tree

                if(root->key.size()==order)///after insertion if any key is promoted from child then we are checking if parent is become full or not

                    root=split_non_leaf(root,parent,order);///if parent becomes full we have to split it

                break;///after insertion we have to break the loop.

            }

            else if(key>root->key.at(i))///here we are going on right subtree of key[i] if following conditions satisfies else continue the loop

            {

                if((i==root->key.size()-1)||(key<root->key.at(i+1)))///if one of the condition is true then we go to right sub tree

                {

                    root->child.at(i+1)=insert_key(root->child.at(i+1),key,order,root);///inserting key in right sub-tree

                    if(root->key.size()==order)///after insertion if any key is promoted from child then we are checking if parent is become full or not

                        root=split_non_leaf(root,parent,order);///if parent becomes full we have to split it

                    break;///after insertion we have to break the loop.

                }

            }

            i++;///continue...

        }

    }

    return root;///at last we are returning updated root

}

void inorder_traversal(Node *root)

{

    if(root!=NULL)

    {

        int i=0;

        while(i<root->key.size())///for every key we have to do the same thing which we already done with BST.

        {

            if((i==0)&&(root->isLeaf==false))

                inorder_traversal(root->child.at(i));

            cout<<root->key.at(i)<<" ";

            if(root->isLeaf==false)

                inorder_traversal(root->child.at(i+1));

            i++;

        }

    }

}

int main()

{

  Node *root=NULL;

  root=insert_key(root,10,5,root);

  root=insert_key(root,5,5,root);

  root=insert_key(root,30,5,root);

  root=insert_key(root,40,5,root);

  root=insert_key(root,2,5,root);

  root=insert_key(root,35,5,root);

  root=insert_key(root,45,5,root);

  root=insert_key(root,15,5,root);

  root=insert_key(root,0,5,root);

  root=insert_key(root,50,5,root);

  root=insert_key(root,18,5,root);

  root=insert_key(root,55,5,root);

  root=insert_key(root,60,5,root);

  root=insert_key(root,65,5,root);

  root=insert_key(root,70,5,root);

  inorder_traversal(root);

}