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
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.