Construct B-Tree an order of 5 with a set of 100 random elements stored in array. Implement searching, insertion and deletion operations.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ORDER 5
#define MAX_KEYS (ORDER - 1)
#define MIN_KEYS (ORDER / 2)
typedef struct BTreeNode {
int keys[MAX_KEYS];
struct BTreeNode *children[ORDER];
int num_keys;
int is_leaf;
} BTreeNode;
typedef struct BTree {
BTreeNode *root;
} BTree;
// Create a new node
BTreeNode* create_node() {
BTreeNode *node = (BTreeNode*)malloc(sizeof(BTreeNode));
node->num_keys = 0;
node->is_leaf = 1;
for (int i = 0; i < ORDER; i++) {
node->children[i] = NULL;
}
return node;
}
// Create a new B-Tree
BTree* create_btree() {
BTree *tree = (BTree*)malloc(sizeof(BTree));
tree->root = NULL;
return tree;
}
// Split a full child node
void split_child(BTreeNode *parent, int index, BTreeNode *child) {
BTreeNode *new_node = create_node();
new_node->is_leaf = child->is_leaf;
new_node->num_keys = MIN_KEYS - 1;
// Move keys to new node
for (int i = 0; i < MIN_KEYS - 1; i++) {
new_node->keys[i] = child->keys[i + MIN_KEYS];
}
// Move children if not leaf
if (!child->is_leaf) {
for (int i = 0; i < MIN_KEYS; i++) {
new_node->children[i] = child->children[i + MIN_KEYS];
}
}
child->num_keys = MIN_KEYS - 1;
// Shift parent's children
for (int i = parent->num_keys; i > index; i--) {
parent->children[i + 1] = parent->children[i];
}
parent->children[index + 1] = new_node;
// Shift parent's keys
for (int i = parent->num_keys - 1; i >= index; i--) {
parent->keys[i + 1] = parent->keys[i];
}
parent->keys[index] = child->keys[MIN_KEYS - 1];
parent->num_keys++;
}
// Insert a key into a non-full node
void insert_nonfull(BTreeNode *node, int key) {
int i = node->num_keys - 1;
if (node->is_leaf) {
while (i >= 0 && key < node->keys[i]) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->num_keys++;
} else {
while (i >= 0 && key < node->keys[i]) {
i--;
}
i++;
if (node->children[i]->num_keys == MAX_KEYS) {
split_child(node, i, node->children[i]);
if (key > node->keys[i]) {
i++;
}
}
insert_nonfull(node->children[i], key);
}
}
// Insert a key into the B-Tree
void insert(BTree *tree, int key) {
if (tree->root == NULL) {
tree->root = create_node();
tree->root->keys[0] = key;
tree->root->num_keys = 1;
return;
}
if (tree->root->num_keys == MAX_KEYS) {
BTreeNode *new_root = create_node();
new_root->is_leaf = 0;
new_root->children[0] = tree->root;
tree->root = new_root;
split_child(new_root, 0, new_root->children[0]);
insert_nonfull(new_root, key);
} else {
insert_nonfull(tree->root, key);
}
}
// Search for a key
BTreeNode* search(BTreeNode *node, int key, int *index) {
if (node == NULL) return NULL;
int i = 0;
while (i < node->num_keys && key > node->keys[i]) {
i++;
}
if (i < node->num_keys && key == node->keys[i]) {
*index = i;
return node;
}
if (node->is_leaf) {
return NULL;
}
return search(node->children[i], key, index);
}
// Find predecessor
int get_predecessor(BTreeNode *node) {
BTreeNode *current = node;
while (!current->is_leaf) {
current = current->children[current->num_keys];
}
return current->keys[current->num_keys - 1];
}
// Merge two nodes
void merge_nodes(BTreeNode *node, int index) {
BTreeNode *child = node->children[index];
BTreeNode *sibling = node->children[index + 1];
child->keys[MIN_KEYS - 1] = node->keys[index];
for (int i = 0; i < sibling->num_keys; i++) {
child->keys[i + MIN_KEYS] = sibling->keys[i];
}
if (!child->is_leaf) {
for (int i = 0; i <= sibling->num_keys; i++) {
child->children[i + MIN_KEYS] = sibling->children[i];
}
}
for (int i = index + 1; i < node->num_keys; i++) {
node->keys[i - 1] = node->keys[i];
node->children[i] = node->children[i + 1];
}
child->num_keys += sibling->num_keys + 1;
node->num_keys--;
free(sibling);
}
// Borrow from previous sibling
void borrow_from_prev(BTreeNode *node, int index) {
BTreeNode *child = node->children[index];
BTreeNode *sibling = node->children[index - 1];
for (int i = child->num_keys - 1; i >= 0; i--) {
child->keys[i + 1] = child->keys[i];
}
if (!child->is_leaf) {
for (int i = child->num_keys; i >= 0; i--) {
child->children[i + 1] = child->children[i];
}
}
child->keys[0] = node->keys[index - 1];
if (!child->is_leaf) {
child->children[0] = sibling->children[sibling->num_keys];
}
node->keys[index - 1] = sibling->keys[sibling->num_keys - 1];
child->num_keys++;
sibling->num_keys--;
}
// Borrow from next sibling
void borrow_from_next(BTreeNode *node, int index) {
BTreeNode *child = node->children[index];
BTreeNode *sibling = node->children[index + 1];
child->keys[child->num_keys] = node->keys[index];
if (!child->is_leaf) {
child->children[child->num_keys + 1] = sibling->children[0];
}
node->keys[index] = sibling->keys[0];
for (int i = 1; i < sibling->num_keys; i++) {
sibling->keys[i - 1] = sibling->keys[i];
}
if (!sibling->is_leaf) {
for (int i = 1; i <= sibling->num_keys; i++) {
sibling->children[i - 1] = sibling->children[i];
}
}
child->num_keys++;
sibling->num_keys--;
}
// Delete a key from a node
void delete_key(BTreeNode *node, int key) {
int i = 0;
while (i < node->num_keys && key > node->keys[i]) {
i++;
}
if (i < node->num_keys && key == node->keys[i]) {
if (node->is_leaf) {
for (int j = i; j < node->num_keys - 1; j++) {
node->keys[j] = node->keys[j + 1];
}
node->num_keys--;
} else {
BTreeNode *pred = node->children[i];
if (pred->num_keys >= MIN_KEYS) {
int pred_key = get_predecessor(pred);
delete_key(pred, pred_key);
node->keys[i] = pred_key;
} else {
BTreeNode *succ = node->children[i + 1];
if (succ->num_keys >= MIN_KEYS) {
int succ_key = succ->keys[0];
delete_key(succ, succ_key);
node->keys[i] = succ_key;
} else {
merge_nodes(node, i);
delete_key(node->children[i], key);
}
}
}
} else {
if (node->is_leaf) {
return;
}
BTreeNode *child = node->children[i];
if (child->num_keys < MIN_KEYS) {
if (i > 0 && node->children[i - 1]->num_keys >= MIN_KEYS) {
borrow_from_prev(node, i);
} else if (i < node->num_keys && node->children[i + 1]->num_keys >= MIN_KEYS) {
borrow_from_next(node, i);
} else {
if (i < node->num_keys) {
merge_nodes(node, i);
} else {
merge_nodes(node, i - 1);
i--;
}
}
}
delete_key(child, key);
}
}
// Delete a key from the B-Tree
void delete(BTree *tree, int key) {
if (tree->root == NULL) return;
delete_key(tree->root, key);
if (tree->root->num_keys == 0 && !tree->root->is_leaf) {
BTreeNode *temp = tree->root;
tree->root = tree->root->children[0];
free(temp);
}
}
// Print the tree (for debugging)
void print_tree(BTreeNode *node, int level) {
if (node == NULL) return;
for (int i = 0; i < node->num_keys; i++) {
printf("%*s%d ", level * 2, "", node->keys[i]);
}
printf("\n");
if (!node->is_leaf) {
for (int i = 0; i <= node->num_keys; i++) {
print_tree(node->children[i], level + 1);
}
}
}
int main() {
BTree *tree = create_btree();
srand(time(NULL));
// Generate and insert 100 random numbers
int numbers[100];
printf("Inserting 100 random numbers:\n");
for (int i = 0; i < 100; i++) {
numbers[i] = rand() % 1000; // Random numbers 0-999
insert(tree, numbers[i]);
printf("%d ", numbers[i]);
}
printf("\n\nB-Tree structure:\n");
print_tree(tree->root, 0);
// Demonstrate search
printf("\nSearching for 5 random numbers:\n");
for (int i = 0; i < 5; i++) {
int key = numbers[rand() % 100];
int index;
BTreeNode *result = search(tree->root, key, &index);
printf("Key %d: %s\n", key, result ? "Found" : "Not found");
}
// Demonstrate deletion
printf("\nDeleting 5 random numbers:\n");
for (int i = 0; i < 5; i++) {
int key = numbers[rand() % 100];
printf("Deleting %d\n", key);
delete(tree, key);
}
printf("\nB-Tree structure after deletions:\n");
print_tree(tree->root, 0);
return 0;
}
Output:
Comments
Post a Comment