#include <stdio.
h>
#include <stdlib.h>
#define MAX 4 // Maximum number of keys in a node (order 5)
#define MIN 2 // Minimum number of keys in a node
typedef struct BTreeNode {
int keys[MAX + 1]; // Keys in the node
int count; // Number of keys in the node
struct BTreeNode* children[MAX + 1]; // Child pointers
} BTreeNode;
BTreeNode* root = NULL;
// Function prototypes
void insert(int key);
void delete(int key);
void inorderTraversal(BTreeNode* node);
BTreeNode* createNode(int key, BTreeNode* child);
void insertValue(int key, int pos, BTreeNode* node, BTreeNode* child);
void splitNode(int key, int* pval, int pos, BTreeNode* node, BTreeNode* child,
BTreeNode** newNode);
int setValue(int key, int* pval, BTreeNode* node, BTreeNode** child);
void deleteValue(int key, BTreeNode* node);
void adjustNode(BTreeNode* node, int pos);
void mergeNodes(BTreeNode* node, int pos);
void successor(BTreeNode* node, int pos);
void borrowFromPrev(BTreeNode* node, int pos);
void borrowFromNext(BTreeNode* node, int pos);
BTreeNode* createNode(int key, BTreeNode* child) {
BTreeNode* newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
newNode->keys[1] = key;
newNode->count = 1;
newNode->children[0] = root;
newNode->children[1] = child;
return newNode;
}
void insertValue(int key, int pos, BTreeNode* node, BTreeNode* child) {
int j = node->count;
while (j > pos) {
node->keys[j + 1] = node->keys[j];
node->children[j + 1] = node->children[j];
j--;
}
node->keys[j + 1] = key;
node->children[j + 1] = child;
node->count++;
}
void splitNode(int key, int* pval, int pos, BTreeNode* node, BTreeNode* child,
BTreeNode** newNode) {
int median, j;
if (pos > MIN) {
median = MIN + 1;
} else {
median = MIN;
}
*newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
j = median + 1;
while (j <= MAX) {
(*newNode)->keys[j - median] = node->keys[j];
(*newNode)->children[j - median] = node->children[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;
if (pos <= MIN) {
insertValue(key, pos, node, child);
} else {
insertValue(key, pos - median, *newNode, child);
}
*pval = node->keys[node->count];
(*newNode)->children[0] = node->children[node->count];
node->count--;
}
int setValue(int key, int* pval, BTreeNode* node, BTreeNode** child) {
int pos;
if (!node) {
*pval = key;
*child = NULL;
return 1;
}
if (key < node->keys[1]) {
pos = 0;
} else {
for (pos = node->count; (key < node->keys[pos] && pos > 1); pos--);
if (key == node->keys[pos]) {
printf("Duplicate keys are not allowed.\n");
return 0;
}
}
if (setValue(key, pval, node->children[pos], child)) {
if (node->count < MAX) {
insertValue(*pval, pos, node, *child);
} else {
splitNode(*pval, pval, pos, node, *child, child);
return 1;
}
}
return 0;
}
void insert(int key) {
int flag, i;
BTreeNode* child;
flag = setValue(key, &i, root, &child);
if (flag) {
root = createNode(i, child);
}
}
void inorderTraversal(BTreeNode* node) {
if (node) {
int i;
for (i = 0; i < node->count; i++) {
inorderTraversal(node->children[i]);
printf("%d ", node->keys[i + 1]);
}
inorderTraversal(node->children[i]);
}
}
void delete(int key) {
deleteValue(key, root);
if (root->count == 0) {
BTreeNode* tmp = root;
if (root->children[0]) {
root = root->children[0];
} else {
root = NULL;
}
free(tmp);
}
}
void deleteValue(int key, BTreeNode* node) {
int pos, found,i;
if (!node) {
printf("The key %d is not found in the tree.\n", key);
return;
}
if (key < node->keys[1]) {
pos = 0;
} else {
for (pos = node->count; (key < node->keys[pos] && pos > 1); pos--);
if (key == node->keys[pos]) {
found = 1;
}
}
if (found) {
if (node->children[pos]) { // Key found in internal node
successor(node, pos);
deleteValue(node->keys[pos], node->children[pos]);
} else { // Key found in leaf node
for (i = pos + 1; i <= node->count; i++) {
node->keys[i - 1] = node->keys[i];
}
node->count--;
}
} else {
if (node->children[pos]) { // Key not found, go to child
if (node->children[pos]->count >= MIN) {
deleteValue(key, node->children[pos]);
} else {
adjustNode(node, pos);
deleteValue(key, node->children[pos]);
}
} else {
printf("The key %d is not found in the tree.\n", key);
}
}
}
void adjustNode(BTreeNode* node, int pos) {
if (pos == 0) {
if (node->children[1]->count > MIN) {
borrowFromNext(node, pos);
} else {
mergeNodes(node, pos);
}
} else if (pos == node->count) {
if (node->children[pos - 1]->count > MIN) {
borrowFromPrev(node, pos);
} else {
mergeNodes(node, pos - 1);
}
} else {
if (node->children[pos - 1]->count > MIN) {
borrowFromPrev(node, pos);
} else if (node->children[pos + 1]->count > MIN) {
borrowFromNext(node, pos);
} else {
mergeNodes(node, pos);
}
}
}
void mergeNodes(BTreeNode* node, int pos) {
BTreeNode* child = node->children[pos];
BTreeNode* sibling = node->children[pos + 1];
int i;
child->keys[MIN] = node->keys[pos + 1];
for (i = 1; i <= sibling->count; i++) {
child->keys[i + MIN] = sibling->keys[i];
}
for (i = 0; i <= sibling->count; i++) {
child->children[i + MIN] = sibling->children[i];
}
for (i = pos + 1; i < node->count; i++) {
node->keys[i] = node->keys[i + 1];
node->children[i] = node->children[i + 1];
}
child->count += sibling->count + 1;
node->count--;
free(sibling);
}
void successor(BTreeNode* node, int pos) {
BTreeNode* current = node->children[pos];
while (current->children[0]) {
current = current->children[current->count];
}
node->keys[pos + 1] = current->keys[current->count];
}
void borrowFromPrev(BTreeNode* node, int pos) {
BTreeNode* child = node->children[pos];
BTreeNode* sibling = node->children[pos - 1];
int i;
for (i = child->count; i > 0; i--) {
child->keys[i + 1] = child->keys[i];
}
if (child->children[0]) {
for (i = child->count + 1; i > 0; i--) {
child->children[i] = child->children[i - 1];
}
}
child->keys[1] = node->keys[pos];
if (child->children[0]) {
child->children[0] = sibling->children[sibling->count];
}
node->keys[pos] = sibling->keys[sibling->count];
sibling->count--;
child->count++;
}
void borrowFromNext(BTreeNode* node, int pos) {
BTreeNode* child = node->children[pos];
BTreeNode* sibling = node->children[pos + 1];
int i;
child->keys[child->count + 1] = node->keys[pos + 1];
if (child->children[0]) {
child->children[child->count + 1] = sibling->children[0];
}
node->keys[pos + 1] = sibling->keys[1];
for (i = 1; i < sibling->count; i++) {
sibling->keys[i] = sibling->keys[i + 1];
}
if (sibling->children[0]) {
for (i = 0; i < sibling->count; i++) {
sibling->children[i] = sibling->children[i + 1];
}
}
sibling->count--;
child->count++;
}
int main() {
int key, choice;
while (1) {
printf("\n1. Insert\n2. Delete\n3. Inorder Traversal\n4. Exit\nEnter your
choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the key to insert: ");
scanf("%d", &key);
insert(key);
break;
case 2:
printf("Enter the key to delete: ");
scanf("%d", &key);
delete(key);
break;
case 3:
printf("Inorder traversal of the B-tree: ");
inorderTraversal(root);
printf("\n");
break;
case 4:
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}
