This blog is under construction

Friday 31 May 2013

C Program To Perform Insertion, Deletion and Traversal In B-Tree

  • B- tree is a multiway search tree.  A node in B-tree of order n can have at most n-1 values and n children.
  • All values that appear on the left sub-tree are smaller than left most value in the parent node.
  • All values that appear on the right sub-tree are greater than right most value in the parent node.
  • All values that appear on the middle sub-tree are greater than leftmost value in parent node and smaller than right most value in parent node.

Example for B-tree of Order 3:
                                                  70
                                             /          \
                                        17  67        89 
                                     /    |     \     /     \
                               12 15   29   69  75    92 99 

 Above is an example for B-Tree of order 3.
  • An intermediate node can have 2 or 3 children.
  • Any node can have at most 1 or 2 values.
  • Nodes on the left sub-tree are smaller than the left most value in parent node.
  • Nodes on the right sub-tree are greater than the right most value in parent node.
  • Nodes on the middle sub-tree are smaller than left most value and greater than right most value in parent node.

Searching in B-Tree:

                                                   70 
                                             /          \
                                        17  67         89 
                                     /    |     \     /     \
                               12 15   29    69  75    92 99 

 Search the value 29 in above B-Tree.
29 < 70 - So, search in left sub-tree of 70
29 > 17  && 29 < 67 - So, search in middle sub-tree.
29 is the middle child of 17 & 67.

 Insertion in B-Tree:

                                                   70 
                                             /          \
                                        17  67        89 
                                     /    |     \     /     \
                               12 15   29     69 75    92 99

 Insert the value 10 to the above B-Tree.
Find the appropriate position to insert the given value in B-Tree.
10 < 70 - Search in left sub-tree of 70.
10 < 17 - Search in left sub-tree of 17.

 17 needs to be inserted in the left child of 17.

                                                   70 
                                             /          \
                                        17  67         89 
                                     /    |     \     /     \
                           17 12 15   29    69  75    92 99

 Now, the modified node has 3 values 17, 12 and 15.  But, it violates the rule in B-Tree(any node in B-Tree of order can have at most n-1 value).

 To restore B-Tree, middle value of 17, 12 and 15 is moved to parent node.  Then, split the resultant node containing 17 and 15 into two nodes forming left and right sub-tree containing the value 17 and 15 correspondingly. 

                                                    70     
                                             /             \
                                    12  17  67           89 
                                  /    /    |     \      /     \
                               17    15   29     69 75    92 99

 Now, the parent node violates B-Tree definition.  So, restore it.
                                                  70  17  
                                             /       |         \
                                          12       67        89 
                                        /   \     /   \      /     \
                                     17    15  29    69 75    92 99

 Deletion in B-Tree:

                                                  70 
                                             /          \
                                        17  67         89 
                                     /    |     \     /     \
                                12 15   29   69  75    92 99 

 Delete 69 from the above B-Tree.  Search the position of 69 to delete.
