#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 3 // Order of the B-tree
#define MIN 2 // Minimum keys in a node
typedef struct BTreeNode {
int keys[MAX + 1]; // Array to store keys
struct BTreeNode* children[MAX + 1]; // Array of child pointers
int n; // Current number of keys
bool leaf; // Is true if the node is a leaf
} BTreeNode;
BTreeNode* createNode(bool leaf) {
BTreeNode* newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
newNode->leaf = leaf;
newNode->n = 0; // Initialize number of keys as 0
for (int i = 0; i <= MAX; i++) {
newNode->children[i] = NULL;
}
return newNode;
}
void splitChild(BTreeNode* parent, int i, BTreeNode* child) {
BTreeNode* newNode = createNode(child->leaf);
newNode->n = MIN - 1;
for (int j = 0; j < MIN - 1; j++) {
newNode->keys[j] = child->keys[j + MIN];
}
if (!child->leaf) {
for (int j = 0; j < MIN; j++) {
newNode->children[j] = child->children[j + MIN];
}
}
child->n = MIN - 1;
for (int j = parent->n; j >= i + 1; j--) {
parent->children[j + 1] = parent->children[j];
}
parent->children[i + 1] = newNode;
for (int j = parent->n - 1; j >= i; j--) {
parent->keys[j + 1] = parent->keys[j];
}
parent->keys[i] = child->keys[MIN - 1];
parent->n++;
}
void insertNonFull(BTreeNode* node, int key) {
int i = node->n - 1;
if (node->leaf) {
while (i >= 0 && key < node->keys[i]) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->n++;
} else {
while (i >= 0 && key < node->keys[i]) i--;
if (node->children[i + 1]->n == MAX) {
splitChild(node, i + 1, node->children[i + 1]);
if (key > node->keys[i + 1]) i++;
}
insertNonFull(node->children[i + 1], key);
}
}
void insert(BTreeNode** root, int key) {
BTreeNode* r = *root;
if (r->n == MAX) {
BTreeNode* s = createNode(false);
s->children[0] = r;
splitChild(s, 0, r);
int i = 0;
if (s->keys[0] < key) i++;
insertNonFull(s->children[i], key);
*root = s;
} else {
insertNonFull(r, key);
}
}
void traverse(BTreeNode* root) {
if (root != NULL) {
int i;
for (i = 0; i < root->n; i++) {
if (!root->leaf) {
traverse(root->children[i]);
}
printf("%d ", root->keys[i]);
}
if (!root->leaf) {
traverse(root->children[i]);
}
}
}
int main() {
BTreeNode* root = createNode(true);
insert(&root, 10);
insert(&root, 20);
insert(&root, 5);
insert(&root, 6);
insert(&root, 12);
insert(&root, 30);
insert(&root, 7);
insert(&root, 17);
printf("Traversal of the B-tree:\n");
traverse(root);
return 0;
}