btree.c

#include <stdio.h>
#include <stdlib.h>

#define MAX 3
#define MIN 2

struct BTreeNode {
  int val[MAX + 1], count;
  struct BTreeNode *link[MAX + 1];
};

struct BTreeNode *root;

struct BTreeNode *createNode(int val, struct BTreeNode *child);
void insertNode(int val, int pos, struct BTreeNode *node, struct BTreeNode *child);
void splitNode(int val, int *pval, int pos, struct BTreeNode *node, struct BTreeNode *child, struct BTreeNode **newNode);
int setValue(int val, int *pval, struct BTreeNode *node, struct BTreeNode **child);
void insert(int val);
void search(int val, int *pos, struct BTreeNode *myNode);
void traversal(struct BTreeNode *myNode);

void displayMenu() {
    printf("B-Tree Operations:\n");
    printf("1. Insert\n");
    printf("2. Search\n");
    printf("3. Display\n");
    printf("4. Exit\n");
}

int main() {
    int choice, value, pos;

    while (1) {
        displayMenu();
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter value to insert: ");
                scanf("%d", &value);
                insert(value);
                break;

            case 2:
                printf("Enter value to search: ");
                scanf("%d", &value);
                search(value, &pos, root);
                if (pos != -1) {
                    printf("%d is found at position %d.\n", value, pos);
                } else {
                    printf("%d is not found.\n", value);
                }
                break;

            case 3:
                printf("B-tree: ");
                traversal(root);
                printf("\n");
                break;

            case 4:
                printf("Exiting the program.\n");
                exit(0);

            default:
                printf("Invalid choice. Please try again.\n");
        }
    }

    return 0;
}

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;
}

void insertNode(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++;
}

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) {
    insertNode(val, pos, node, child);
  } else {
    insertNode(val, pos - median, *newNode, child);
  }
  *pval = node->val[node->count];
  (*newNode)->link[0] = node->link[node->count];
  node->count--;
}

int setValue(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 are not permitted\n");
      return 0;
    }
  }
  if (setValue(val, pval, node->link[pos], child)) {
    if (node->count < MAX) {
      insertNode(*pval, pos, node, *child);
    } else {
      splitNode(*pval, pval, pos, node, *child, child);
      return 1;
    }
  }
  return 0;
}

void insert(int val) {
  int flag, i;
  struct BTreeNode *child;

  flag = setValue(val, &i, root, &child);
  if (flag)
    root = createNode(i, child);
}

void search(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("%d is found\n", val);
      return;
    }
  }
  search(val, pos, myNode->link[*pos]);

  return;
}

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]);
  }
}
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 5
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 3
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 21
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 9
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 1
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 13
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 2
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 7
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 10
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 12
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 4
// B-Tree Operations:
// 1. Insert
// 2. Search
// 3. Display
// 4. Exit
// Enter your choice: 1
// Enter value to insert: 8