Untitled

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// A BTree node
class BTreeNode {
    int *keys;     // An array of keys
    int t;         // Minimum degree (defines the range for number of keys)
    BTreeNode **C; // An array of child pointers
    int n;         // Current number of keys
    bool leaf;     // Is true when the node is a leaf. Otherwise false

public:
    BTreeNode(int _t, bool _leaf);   // Constructor

    // A function to traverse all nodes in a subtree rooted with this node
    void traverse();

    // A function to search a key in subtree rooted with this node.
    BTreeNode *search(int k);   // returns NULL if k is not present.

    // A function that returns the index of the first key that is greater or equal to k
    int findKey(int k);

    // A function to remove the key k from the sub-tree rooted with this node
    void remove(int k);

    // A function to remove the key present in idx-th position in this node which is a leaf
    void removeFromLeaf(int idx);

    // A function to remove the key present in idx-th position in this node which is not a leaf
    void removeFromNonLeaf(int idx);

    // A function to get the predecessor of the key- where the key is present in the idx-th position in the node
    int getPred(int idx);

    // A function to get the successor of the key- where the key is present in the idx-th position in the node
    int getSucc(int idx);

    // A function to fill up the child node present in the idx-th position in the C array if that child has less than t-1 keys
    void fill(int idx);

    // A function to borrow a key from the previous child and insert it into C[idx]
    void borrowFromPrev(int idx);

    // A function to borrow a key from the next child and insert it into C[idx]
    void borrowFromNext(int idx);

    // A function to merge idx-th child of the node with (idx+1)th child of the node
    void merge(int idx);

    // Make BTree a friend so that we can access private members of this class in BTree functions
    friend class BTree;
};

// A BTree
class BTree {
    BTreeNode *root; // Pointer to root node
    int t;           // Minimum degree
public:
    // Constructor (Initializes tree as empty)
    BTree(int _t) {
        root = NULL;
        t = _t;
    }

    // function to traverse the tree
    void traverse() {
        if (root != NULL) root->traverse();
    }

    // function to search a key in this tree
    BTreeNode* search(int k) {
        return (root == NULL) ? NULL : root->search(k);
    }

    // The main function that inserts a new key in this B-Tree
    void insert(int k);

    // The main function that removes a new key in this B-Tree
    void remove(int k);
};

// Constructor for BTreeNode class
BTreeNode::BTreeNode(int t1, bool leaf1) {
    // Copy the given minimum degree and leaf property
    t = t1;
    leaf = leaf1;

    // Allocate memory for maximum number of possible keys
    // and child pointers
    keys = new int[2 * t - 1];
    C = new BTreeNode *[2 * t];

    // Initialize the number of keys as 0
    n = 0;
}

// Function to traverse all nodes in a subtree rooted with this node
void BTreeNode::traverse() {
    // There are n keys and n+1 children, traverse through n keys
    // and first n children
    int i;
    for (i = 0; i < n; i++) {
        // If this is not leaf, then before printing keys[i],
        // traverse the subtree rooted with child C[i].
        if (leaf == false)
            C[i]->traverse();
        cout << keys[i] << " ";
    }

    // Print the subtree rooted with last child
    if (leaf == false)
        C[i]->traverse();
}

// Function to search key k in subtree rooted with this node
BTreeNode *BTreeNode::search(int k) {
    // Find the first key greater than or equal to k
    int i = 0;
    while (i < n && k > keys[i])
        i++;

    // If the found key is equal to k, return this node
    if (keys[i] == k)
        return this;

    // If the key is not found here and this is a leaf node
    if (leaf == true)
        return NULL;

    // Go to the appropriate child
    return C[i]->search(k);
}

// The main function that inserts a new key in this B-Tree
void BTree::insert(int k) {
    // If tree is empty
    if (root == NULL) {
        // Allocate memory for root
        root = new BTreeNode(t, true);
        root->keys[0] = k;  // Insert key
        root->n = 1;  // Update number of keys in root
    }
    else {  // If tree is not empty
        // If root is full, then tree grows in height
        if (root->n == 2 * t - 1) {
            // Allocate memory for new root
            BTreeNode *s = new BTreeNode(t, false);

            // Make old root as child of new root
            s->C[0] = root;

            // Split the old root and move a key to the new root
            s->splitChild(0, root);

            // New root has two children now. Decide which of the
            // two children is going to have new key
            int i = 0;
            if (s->keys[0] < k)
                i++;
            s->C[i]->insertNonFull(k);

            // Change root
            root = s;
        }
        else  // If root is not full, call insertNonFull for root
            root->insertNonFull(k);
    }
}

// Function to remove a key k from the tree
void BTree::remove(int k) {
    if (!root) {
        cout << "The tree is empty\n";
        return;
    }

    // Call the remove function for root
    root->remove(k);

    // If the root node has 0 keys, make its first child as the new root
    // if it has a child, otherwise set root as NULL
    if (root->n == 0) {
        BTreeNode *tmp = root;
        if (root->leaf)
            root = NULL;
        else
            root = root->C[0];

        delete tmp;
    }
    return;
}

int main() {
    BTree t(3);  // A B-Tree with minimum degree 3

    // Sample input insertion
    int arr[10] = {10, 20, 5, 6, 12, 30, 7, 17, 2, 3};
    int to_delete = 12;

    // Insert the elements
    for (int i = 0; i < 10; i++) {
        t.insert(arr[i]);
    }

    // Print the B-tree before deletion
    cout << "B-tree before deletion: ";
    t.traverse();
    cout << endl;

    // Perform deletion
    t.remove(to_delete);

    // Print the B-tree after deletion
    cout << "B-tree after deletion: ";
    t.traverse();
    cout << endl;

    return 0;
}