C program for Insertion into a B-tree

1			#include<stdio.h>
2			#include<stdlib.h>
3			#define M 5
4			struct node
5			{
6			int n; /* n<M No.of keys in node will always less than order of B-tree */
7			int keys[M-1]; /*array of keys*/
8			struct node *p[M]; /* (n+1 pointers will be in use) */
9			}*root=NULL;
10			enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };
11			void insert(int key);
12			void display(struct node *root,int);
13			void DelNode(int x);
14			void search(int x);
15			enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
16			int searchPos(int x,int *key_arr, int n);
17			enum KeyStatus del(struct node *r, int x);
18			int main()
19			{
20			int key;
21			int choice;
22			printf("Creation of B tree for order is %d \n",M);
23			while(1)
24			{
25			printf("\n1.Insert\n");
26			printf("2.Delete\n");
27			printf("3.Search\n");
28			printf("4.Display\n");
29			printf("5.Quit\n");
30			printf("Enter your choice : ");
31			scanf("%d",&choice);
32			switch(choice)
33			{
34			case 1:
35			printf("Enter the key : ");
36			scanf("%d",&key);
37			insert(key);
38			break;
39			case 2:
40			printf("Enter the key : ");
41			scanf("%d",&key);
42			DelNode(key);
43			break;
44			case 3:
45			printf("Enter the key : ");
46			scanf("%d",&key);
47			search(key);
48			break;
49			case 4:
50			printf("Btree is :\n");
51			display(root,10);
52			break;
53			case 5:
54			exit(1);
55			default:
56			printf("Wrong choice\n");
57			break;
58			}
59			}
60			return 0;
61			}
62			void insert(int key)
63			{
64			struct node *newnode;
65			int upKey;
66			enum KeyStatus value;
67			value = ins(root, key, &upKey, &newnode);
68			if (value == Duplicate)
69			printf("Key already available\n");
70			if (value == InsertIt)
71			{
72			struct node *uproot = root;
73			root=(struct node *)malloc(sizeof(struct node));
74			root->n = 1;
75			root->keys[0] = upKey;
76			root->p[0] = uproot;
77			root->p[1] = newnode;
78			}
79			}
80			enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode)
81			{
82			struct node *newPtr, *lastPtr;
83			int pos, i, n,splitPos;
84			int newKey, lastKey;
85			enum KeyStatus value;
86			if (ptr == NULL)
87			{
88			*newnode = NULL;
89			*upKey = key;
90			return InsertIt;
91			}
92			n = ptr->n;
93			pos = searchPos(key, ptr->keys, n);
94			if (pos < n && key == ptr->keys[pos])
95			return Duplicate;
96			value = ins(ptr->p[pos], key, &newKey, &newPtr);
97			if (value != InsertIt)
98			return value;
99			/*If keys in node is less than M-1 where M is order of B tree*/
100			if (n < M - 1)
101			{
102			pos = searchPos(newKey, ptr->keys, n);
103			/*Shifting the key and pointer right for inserting the new key*/
104			for (i=n; i>pos; i--)
105			{
106			ptr->keys[i] = ptr->keys[i-1];
107			ptr->p[i+1] = ptr->p[i];
108			}
109			/*Key is inserted at exact location*/
110			ptr->keys[pos] = newKey;
111			ptr->p[pos+1] = newPtr;
112			++ptr->n; /*incrementing the number of keys in node*/
113			return Success;
114			}
115			/*If keys in nodes are maximum and position of node to be inserted is
116			last*/
117			if (pos == M - 1)
118			{
119			lastKey = newKey;
120			lastPtr = newPtr;
121			}
122			else /*If keys in node are maximum and position of node to be inserted is not last*/
123			{
124			lastKey = ptr->keys[M-2];
125			lastPtr = ptr->p[M-1];
126			for (i=M-2; i>pos; i--)
127			{
128			ptr->keys[i] = ptr->keys[i-1];
129			ptr->p[i+1] = ptr->p[i];
130			}
131			ptr->keys[pos] = newKey;
132			ptr->p[pos+1] = newPtr;
133			}
134			splitPos = (M - 1)/2;
135			(*upKey) = ptr->keys[splitPos];
136			(*newnode)= (struct node *)malloc(sizeof(struct node)); /*Right node after split*/
137			ptr->n = splitPos; /*No. of keys for left splitted node*/
138			(*newnode)->n = M-1-splitPos; /*No. of keys for right splitted node*/
139			for (i=0; i < (*newnode)->n; i++)
140			{
141			(*newnode)->p[i] = ptr->p[i + splitPos + 1];
142			if(i < (*newnode)->n - 1)
143			(*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
144			else
145			(*newnode)->keys[i] = lastKey;
146			}
147			(*newnode)->p[(*newnode)->n] = lastPtr;
148			return InsertIt;
149			}
150			void display(struct node *ptr, int blanks)
151			{
152			if (ptr)
153			{
154			int i;
155			for(i=1;i<=blanks;i++)
156			printf(" ");
157			for (i=0; i < ptr->n; i++)
158			printf("%d ",ptr->keys[i]);
159			if(blanks==10)
160			printf("\n");
161			for (i=0; i <= ptr->n; i++)
162			display(ptr->p[i], blanks-5);
163			}
164			}
165			void search(int key)
166			{
167			int pos, i, n;
168			struct node *ptr = root;
169			printf("Search path:\n");
170			while (ptr)
171			{
172			n = ptr->n;
173			for (i=0; i < ptr->n; i++)
174			printf("%d ",ptr->keys[i]);
175			printf("\n");
176			pos = searchPos(key, ptr->keys, n);
177			if (pos < n && key == ptr->keys[pos])
178			{
179			printf("Key %d found in position %d of last dispalyednode\n",key,pos);
180			return;
181			}
182			ptr = ptr->p[pos];
183			}
184			printf("Key %d is not available\n",key);
185			}
186			int searchPos(int key, int *key_arr, int n)
187			{
188			int pos=0;
189			while (pos<n && key>key_arr[pos])
190			pos++;
191			return pos;
192			}
193			void DelNode(int key)
194			{
195			struct node *uproot;
196			enum KeyStatus value;
197			value = del(root,key);
198			switch (value)
199			{
200			case SearchFailure:
201			printf("Key %d is not available\n",key);
202			break;
203			case LessKeys:
204			uproot = root;
205			root = root->p[0];
206			free(uproot);
207			break;
208			}
209			}
210			enum KeyStatus del(struct node *ptr, int key)
211			{
212			int pos, i, pivot, n ,min;
213			int *key_arr;
214			enum KeyStatus value;
215			struct node **p,*lptr,*rptr;
216			if (ptr == NULL)
217			return SearchFailure;
218			/*Assigns values of node*/
219			n=ptr->n;
220			key_arr = ptr->keys;
221			p = ptr->p;
222			min = (M - 1)/2; /*Minimum number of keys*/
223			pos = searchPos(key, key_arr, n);
224			if (p[0]==NULL)
225			{
226			if (pos==n || key<key_arr[pos])
227			return SearchFailure;
228			/*Shift keys and pointers left*/
229			for (i=pos+1; i<n; i++)
230			{
231			key_arr[i-1] = key_arr[i];
232			p[i] = p[i+1];
233			}
234			return --ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys;
235			}
236			if(pos<n && key==key_arr[pos])
237			{
238			struct node *qp = p[pos], *qp1;
239			int nkey;
240			while(1)
241			{
242			nkey = qp->n;
243			qp1 = qp->p[nkey];
244			if (qp1 == NULL)
245			break;
246			qp = qp1;
247			}
248			key_arr[pos] = qp->keys[nkey-1];
249			qp->keys[nkey - 1] = key;
250			}
251			value = del(p[pos], key);
252			if (value != LessKeys)
253			return value;
254			if (pos > 0 && p[pos-1]->n > min)
255			{
256			pivot = pos - 1; /*pivot for left and right node*/
257			lptr = p[pivot];
258			rptr = p[pos];
259			/*Assigns values for right node*/
260			rptr->p[rptr->n + 1] = rptr->p[rptr->n];
261			for (i=rptr->n; i>0; i--)
262			{
263			rptr->keys[i] = rptr->keys[i-1];
264			rptr->p[i] = rptr->p[i-1];
265			}
266			rptr->n++;
267			rptr->keys[0] = key_arr[pivot];
268			rptr->p[0] = lptr->p[lptr->n];
269			key_arr[pivot] = lptr->keys[--lptr->n];
270			return Success;
271			}
272			if (pos > min)
273			{
274			pivot = pos; /*pivot for left and right node*/
275			lptr = p[pivot];
276			rptr = p[pivot+1];
277			/*Assigns values for left node*/
278			lptr->keys[lptr->n] = key_arr[pivot];
279			lptr->p[lptr->n + 1] = rptr->p[0];
280			key_arr[pivot] = rptr->keys[0];
281			lptr->n++;
282			rptr->n--;
283			for (i=0; i < rptr->n; i++)
284			{
285			rptr->keys[i] = rptr->keys[i+1];
286			rptr->p[i] = rptr->p[i+1];
287			}
288			rptr->p[rptr->n] = rptr->p[rptr->n + 1];
289			return Success;
290			}
291			if(pos == n)
292			pivot = pos-1;
293			else
294			pivot = pos;
295			lptr = p[pivot];
296			rptr = p[pivot+1];
297			/*merge right node with left node*/
298			lptr->keys[lptr->n] = key_arr[pivot];
299			lptr->p[lptr->n + 1] = rptr->p[0];
300			for (i=0; i < rptr->n; i++)
301			{
302			lptr->keys[lptr->n + 1 + i] = rptr->keys[i];
303			lptr->p[lptr->n + 2 + i] = rptr->p[i+1];
304			}
305			lptr->n = lptr->n + rptr->n +1;
306			free(rptr); /*Remove right node*/
307			for (i=pos+1; i < n; i++)
308			{
309			key_arr[i-1] = key_arr[i];
310			p[i] = p[i+1];
311			}
312			return --ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys;
313			}
			OUTPUT:
			Creation of B tree for order is 5
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice : 1
			Enter the key : 1
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice : 1
			Enter the key : 2
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice : 1
			Enter the key : 3
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice : 1
			Enter the key : 4
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice :4
			Btree is :
			1 2 3 4
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice : 1
			Enter the key : 5
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice : 4
			Btree is : 3
			1 2 4 5
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice :2
			Enter the key : 5
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice : 4
			Btree is :
			1 2 3 4
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice : 3
			Enter the key : 5
			Search path: 1 2 3 4
			Key 5 is not available
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice : 3
			Enter the key : 1
			Search path: 1 2 3 4
			Key 1 found in position 0 of last dispalyed node
			1.Insert
			2.Delete
			3.Search
			4.Display
			5.Quit
			Enter your choice :5