M-way Search Tree

//B-Tree Insertion;
#include<stdio.h>
#include<malloc.h>

 int m=5,number;

 struct mtree
{
    int data;
    struct mtree *left,*right,*leftchild,*rightchild,*parent;
}*p=NULL,*q=NULL,*tmp=NULL,*head=NULL,*t1=NULL,*t2=NULL;

 struct level
{
    int num;
    struct mtree *link;
    struct level *left,*right;
}*first=NULL,*last=NULL,*node=NULL;

 pushup()
{

      //checking if node has >m-1 elements;
    t1=p;
    int i=0;
    while(t1!=NULL)
    {
        i++;
        t1=t1->right;
    }
    if(i>(m-1))
    {

         tmp=p;
        int j;
        for(j=0;j<((m/2));j++)
            tmp=tmp->right;

        t1=tmp->left;
        t2=tmp->right;

         q=p->parent;

            p->parent=tmp;
            t1->right=NULL;
            t2->left=NULL;
            t2->parent=tmp;

             tmp->leftchild=p;
            tmp->rightchild=t2;
        if(q==NULL)
        {

             tmp->left=NULL;
            tmp->right=NULL;
            head=tmp;
        }
        else{

             if(q->leftchild==p)
            {
                tmp->left=q->left;
                tmp->right=q;
                if(q->left!=NULL)
                    q->left->right=tmp;
                else{
                    if(q->parent==NULL)
                    {
                        head=tmp;
                    }
                    else if(q->parent->leftchild==q)
                        {
                            q->parent->leftchild=tmp;
                            if(q->parent->left!=NULL)
                                q->parent->left->rightchild=tmp;
                        }
                    else{
                        {
                            q->parent->rightchild=tmp;
                            if(q->parent->right!=NULL)
                                q->parent->right->leftchild=tmp;
                        }
                    }
                }
                q->left=tmp;
                if(tmp->right!=NULL)
                    tmp->right->leftchild=t2;

             }
            else{
                tmp->right=q->right;
                tmp->left=q;
                if(q->right!=NULL)
                    q->right->left=tmp;
                q->right=tmp;
                if(tmp->right!=NULL)
                    tmp->right->leftchild=t2;
            }
        p=q;
        while(p->left!=NULL)
            p=p->left;

         pushup();//will push middle element to parentent node;
        }
    }
}

 locate(int number)
{
    p=head;
    q=p;
    while(p->leftchild!=NULL || p->rightchild!=NULL)
    {
        if(number<p->data)
        {
            q=p;
            p=p->leftchild;
        }
        else if(p->right!=NULL)
            p=p->right;
        else
        {
            q=p;
            p=p->rightchild;
        }
    }

 }

 insert()
{
    int i=0;
    printf("\nEnter the number: ");
    scanf("%d",&number);

     //entry to a new node;
    tmp=malloc(sizeof(struct mtree));
    tmp->data=number;
    tmp->left=NULL;
    tmp->right=NULL;
    tmp->leftchild=NULL;
    tmp->rightchild=NULL;
    tmp->parent=NULL;

     p=head;
    if(p==NULL)
    {
        head=tmp;
        return 0;
    }
    //find location of node;
    locate(number);
        //insert the tmp node in the set node;
    if(tmp->data<p->data)
    {
        p->left=tmp;
        tmp->right=p;
        tmp->rightchild=p->leftchild;
        tmp->parent=p->parent;

         if(p->parent==NULL)
            head=tmp;
        else
        {
            if(p->parent->leftchild==p)
            {
                p->parent->leftchild=tmp;
                if(p->parent->left!=NULL)
                    p->parent->left->rightchild=tmp;
                p->parent=NULL;
            }
            else if(p->parent->rightchild==p)
            {
                p->parent->rightchild=tmp;
                if(p->parent->right!=NULL)
                    p->parent->right->leftchild=tmp;
                p->parent=NULL;
            }
        }
            p=tmp;
    }
    else
    {
        t1=p;
        t2=p;
        while(t1!=NULL)
        {
            if(number>=t1->data)

             {
                t2=t1;
                t1=t1->right;
            }
            else
                break;
        }
        if(t1==NULL)
        {
            t2->right=tmp;
            tmp->left=t2;
            tmp->leftchild=t2->rightchild;
        }
        else{
            t2->right=tmp;
            tmp->left=t2;
            tmp->leftchild=t2->rightchild;
            t1->left=tmp;
            tmp->right=t1;
            tmp->rightchild=t1->leftchild;
        }
    }//node 1st entry;

   pushup();//will push middle element to parent node;

 }

 push(struct mtree *temp,int global)
{
    if(temp!=NULL)
    {
        node=malloc(sizeof(struct level));
        node->num=global;
        node->link=temp;
        node->left=NULL;
        node->right=NULL;

         if(first==NULL && last==NULL)
        {
            first=node;
            last=node;
        }
        else{
            node->left=last;
            last->right=node;
            last=node;
        }
    }
}

 pop()
{
    if(first!=NULL)
    {
        node=first;
        first=first->right;
        if(first==NULL)
            last=NULL;
        else
            first->left=NULL;

         display(node->link,node->num);

     }
}

 display(struct mtree *temp,int global)
{
    printf("\nLevel-%d\n",global);
    while(temp!=NULL)
    {
        printf("%d , ",temp->data);
        push(temp->leftchild,(global+1));
        if(temp->right==NULL)
            push(temp->rightchild,(global+1));
        temp=temp->right;

         if(temp==NULL)
            pop();
    }

 }

 main()
{
    printf("\nEnter the value of m in m-way search tree:");
    scanf("%d",&m);
    int ch=1;
    while(ch==1)
    {
        insert();
        display(head,1);

         printf("\nEnter 1-insert,0-exit: ");
        scanf("%d",&ch);
    }

 }



