/* For simplicity, provide a basic implementation focusing on insertion, search, and a simple traversal. We will not include deletion as it is quite complex and would make the code exceedingly long. In practice, B-tree deletion requires handling numerous cases to redistribute or merge nodes. */
#include <stdio.h>
#include <stdlib.h>
#define MAX_KEYS 3 // Maximum keys in a node (t-1 where t is the minimum degree)
#define MIN_KEYS 1 // Minimum keys in a node (ceil(t/2) - 1)
#define MAX_CHILDREN (MAX_KEYS + 1) // Maximum children in a node (t)
typedef struct BTreeNode {
int keys[MAX_KEYS];
struct BTreeNode* children[MAX_CHILDREN];
int numKeys;
int isLeaf;
} BTreeNode;
BTreeNode* createNode(int isLeaf) {
BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
node->isLeaf = isLeaf;
node->numKeys = 0;
for (int i = 0; i < MAX_CHILDREN; i++) {
node->children[i] = NULL;
}
return node;
}
void splitChild(BTreeNode* parent, int index, BTreeNode* child) {
BTreeNode* newChild = createNode(child->isLeaf);
newChild->numKeys = MIN_KEYS;
for (int i = 0; i < MIN_KEYS; i++) {
newChild->keys[i] = child->keys[i + MIN_KEYS + 1];
}
if (!child->isLeaf) {
for (int i = 0; i < MIN_KEYS + 1; i++) {
newChild->children[i] = child->children[i + MIN_KEYS + 1];
}
}
child->numKeys = MIN_KEYS;
for (int i = parent->numKeys; i >= index + 1; i--) {
parent->children[i + 1] = parent->children[i];
}
parent->children[index + 1] = newChild;
for (int i = parent->numKeys - 1; i >= index; i--) {
parent->keys[i + 1] = parent->keys[i];
}
parent->keys[index] = child->keys[MIN_KEYS];
parent->numKeys++;
}
void insertNonFull(BTreeNode* node, int key) {
int i = node->numKeys - 1;
if (node->isLeaf) {
while (i >= 0 && node->keys[i] > key) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->numKeys++;
} else {
while (i >= 0 && node->keys[i] > key) {
i--;
}
if (node->children[i + 1]->numKeys == MAX_KEYS) {
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->numKeys == MAX_KEYS) {
BTreeNode* newRoot = createNode(0);
newRoot->children[0] = r;
splitChild(newRoot, 0, r);
int i = 0;
if (newRoot->keys[0] < key) {
i++;
}
insertNonFull(newRoot->children[i], key);
*root = newRoot;
} else {
insertNonFull(r, key);
}
}
void traverse(BTreeNode* root) {
if (root == NULL) return;
int i;
for (i = 0; i < root->numKeys; i++) {
if (!root->isLeaf) {
traverse(root->children[i]);
}
printf("%d ", root->keys[i]);
}
if (!root->isLeaf) {
traverse(root->children[i]);
}
}
int main() {
BTreeNode* root = createNode(1);
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 constructed B-tree is:\n");
traverse(root);
return 0;
}
Traversal of the constructed B-tree is:
5 6 7 10 12 17 20 30
1) Write a program that uses functions to perform the following operations on singly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution
2) Write a program that uses functions to perform the following operations on doubly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution
3) Write a program that uses functions to perform the following operations on circular linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution
4) Write a program that implement Stack (its operations) using Array View Solution
5) Write a program that implement Stack (its operations) using Linked List (Pointer) View Solution
6) Write a program that implement Queue(its operations) using Array View Solution
7) Write a program that implement Queue (its operations) using Linked List (Pointer) View Solution
8) Write a program that implements Quick sort sorting methods to sort a given list of integers in ascending order View Solution
9) Write a program that implements Merge sort sorting methods to sort a given list of integers in ascending order View Solution
10) Write a program that implements Heap sort sorting methods to sort a given list of integers in ascending order View Solution
11) Write a program to implement the tree traversal methods using Recursive View Solution
12) Write a program to implement the tree traversal methods using Non Recursive View Solution
13) Write a program to implement Binary Search Tree (its operations) View Solution
14) Write a program to implement AVL Tree (its operations) View Solution
15) Write a program to implement Red - Black Tree (its operations) View Solution
16) Write a program to implement B Trees (its operations) View Solution
17) Write a program to implement B+ Trees (its operations) View Solution
18) Write a program to implement the graph traversal methods (Breadth First Search) View Solution
19) Write a program to implement the graph traversal methods (Depth First Search) View Solution
20) Write a program to Implement a Pattern matching algorithms using Boyer- Moore View Solution
21) Write a program to Implement a Pattern matching algorithms using Knuth-Morris-Pratt View Solution