C++ Program to Implement B+ Tree

«
»
This C++ program implements the B+ Tree. A B+ tree is an n-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.

Here is the source code of the C++ program to display a constructed B-Tree by giving the elements of the B+ Tree dynamically. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

  1. /*
  2.  * C++ Program to Implement B+ Tree
  3.  */
  4. #include<stdio.h>
  5. #include<conio.h>
  6. #include<iostream>
  7. using namespace std;
  8. struct B+TreeNode
  9. {
  10.     int *data;
  11.     B+TreeNode **child_ptr;
  12.     bool leaf;
  13.     int n;
  14. }*root = NULL, *np = NULL, *x = NULL;
  15. B+TreeNode * init()
  16. {
  17.     int i;
  18.     np = new B+TreeNode;
  19.     np->data = new int[5];
  20.     np->child_ptr = new B+TreeNode *[6];
  21.     np->leaf = true;
  22.     np->n = 0;
  23.     for (i = 0; i < 6; i++)
  24.     {
  25.         np->child_ptr[i] = NULL;
  26.     }
  27.     return np;
  28. }
  29. void traverse(B+TreeNode *p)
  30. {
  31.     cout<<endl;
  32.     int i;
  33.     for (i = 0; i < p->n; i++)
  34.     {
  35.         if (p->leaf == false)
  36.         {
  37.             traverse(p->child_ptr[i]);
  38.         }
  39.         cout << " " << p->data[i];
  40.     } 
  41.     if (p->leaf == false)
  42.     {
  43.         traverse(p->child_ptr[i]);
  44.     }
  45.     cout<<endl;
  46. }
  47. void sort(int *p, int n)
  48. {
  49.     int i, j, temp;
  50.     for (i = 0; i < n; i++)
  51.     {
  52.         for (j = i; j <= n; j++)
  53.         {
  54.             if (p[i] > p[j])
  55.             {
  56.                 temp = p[i];
  57.                 p[i] = p[j];
  58.                 p[j] = temp;
  59.             }
  60.         }
  61.     }
  62. }
  63. int split_child(B+TreeNode *x, int i)
  64. {
  65.     int j, mid;
  66.     B+TreeNode *np1, *np3, *y;
  67.     np3 = init();
  68.     np3->leaf = true;
  69.     if (i == -1)
  70.     {
  71.         mid = x->data[2];
  72.         x->data[2] = 0;
  73.         x->n--;
  74.         np1 = init();
  75.         np1->leaf = false;
  76.         x->leaf = true;
  77.         for (j = 3; j < 5; j++)
  78.         {
  79.             np3->data[j - 3] = x->data[j];
  80.             np3->child_ptr[j - 3] = x->child_ptr[j];
  81.             np3->n++;
  82.             x->data[j] = 0;
  83.             x->n--;
  84.         }
  85.         for(j = 0; j < 6; j++)
  86.         {
  87.             x->child_ptr[j] = NULL;
  88.         }
  89.         np1->data[0] = mid;
  90.         np1->child_ptr[np1->n] = x;
  91.         np1->child_ptr[np1->n + 1] = np3;
  92.         np1->n++;
  93.         root = np1;
  94.     }
  95.     else
  96.     {
  97.         y = x->child_ptr[i];
  98.         mid = y->data[2];
  99.         y->data[2] = 0;
  100.         y->n--;
  101.         for (j = 3; j < 5; j++)
  102.         {
  103.             np3->data[j - 3] = y->data[j];
  104.             np3->n++;
  105.             y->data[j] = 0;
  106.             y->n--;
  107.         }
  108.         x->child_ptr[i + 1] = y;
  109.         x->child_ptr[i + 1] = np3; 
  110.     }
  111.     return mid;
  112. }
  113. void insert(int a)
  114. {
  115.     int i, temp;
  116.     x = root;
  117.     if (x == NULL)
  118.     {
  119.         root = init();
  120.         x = root;
  121.     }
  122.     else
  123.     {
  124.         if (x->leaf == true && x->n == 5)
  125.         {
  126.             temp = split_child(x, -1);
  127.             x = root;
  128.             for (i = 0; i < (x->n); i++)
  129.             {
  130.                 if ((a > x->data[i]) && (a < x->data[i + 1]))
  131.                 {
  132.                     i++;
  133.                     break;
  134.                 }
  135.                 else if (a < x->data[0])
  136.                 {
  137.                     break;
  138.                 }
  139.                 else
  140.                 {
  141.                     continue;
  142.                 }
  143.             }
  144.             x = x->child_ptr[i];
  145.         }
  146.         else
  147.         {
  148.             while (x->leaf == false)
  149.             {
  150.             for (i = 0; i < (x->n); i++)
  151.             {
  152.                 if ((a > x->data[i]) && (a < x->data[i + 1]))
  153.                 {
  154.                     i++;
  155.                     break;
  156.                 }
  157.                 else if (a < x->data[0])
  158.                 {
  159.                     break;
  160.                 }
  161.                 else
  162.                 {
  163.                     continue;
  164.                 }
  165.             }
  166.                 if ((x->child_ptr[i])->n == 5)
  167.                 {
  168.                     temp = split_child(x, i);
  169.                     x->data[x->n] = temp;
  170.                     x->n++;
  171.                     continue;
  172.                 }
  173.                 else
  174.                 {
  175.                     x = x->child_ptr[i];
  176.                 }
  177.             }
  178.         }
  179.     }
  180.     x->data[x->n] = a;
  181.     sort(x->data, x->n);
  182.     x->n++;
  183. }
  184. int main()
  185. {
  186.     int i, n, t;
  187.     cout<<"enter the no of elements to be inserted\n";
  188.     cin>>n;
  189.     for(i = 0; i < n; i++)
  190.     {
  191.         cout<<"enter the element\n";
  192.         cin>>t;
  193.         insert(t);
  194.     }
  195.     cout<<"traversal of constructed tree\n";
  196.     traverse(root);
  197.     getch();
  198. }

advertisement
Output
enter the no of elements to be inserted
12
enter the element
4
enter the element
7
enter the element
5
enter the element
1
enter the element
9
enter the element
8
enter the element
3
enter the element
6
enter the element
2
enter the element
23
enter the element
76
enter the element
89
traversal of constructed tree
 
 
 1 2 3 4
 5
 6 7
 8
 9 23 76 89

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn