B tree in data structure – technicalseek

B tree in data structure is another type of tree data structure. It is also called as multiway search tree.

In this tutorial we will see B tree definition, B tree properties and B tree program in c.

B tree Definition

In External searching out aim is to minimize the file access and this can be done by reducing the height of the trees. The height to M-way tree is less because of its large branching factor, but its height can still be reduced. If it is balanced so a new tree structure was developed by Bayer which was a height balanced M-way tree which is named as B tree.

B tree properties

All leaf nodes are at same level.
And All non leaf (except root) should have at least [M/2] Child.
All node should have at least [M/2-1] keys.
If the root node is non leaf then it have at least 2 child and at least one key.
A non leaf with N-1 key value should have non Null child.

Insertion in B Tree

Insert the nodes in tree by considering the rules of B tree .

B tree Deletion

Searching in B tree

Search 25 in below tree

first it compare with 30 , 25 < 30 , search in left sub tree.

Now 25 > 12 && 25 > 20 , search in right sub tree

compared 25 with 25, 27 and 28

25 = 25 , found in tree.

C program for B tree implementation

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349

#include <stdio.h> #include <stdlib.h> #define MAX 4 #define MIN 2 struct btreeNode { int val[MAX + 1], count; struct btreeNode *link[MAX + 1]; }; struct btreeNode *root; /* creating new node */ struct btreeNode * createNode(int val, struct btreeNode *child) { struct btreeNode *newNode; newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode)); newNode->val[1] = val; newNode->count = 1; newNode->link[0] = root; newNode->link[1] = child; return newNode; } /* Places the value in appropriate position */ void addValToNode(int val, int pos, struct btreeNode *node, struct btreeNode *child) { int j = node->count; while (j > pos) { node->val[j + 1] = node->val[j]; node->link[j + 1] = node->link[j]; j–; } node->val[j + 1] = val; node->link[j + 1] = child; node->count++; } /* split the node */ void splitNode (int val, int *pval, int pos, struct btreeNode *node, struct btreeNode *child, struct btreeNode **newNode) { int median, j; if (pos > MIN) median = MIN + 1; else median = MIN; *newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode)); j = median + 1; while (j <= MAX) { (*newNode)->val[j – median] = node->val[j]; (*newNode)->link[j – median] = node->link[j]; j++; } node->count = median; (*newNode)->count = MAX – median; if (pos <= MIN) { addValToNode(val, pos, node, child); } else { addValToNode(val, pos – median, *newNode, child); } *pval = node->val[node->count]; (*newNode)->link[0] = node->link[node->count]; node->count–; } /* sets the value val in the node */ int setValueInNode(int val, int *pval, struct btreeNode *node, struct btreeNode **child) { int pos; if (!node) { *pval = val; *child = NULL; return 1; } if (val < node->val[1]) { pos = 0; } else { for (pos = node->count; (val < node->val[pos] && pos > 1); pos–); if (val == node->val[pos]) { printf(“Duplicates not allowed\n”); return 0; } } if (setValueInNode(val, pval, node->link[pos], child)) { if (node->count < MAX) { addValToNode(*pval, pos, node, *child); } else { splitNode(*pval, pval, pos, node, *child, child); return 1; } } return 0; } /* insert val in B-Tree */ void insertion(int val) { int flag, i; struct btreeNode *child; flag = setValueInNode(val, &i, root, &child); if (flag) root = createNode(i, child); } /* copy successor for the value to be deleted */ void copySuccessor(struct btreeNode *myNode, int pos) { struct btreeNode *dummy; dummy = myNode->link[pos]; for (;dummy->link[0] != NULL;) dummy = dummy->link[0]; myNode->val[pos] = dummy->val[1]; } /* removes the value from the given node and rearrange values */ void removeVal(struct btreeNode *myNode, int pos) { int i = pos + 1; while (i <= myNode->count) { myNode->val[i – 1] = myNode->val[i]; myNode->link[i – 1] = myNode->link[i]; i++; } myNode->count–; } /* shifts value from parent to right child */ void doRightShift(struct btreeNode *myNode, int pos) { struct btreeNode *x = myNode->link[pos]; int j = x->count; while (j > 0) { x->val[j + 1] = x->val[j]; x->link[j + 1] = x->link[j]; } x->val[1] = myNode->val[pos]; x->link[1] = x->link[0]; x->count++; x = myNode->link[pos – 1]; myNode->val[pos] = x->val[x->count]; myNode->link[pos] = x->link[x->count]; x->count–; return; } /* shifts value from parent to left child */ void doLeftShift(struct btreeNode *myNode, int pos) { int j = 1; struct btreeNode *x = myNode->link[pos – 1]; x->count++; x->val[x->count] = myNode->val[pos]; x->link[x->count] = myNode->link[pos]->link[0]; x = myNode->link[pos]; myNode->val[pos] = x->val[1]; x->link[0] = x->link[1]; x->count–; while (j <= x->count) { x->val[j] = x->val[j + 1]; x->link[j] = x->link[j + 1]; j++; } return; } /* merge nodes */ void mergeNodes(struct btreeNode *myNode, int pos) { int j = 1; struct btreeNode *x1 = myNode->link[pos], *x2 = myNode->link[pos – 1]; x2->count++; x2->val[x2->count] = myNode->val[pos]; x2->link[x2->count] = myNode->link[0]; while (j <= x1->count) { x2->count++; x2->val[x2->count] = x1->val[j]; x2->link[x2->count] = x1->link[j]; j++; } j = pos; while (j < myNode->count) { myNode->val[j] = myNode->val[j + 1]; myNode->link[j] = myNode->link[j + 1]; j++; } myNode->count–; free(x1); } /* adjusts the given node */ void adjustNode(struct btreeNode *myNode, int pos) { if (!pos) { if (myNode->link[1]->count > MIN) { doLeftShift(myNode, 1); } else { mergeNodes(myNode, 1); } } else { if (myNode->count != pos) { if(myNode->link[pos – 1]->count > MIN) { doRightShift(myNode, pos); } else { if (myNode->link[pos + 1]->count > MIN) { doLeftShift(myNode, pos + 1); } else { mergeNodes(myNode, pos); } } } else { if (myNode->link[pos – 1]->count > MIN) doRightShift(myNode, pos); else mergeNodes(myNode, pos); } } } /* delete val from the node */ int delValFromNode(int val, struct btreeNode *myNode) { int pos, flag = 0; if (myNode) { if (val < myNode->val[1]) { pos = 0; flag = 0; } else { for (pos = myNode->count; (val < myNode->val[pos] && pos > 1); pos–); if (val == myNode->val[pos]) { flag = 1; } else { flag = 0; } } if (flag) { if (myNode->link[pos – 1]) { copySuccessor(myNode, pos); flag = delValFromNode(myNode->val[pos], myNode->link[pos]); if (flag == 0) { printf(“Given data is not present in B-Tree\n”); } } else { removeVal(myNode, pos); } } else { flag = delValFromNode(val, myNode->link[pos]); } if (myNode->link[pos]) { if (myNode->link[pos]->count < MIN) adjustNode(myNode, pos); } } return flag; } /* delete val from B-tree */ void deletion(int val, struct btreeNode *myNode) { struct btreeNode *tmp; if (!delValFromNode(val, myNode)) { printf(“Given value is not present in B-Tree\n”); return; } else { if (myNode->count == 0) { tmp = myNode; myNode = myNode->link[0]; free(tmp); } } root = myNode; return; } /* search val in B-Tree */ void searching(int val, int *pos, struct btreeNode *myNode) { if (!myNode) { return; } if (val < myNode->val[1]) { *pos = 0; } else { for (*pos = myNode->count; (val < myNode->val[*pos] && *pos > 1); (*pos)–); if (val == myNode->val[*pos]) { printf(“Given data %d is present in B-Tree”, val); return; } } searching(val, pos, myNode->link[*pos]); return; } /* B-Tree Traversal */ void traversal(struct btreeNode *myNode) { int i; if (myNode) { for (i = 0; i < myNode->count; i++) { traversal(myNode->link[i]); printf(“%d “, myNode->val[i + 1]); } traversal(myNode->link[i]); } } int main() { int val, ch; while (1) { printf(“1. Insertion\t2. Deletion\n”); printf(“3. Searching\t4. Traversal\n”); printf(“5. Exit\nEnter your choice:”); scanf(“%d”, &ch); switch (ch) { case 1: printf(“Enter your input:”); scanf(“%d”, &val); insertion(val); break; case 2: printf(“Enter the element to delete:”); scanf(“%d”, &val); deletion(val, root); break; case 3: printf(“Enter the element to search:”); scanf(“%d”, &val); searching(val, &ch, root); break; case 4: traversal(root); break; case 5: exit(0); default: printf(“U have entered wrong option!!\n”); break; } printf(“\n”); } }