# Insertion into a B-tree

B-tree, Insertion into a B-tree
Write a C program to perform the Insertion into a B-tree.

#define M 5
struct node
{
int n;
int keys[M-1];
struct node *p[M];
}
*root=NULL;
enum KeyStatus
Duplicate,SearchFailure,Success,InsertIt,LessKeys
};

1. Algorithm for search:
int searchPos(int key, int *key_arr, int n)
Step1: Declare int pos=0;
Step2:Repeat from step2 to step4
while (pos < n && key > key_arr[pos])
Step3: Increment the position
pos++;
Step4: return pos;
Step5: Stop

2. Algorithm for insert:
enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct
node**newnode)
Step1: Start
Step2: Declare struct node *newPtr, *lastPtr;
int pos, i, n,splitPos;
int newKey, lastKey;
enum KeyStatus value;
Step3: Check the pointer is Null upto step6
if (ptr == NULL)
Step4: Assign *newnode = NULL;
Step5: Assign *upKey = key;
Step6: return InsertIt;
Step7: n = ptr->n;
Step8: call subfunction search
pos = searchPos(key, ptr->keys, n);
Step9: Check & return
if (pos < n && key == ptr->keys[pos])
return Duplicate;
Step10: call sub function insert
value = ins(ptr->p[pos], key, &newKey, &newPtr);
Step11: check value not equal to insert & return
if (value != InsertIt)
return value;
Step12: Check n less than m-1 upto step 20
if (n < M - 1)
Step13: call subfunction searchposition
pos = searchPos(newKey, ptr->keys, n);
Step14: Repeat from step 14 to step 16
for (i=n; i>pos; i--)
Step15: ptr->keys[i] = ptr->keys[i-1];
Step16: ptr->p[i+1] = ptr->p[i];
Step17: ptr->keys[pos] = newKey;
Step18: ptr->p[pos+1] = newPtr;
Step19: ++ptr->n
Step20 return Success;
Step21:check if (pos == M – 1) upto step23 otherwise gotostep 24
Step22: lastKey = newKey;
Step23: lastPtr = newPtr;
Step24: else lastKey = ptr->keys[M-2];
Step25: lastPtr = ptr->p[M-1];
Step26 : repeat for (i=M-2; i>pos; i--)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
Step27: ptr->keys[pos] = newKey;
Step28: ptr->p[pos+1] = newPtr; }
Step29: splitPos = (M - 1)/2;
Step30: (*upKey) = ptr->keys[splitPos];
Step31:(*newnode)=malloc(sizeof(struct node));
Step32: ptr->n = splitPos;
Step33:(*newnode)->n = M-1-splitPos;
Step34: repeat upto step 37
for (i=0; i < (*newnode)->n; i++)
Step35:
(*newnode)->p[i] = ptr->p[i + splitPos + 1];
Step36: check
if(i < (*newnode)->n - 1)
(*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
Step37: else
(*newnode)->keys[i] = lastKey;
Step38:
(*newnode)->p[(*newnode)->n] = lastPtr;
Step39: return InsertIt;
Step40: Stop

3. Algorithm for inserting key:
void insert(int key)
Step1: Start
Step2: Declare struct node *newnode;
int upKey;
enum KeyStatus value;
Step3:value=ins(root,key,&upKey,&newnode);
Step4: Check if (value == Duplicate)
Step6: check if (value == InsertIt)
{
struct node *uproot = root;
root=malloc(sizeof(struct node));
root->n = 1;
root->keys[0] = upKey;
root->p[0] = uproot;
root->p[1] = newnode;
}
Step7: Stop

4. Algorithm for display:
void display(struct node *ptr, int blanks)
Step1:Start
Step2: Check if (ptr) upto step9
Step3:Repeat for(i=1;i<=blanks;i++)
Step4: print(" ")
Step5: repeat for (i=0; i < ptr->n; i++)
Step6: print ptr->keys[i]
Step7: print "\n"
Step8: repeat for (i=0; i <= ptr->n; i++)
Step9: call sub function
display(ptr->p[i], blanks+10)
Step10: Stop

5. Algorithm:
int main()
Step1: Start
Step2: Declare int key,ch
Step3:Read the Creation of B tree for node M
Step4: repeat while(1) upto step 7
Step7: switch(ch)
case 1: printf("Enter the key : ");
scanf("%d",&key);
insert(key);
break;
case 2: printf("Btree is :\n");
display(root,0);
break;
case 3: exit(0);
default:printf("Wrong choice\n");
break;
Step8: stop

Thanks
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..