OUTPUT:-


Enter the value of m in m-way search tree:5

Enter the number: 50

Level-1
50 ,
Enter 1-insert,0-exit: 1

Enter the number: 60

Level-1
50 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 55

Level-1
50 , 55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 40

Level-1
40 , 50 , 55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 30

Level-1
50 ,
Level-2
30 , 40 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 10

Level-1
50 ,
Level-2
10 , 30 , 40 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 20

Level-1
50 ,
Level-2
10 , 20 , 30 , 40 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 5

Level-1
20 , 50 ,
Level-2
5 , 10 ,
Level-2
30 , 40 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 41

Level-1
20 , 50 ,
Level-2
5 , 10 ,
Level-2
30 , 40 , 41 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 42

Level-1
20 , 50 ,
Level-2
5 , 10 ,
Level-2
30 , 40 , 41 , 42 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 43

Level-1
20 , 41 , 50 ,
Level-2
5 , 10 ,
Level-2
30 , 40 ,
Level-2
42 , 43 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 4

Level-1
20 , 41 , 50 ,
Level-2
4 , 5 , 10 ,
Level-2
30 , 40 ,
Level-2
42 , 43 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 3

Level-1
20 , 41 , 50 ,
Level-2
3 , 4 , 5 , 10 ,
Level-2
30 , 40 ,
Level-2
42 , 43 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 2

Level-1
4 , 20 , 41 , 50 ,
Level-2
2 , 3 ,
Level-2
5 , 10 ,
Level-2
30 , 40 ,
Level-2
42 , 43 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 11

Level-1
4 , 20 , 41 , 50 ,
Level-2
2 , 3 ,
Level-2
5 , 10 , 11 ,
Level-2
30 , 40 ,
Level-2
42 , 43 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 12

Level-1
4 , 20 , 41 , 50 ,
Level-2
2 , 3 ,
Level-2
5 , 10 , 11 , 12 ,
Level-2
30 , 40 ,
Level-2
42 , 43 ,
Level-2
55 , 60 ,
Enter 1-insert,0-exit: 1

Enter the number: 13

Level-1
20 ,
Level-2
4 , 11 ,
Level-2
41 , 50 ,
Level-3
2 , 3 ,
Level-3
5 , 10 ,
Level-3
12 , 13 ,
Level-3
30 , 40 ,
Level-3
42 , 43 ,
Level-3
55 , 60 ,
Enter 1-insert,0-exit: 0

Process returned 0 (0x0)   execution time : 153.235 s


Posted by