69 < 70 - Search in left sub-tree of 70
69 > 17 - Compare 69 with right most value in the search node.
60 > 67 - Search in right sub-tree of 67
69 is the right child of 67.

 In case the node which we are trying to delete has only one value(69), then find the predecessor(29) for it(69) and merge the predecessor with the sibiling(29) of the node to be deleted.  Then, delete the desired node.
                                                  70 
                                             /           \
                                           17            89 
                                         /     \        /     \
                                  12 15   29 67  75     92 99  


 Example Program For Insertion, Deletion And Traversal In B-Tree(in C):


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

   #define MAX 4
  #define MIN 2

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

   struct btreeNode *root;

   /* creating new node */
  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;
  }

   /* Places the value in appropriate position */
  void addValToNode(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++;
  }

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

  /* sets the value val in the node */
  int setValueInNode(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 not allowed\n");
                        return 0;
                }
        }
        if (setValueInNode(val, pval, node->link[pos], child)) {
                if (node->count < MAX) {
                        addValToNode(*pval, pos, node, *child);
                } else {
                        splitNode(*pval, pval, pos, node, *child, child);
                        return 1;
                }
        }
        return 0;
  }

  /* insert val in B-Tree */
  void insertion(int val) {
        int flag, i;
        struct btreeNode *child;

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

  /* copy successor for the value to be deleted */
  void copySuccessor(struct btreeNode *myNode, int pos) {
        struct btreeNode *dummy;
        dummy = myNode->link[pos];

        for (;dummy->link[0] != NULL;)
                dummy = dummy->link[0];
        myNode->val[pos] = dummy->val[1];

  }

  /* removes the value from the given node and rearrange values */
  void removeVal(struct btreeNode *myNode, int pos) {
        int i = pos + 1;
        while (i <= myNode->count) {
                myNode->val[i - 1] = myNode->val[i];
                myNode->link[i - 1] = myNode->link[i];
                i++;
        }
        myNode->count--;
  }

  /* shifts value from parent to right child */
  void doRightShift(struct btreeNode *myNode, int pos) {
        struct btreeNode *x = myNode->link[pos];
        int j = x->count;

        while (j > 0) {
                x->val[j + 1] = x->val[j];
                x->link[j + 1] = x->link[j];
        }
        x->val[1] = myNode->val[pos];
        x->link[1] = x->link[0];
        x->count++;

        x = myNode->link[pos - 1];
        myNode->val[pos] = x->val[x->count];
        myNode->link[pos] = x->link[x->count];
        x->count--;
        return;
  }

  /* shifts value from parent to left child */
  void doLeftShift(struct btreeNode *myNode, int pos) {
        int j = 1;
        struct btreeNode *x = myNode->link[pos - 1];

        x->count++;
        x->val[x->count] = myNode->val[pos];
        x->link[x->count] = myNode->link[pos]->link[0];

        x = myNode->link[pos];
        myNode->val[pos] = x->val[1];
        x->link[0] = x->link[1];
        x->count--;

        while (j <= x->count) {
                x->val[j] = x->val[j + 1];
                x->link[j] = x->link[j + 1];
                j++;
        }
        return;
  }

  /* merge nodes */
  void mergeNodes(struct btreeNode *myNode, int pos) {
        int j = 1;
        struct btreeNode *x1 = myNode->link[pos], *x2 = myNode->link[pos - 1];

        x2->count++;
        x2->val[x2->count] = myNode->val[pos];
        x2->link[x2->count] = myNode->link[0];

        while (j <= x1->count) {
                x2->count++;
                x2->val[x2->count] = x1->val[j];
                x2->link[x2->count] = x1->link[j];
                j++;
        }

        j = pos;
        while (j < myNode->count) {
                myNode->val[j] = myNode->val[j + 1];
                myNode->link[j] = myNode->link[j + 1];
                j++;
        }
        myNode->count--;
        free(x1);
  }

  /* adjusts the given node */
  void adjustNode(struct btreeNode *myNode, int pos) {
        if (!pos) {
                if (myNode->link[1]->count > MIN) {
                        doLeftShift(myNode, 1);
                } else {
                        mergeNodes(myNode, 1);
                }
        } else {
                if (myNode->count != pos) {
                        if(myNode->link[pos - 1]->count > MIN) {
                                doRightShift(myNode, pos);
                        } else {
                                if (myNode->link[pos + 1]->count > MIN) {
                                        doLeftShift(myNode, pos + 1);
                                } else {
                                        mergeNodes(myNode, pos);
                                }
                        }
                } else {
                        if (myNode->link[pos - 1]->count > MIN)
                                doRightShift(myNode, pos);
                        else
                                mergeNodes(myNode, pos);
                }
        }
  }

  /* delete val from the node */
  int delValFromNode(int val, struct btreeNode *myNode) {
        int pos, flag = 0;
        if (myNode) {
                if (val < myNode->val[1]) {
                        pos = 0;
                        flag = 0;
                } else {
                        for (pos = myNode->count;
                                (val < myNode->val[pos] && pos > 1); pos--);
                         if (val == myNode->val[pos]) {
                                flag = 1;
                        } else {
                                flag = 0;
                        }
                }
                if (flag) {
                        if (myNode->link[pos - 1]) {
                                copySuccessor(myNode, pos);
                                flag = delValFromNode(myNode->val[pos], myNode->link[pos]);
                                if (flag == 0) {
                                        printf("Given data is not present in B-Tree\n");
                                }
                        } else {
                                removeVal(myNode, pos);
                        }
                } else {
                        flag = delValFromNode(val, myNode->link[pos]);
                }
                if (myNode->link[pos]) {
                        if (myNode->link[pos]->count < MIN)
                                adjustNode(myNode, pos);
                }
        }
        return flag;
  }

  /* delete val from B-tree */
  void deletion(int val, struct btreeNode *myNode) {
        struct btreeNode *tmp;
        if (!delValFromNode(val, myNode)) {
                printf("Given value is not present in B-Tree\n");
                return;
        } else {
                if (myNode->count == 0) {
                        tmp = myNode;
                        myNode = myNode->link[0];
                        free(tmp);
                }
        }
        root = myNode;
        return;
  }

  /* search val in B-Tree */
  void searching(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("Given data %d is present in B-Tree", val);
                        return;
                }
        }
        searching(val, pos, myNode->link[*pos]);
        return;
  }

  /* B-Tree Traversal */
  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]);
        }
  }

  int main() {
        int val, ch;
        while (1) {
                printf("1. Insertion\t2. Deletion\n");
                printf("3. Searching\t4. Traversal\n");
                printf("5. Exit\nEnter your choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter your input:");
                                scanf("%d", &val);
                                insertion(val);
                                break;
                        case 2:
                                printf("Enter the element to delete:");
                                scanf("%d", &val);
                                deletion(val, root);
                                break;
                        case 3:
                                printf("Enter the element to search:");
                                scanf("%d", &val);
                                searching(val, &ch, root);
                                break;
                        case 4:
                                traversal(root);
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("U have entered wrong option!!\n");
                                break;
                }
                printf("\n");
        }
  }



  Output:(C Program To Implement B-Tree)
  jp@jp-VirtualBox:~/$ ./a.out
  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input:70

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input:17

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input:67

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:1
  Enter your input:89 

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:4
  17 67 70 89 

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:3
  Enter the element to search:70
  Given data 70 is present in B-Tree

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:2
  Enter the element to delete:17

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:4
  67 70 89 

   1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter your choice:5




