fork download
copy 
  1. // C++ Program to Implement B-Tree
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. // class for the node present in a B-Tree
  6. template <typename T, int ORDER>
  7. class BTreeNode {
  8. public:
  9. // Array of keys
  10.     T keys[ORDER - 1]; 
  11.     // Array of child pointers
  12.     BTreeNode* children[ORDER]; 
  13.      // Current number of keys
  14.     int n;
  15.     // True if leaf node, false otherwise
  16.     bool leaf; 
  17.  
  18.     BTreeNode(bool isLeaf = true) : n(0), leaf(isLeaf) {
  19.         for (int i = 0; i < ORDER; i++)
  20.             children[i] = nullptr;
  21.     }
  22. };
  23.  
  24. // class for B-Tree
  25. template <typename T, int ORDER>
  26. class BTree {
  27. private:
  28.     BTreeNode<T, ORDER>* root; // Pointer to root node
  29.  
  30.     // Function to split a full child node
  31.     void splitChild(BTreeNode<T, ORDER>* x, int i) {
  32.         BTreeNode<T, ORDER>* y = x->children[i];
  33.         BTreeNode<T, ORDER>* z = new BTreeNode<T, ORDER>(y->leaf);
  34.         z->n = ORDER / 2 - 1;
  35.  
  36.         for (int j = 0; j < ORDER / 2 - 1; j++)
  37.             z->keys[j] = y->keys[j + ORDER / 2];
  38.  
  39.         if (!y->leaf) {
  40.             for (int j = 0; j < ORDER / 2; j++)
  41.                 z->children[j] = y->children[j + ORDER / 2];
  42.         }
  43.  
  44.         y->n = ORDER / 2 - 1;
  45.  
  46.         for (int j = x->n; j >= i + 1; j--)
  47.             x->children[j + 1] = x->children[j];
  48.  
  49.         x->children[i + 1] = z;
  50.  
  51.         for (int j = x->n - 1; j >= i; j--)
  52.             x->keys[j + 1] = x->keys[j];
  53.  
  54.         x->keys[i] = y->keys[ORDER / 2 - 1];
  55.         x->n = x->n + 1;
  56.     }
  57.  
  58.     // Function to insert a key in a non-full node
  59.     void insertNonFull(BTreeNode<T, ORDER>* x, T k) {
  60.         int i = x->n - 1;
  61.  
  62.         if (x->leaf) {
  63.             while (i >= 0 && k < x->keys[i]) {
  64.                 x->keys[i + 1] = x->keys[i];
  65.                 i--;
  66.             }
  67.  
  68.             x->keys[i + 1] = k;
  69.             x->n = x->n + 1;
  70.         } else {
  71.             while (i >= 0 && k < x->keys[i])
  72.                 i--;
  73.  
  74.             i++;
  75.             if (x->children[i]->n == ORDER - 1) {
  76.                 splitChild(x, i);
  77.  
  78.                 if (k > x->keys[i])
  79.                     i++;
  80.             }
  81.             insertNonFull(x->children[i], k);
  82.         }
  83.     }
  84.  
  85.     // Function to traverse the tree
  86.     void traverse(BTreeNode<T, ORDER>* x) {
  87.         int i;
  88.         for (i = 0; i < x->n; i++) {
  89.             if (!x->leaf)
  90.                 traverse(x->children[i]);
  91.             cout << " " << x->keys[i];
  92.         }
  93.  
  94.         if (!x->leaf)
  95.             traverse(x->children[i]);
  96.     }
  97.  
  98.     // Function to search a key in the tree
  99.     BTreeNode<T, ORDER>* search(BTreeNode<T, ORDER>* x, T k) {
  100.         int i = 0;
  101.         while (i < x->n && k > x->keys[i])
  102.             i++;
  103.  
  104.         if (i < x->n && k == x->keys[i])
  105.             return x;
  106.  
  107.         if (x->leaf)
  108.             return nullptr;
  109.  
  110.         return search(x->children[i], k);
  111.     }
  112.  
  113.     // Function to find the predecessor
  114.     T getPredecessor(BTreeNode<T, ORDER>* node, int idx) {
  115.         BTreeNode<T, ORDER>* current = node->children[idx];
  116.         while (!current->leaf)
  117.             current = current->children[current->n];
  118.         return current->keys[current->n - 1];
  119.     }
  120.  
  121.     // Function to find the successor
  122.     T getSuccessor(BTreeNode<T, ORDER>* node, int idx) {
  123.         BTreeNode<T, ORDER>* current = node->children[idx + 1];
  124.         while (!current->leaf)
  125.             current = current->children[0];
  126.         return current->keys[0];
  127.     }
  128.  
  129.     // Function to fill child node
  130.     void fill(BTreeNode<T, ORDER>* node, int idx) {
  131.         if (idx != 0 && node->children[idx - 1]->n >= ORDER / 2)
  132.             borrowFromPrev(node, idx);
  133.         else if (idx != node->n && node->children[idx + 1]->n >= ORDER / 2)
  134.             borrowFromNext(node, idx);
  135.         else {
  136.             if (idx != node->n)
  137.                 merge(node, idx);
  138.             else
  139.                 merge(node, idx - 1);
  140.         }
  141.     }
  142.  
  143.     // Function to borrow from previous sibling
  144.     void borrowFromPrev(BTreeNode<T, ORDER>* node, int idx) {
  145.         BTreeNode<T, ORDER>* child = node->children[idx];
  146.         BTreeNode<T, ORDER>* sibling = node->children[idx - 1];
  147.  
  148.         for (int i = child->n - 1; i >= 0; --i)
  149.             child->keys[i + 1] = child->keys[i];
  150.  
  151.         if (!child->leaf) {
  152.             for (int i = child->n; i >= 0; --i)
  153.                 child->children[i + 1] = child->children[i];
  154.         }
  155.  
  156.         child->keys[0] = node->keys[idx - 1];
  157.  
  158.         if (!child->leaf)
  159.             child->children[0] = sibling->children[sibling->n];
  160.  
  161.         node->keys[idx - 1] = sibling->keys[sibling->n - 1];
  162.  
  163.         child->n += 1;
  164.         sibling->n -= 1;
  165.     }
  166.  
  167.     // Function to borrow from next sibling
  168.     void borrowFromNext(BTreeNode<T, ORDER>* node, int idx) {
  169.         BTreeNode<T, ORDER>* child = node->children[idx];
  170.         BTreeNode<T, ORDER>* sibling = node->children[idx + 1];
  171.  
  172.         child->keys[child->n] = node->keys[idx];
  173.  
  174.         if (!child->leaf)
  175.             child->children[child->n + 1] = sibling->children[0];
  176.  
  177.         node->keys[idx] = sibling->keys[0];
  178.  
  179.         for (int i = 1; i < sibling->n; ++i)
  180.             sibling->keys[i - 1] = sibling->keys[i];
  181.  
  182.         if (!sibling->leaf) {
  183.             for (int i = 1; i <= sibling->n; ++i)
  184.                 sibling->children[i - 1] = sibling->children[i];
  185.         }
  186.  
  187.         child->n += 1;
  188.         sibling->n -= 1;
  189.     }
  190.  
  191.     // Function to merge two nodes
  192.     void merge(BTreeNode<T, ORDER>* node, int idx) {
  193.         BTreeNode<T, ORDER>* child = node->children[idx];
  194.         BTreeNode<T, ORDER>* sibling = node->children[idx + 1];
  195.  
  196.         child->keys[ORDER / 2 - 1] = node->keys[idx];
  197.  
  198.         for (int i = 0; i < sibling->n; ++i)
  199.             child->keys[i + ORDER / 2] = sibling->keys[i];
  200.  
  201.         if (!child->leaf) {
  202.             for (int i = 0; i <= sibling->n; ++i)
  203.                 child->children[i + ORDER / 2] = sibling->children[i];
  204.         }
  205.  
  206.         for (int i = idx + 1; i < node->n; ++i)
  207.             node->keys[i - 1] = node->keys[i];
  208.  
  209.         for (int i = idx + 2; i <= node->n; ++i)
  210.             node->children[i - 1] = node->children[i];
  211.  
  212.         child->n += sibling->n + 1;
  213.         node->n--;
  214.  
  215.         delete sibling;
  216.     }
  217.  
  218.     // Function to remove a key from a non-leaf node
  219.     void removeFromNonLeaf(BTreeNode<T, ORDER>* node, int idx) {
  220.         T k = node->keys[idx];
  221.  
  222.         if (node->children[idx]->n >= ORDER / 2) {
  223.             T pred = getPredecessor(node, idx);
  224.             node->keys[idx] = pred;
  225.             remove(node->children[idx], pred);
  226.         } else if (node->children[idx + 1]->n >= ORDER / 2) {
  227.             T succ = getSuccessor(node, idx);
  228.             node->keys[idx] = succ;
  229.             remove(node->children[idx + 1], succ);
  230.         } else {
  231.             merge(node, idx);
  232.             remove(node->children[idx], k);
  233.         }
  234.     }
  235.  
  236.     // Function to remove a key from a leaf node
  237.     void removeFromLeaf(BTreeNode<T, ORDER>* node, int idx) {
  238.         for (int i = idx + 1; i < node->n; ++i)
  239.             node->keys[i - 1] = node->keys[i];
  240.  
  241.         node->n--;
  242.     }
  243.  
  244.     // Function to remove a key from the tree
  245.     void remove(BTreeNode<T, ORDER>* node, T k) {
  246.         int idx = 0;
  247.         while (idx < node->n && node->keys[idx] < k)
  248.             ++idx;
  249.  
  250.         if (idx < node->n && node->keys[idx] == k) {
  251.             if (node->leaf)
  252.                 removeFromLeaf(node, idx);
  253.             else
  254.                 removeFromNonLeaf(node, idx);
  255.         } else {
  256.             if (node->leaf) {
  257.                 cout << "The key " << k << " is not present in the tree\n";
  258.                 return;
  259.             }
  260.  
  261.             bool flag = ((idx == node->n) ? true : false);
  262.  
  263.             if (node->children[idx]->n < ORDER / 2)
  264.                 fill(node, idx);
  265.  
  266.             if (flag && idx > node->n)
  267.                 remove(node->children[idx - 1], k);
  268.             else
  269.                 remove(node->children[idx], k);
  270.         }
  271.     }
  272.  
  273. public:
  274.     BTree() { root = new BTreeNode<T, ORDER>(true); }
  275.  
  276.     // Function to insert a key in the tree
  277.     void insert(T k) {
  278.         if (root->n == ORDER - 1) {
  279.             BTreeNode<T, ORDER>* s = new BTreeNode<T, ORDER>(false);
  280.             s->children[0] = root;
  281.             root = s;
  282.             splitChild(s, 0);
  283.             insertNonFull(s, k);
  284.         } else
  285.             insertNonFull(root, k);
  286.     }
  287.  
  288.     // Function to traverse the tree
  289.     void traverse() {
  290.         if (root != nullptr)
  291.             traverse(root);
  292.     }
  293.  
  294.     // Function to search a key in the tree
  295.     BTreeNode<T, ORDER>* search(T k) {
  296.         return (root == nullptr) ? nullptr : search(root, k);
  297.     }
  298.  
  299.     // Function to remove a key from the tree
  300.     void remove(T k) {
  301.         if (!root) {
  302.             cout << "The tree is empty\n";
  303.             return;
  304.         }
  305.  
  306.         remove(root, k);
  307.  
  308.         if (root->n == 0) {
  309.             BTreeNode<T, ORDER>* tmp = root;
  310.             if (root->leaf)
  311.                 root = nullptr;
  312.             else
  313.                 root = root->children[0];
  314.  
  315.             delete tmp;
  316.         }
  317.     }
  318. };
  319.  
  320. int main() {
  321.     BTree<int, 3> t;
  322.  
  323.     t.insert(10);
  324.     t.insert(20);
  325.     t.insert(5);
  326.     t.insert(6);
  327.     t.insert(12);
  328.     t.insert(30);
  329.     t.insert(7);
  330.     t.insert(17);
  331.  
  332.     cout << "Traversal of the constructed tree is: ";
  333.     t.traverse();
  334.     cout << endl;
  335.  
  336.     int k = 6;
  337.     (t.search(k) != nullptr) ? cout << k << " is found" << endl
  338.                              : cout << k << " is not found" << endl;
  339.  
  340.     k = 15;
  341.     (t.search(k) != nullptr) ? cout << k << " is found" << endl
  342.                              : cout << k << " is not found" << endl;
  343.  
  344.     t.remove(6);
  345.     cout << "Traversal of the tree after removing 6: ";
  346.     t.traverse();
  347.     cout << endl;
  348.  
  349.     t.remove(13);
  350.     cout << "Traversal of the tree after removing 13: ";
  351.     t.traverse();
  352.     cout << endl;
  353.  
  354.  
  355.  
  356.     return 0;
  357. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Traversal of the constructed tree is:  5 7 17
6 is not found
15 is not found
The key 6 is not present in the tree
Traversal of the tree after removing 6:  5 7 17
The key 13 is not present in the tree
Traversal of the tree after removing 13:  5 7 17
https://ideone.com/4T1fC3
language:
C++ (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!