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




12 comments:

  1. 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. 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. 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. This comment has been removed by the author.

    ReplyDelete
  3. 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
  4. 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. 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. I think that line should be x2->link[x2->count] = x1->link[0];

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

      Delete
  5. Hi!
    I was hoping you could help me understand the role of a few variables here.
    i)Count
    ii)Pval

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

    ReplyDelete