B tree Data structure is another type of tree and the most important self-balanced M way tree data structure.

B tree Data structure

B tree is a self-balancing tree data structure. It is also called a multi-way search tree.
B tree Definition: B tree Data structure is a self-balanced tree in which every node contains multiple keys and has more than two children.

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.

Why the B tree Data structure?
One of the main reasons for using B tree Data structure is its capability to store a large number of keys in a single node and large key values by keeping the height of the tree relatively small.

B tree Data structure properties

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

Insertion in B Tree

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

B tree insertion
B tree insertion

B tree Deletion

B tree deletion
B tree deletion

Searching in B tree

Search 25 in below tree

B tree Data structure
B tree searching

First, it compares with 30, 25 < 30, search in the left subtree.
Now 25 > 12 && 25 > 20 , search in right sub tree
compared 25 with 25, 27 and 28
25 = 25 , found in tree.

B tree program in c

#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");
}
}

Output :

B tree
B tree

Write A Comment