Posted by at 22:42

20 comments:

  1. Rahul Roshan12 October 2014 at 03:26

    MAX 4 means maximum 4 children one node can have ??
    MIN 2 means minimum 2 children one node can have ??

    clear this please !!!

    ReplyDelete
    Replies
    1. Unknown9 April 2016 at 15:35

      MAX 4 means one node can have 4 pointers and in turn have four children
      and 3 values

      MAX 4 means a node should have minimum 2 pointers which can be null pointers and has a minimum of one value in it

      Delete
    2. Unknown20 June 2016 at 10:33

      Complementing what was said above:
      MAX = maximum number of pointers each node can have.
      MIN = minimum number of pointer each node can have, and according to this B-Tree definition (they vary a LOT), MIN = MAX/2. So, if you're gonna change MAX manually, make you sure you update MIN accordingly.

      Delete
  2. prashu22 July 2015 at 21:02

    same doubt here!!!

    ReplyDelete
  3. abin muhammed30 March 2016 at 15:40

    This comment has been removed by the author.

    ReplyDelete
  4. abin muhammed30 March 2016 at 15:53

    Macros are dangerous in this situation because a or b will get evaluated twice, which would cause unexpected behavior on expressions whose evaluation has side effects (like a function) Beware.

    ReplyDelete
  5. Unknown20 June 2016 at 10:38

    Thanks a lot for the code, it really helped me.
    I found a completely useless line causing a node to point to itself, which is: x2->link[x2->count] = myNode->link[0];
    I really don't know what the purpose of this line was, but removing it just solves the value deletion completely.

    ReplyDelete
    Replies
    1. Unknown20 June 2016 at 10:42

      I ran into this bug while using the deletion function, so removing it fixed it completely for me. You can reproduce the bug deleting a node and then calling traverse, because one of the leaf nodes will be pointing to itself as explained.

      Delete
    2. Unknown1 November 2016 at 03:13

      I think that line should be x2->link[x2->count] = x1->link[0];

      Delete
    3. Unknown1 November 2016 at 04:17

      I think that line should be x2->link[x2->count] = x1->link[0];

      Delete
  6. Unknown29 October 2016 at 13:06

    CAN ANYONE PLEASE PROVIDE ME WITH THE CODE FOR SS TREE. ITS URGENT THANK YOU SO MUCH

    ReplyDelete
  7. Grenal10 May 2017 at 23:09

    The while in doRightShift will never work.

    void doRightShift(struct btreeNode *myNode, int pos) {
    struct btreeNode *x = myNode->link[pos];
    int j = x->count;

    while (j > 0) {
    x->val[j + 1] = x->val[j];
    x->link[j + 1] = x->link[j];
    }

    ReplyDelete
  8. Unknown21 March 2018 at 14:08

    can you give me the code for printing that values level wise as appear in tree

    ReplyDelete
  9. Unknown5 August 2019 at 21:25

    <17 needs to be inserted in the left child of 17 > note:- sir in place of 17 it shld be 10.

    ReplyDelete
  10. Unknown5 August 2019 at 21:26

    <17 needs to be inserted in the left child of 17 > note:- sir in place of 17 it shld be 10

    ReplyDelete
  11. Ravi varma18 June 2020 at 13:49

    Can anyone explain the code

    ReplyDelete
  12. Unknown20 October 2020 at 12:14

    This tree is 4-way or 5-way or 3-way.Which one?

    ReplyDelete
  13. Unknown22 January 2021 at 00:56

    .

    ReplyDelete
  14. Vaibhav yadav20 February 2022 at 13:56

    This comment has been removed by the author.

    ReplyDelete
  15. Vaibhav yadav20 February 2022 at 14:01

    This comment has been removed by the author.

    ReplyDelete

Subscribe to: Post Comments (Atom)