Untitled

#include <iostream>
using namespace std;

// Order of the B-tree
const int ORDER = 3;

// Node structure
class BTreeNode {
public:
    int *keys;           // Array of keys
    int t;               // Minimum degree (defines the range for number of keys)
    BTreeNode **C;       // Array of child pointers
    int n;               // Current number of keys
    bool leaf;           // True if leaf node, otherwise false

    BTreeNode(int _t, bool _leaf);

    // Function to insert a new key in a non-full node
    void insertNonFull(int k);

    // Function to split the child y of this node
    void splitChild(int i, BTreeNode *y);

    // Function to search a key in the subtree rooted with this node
    BTreeNode *search(int k);

    // A utility function to display the tree structure
    void display();
};

// A BTree class
class BTree {
public:
    BTreeNode *root; // Pointer to root node
    int t;           // Minimum degree

    BTree(int _t) {
        root = NULL;
        t = _t;
    }

    // Function to search a key in the 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);

    // Function to display the structure of the tree
    void display() {
        if (root != NULL) root->display();
    }
};

// Constructor for BTreeNode class
BTreeNode::BTreeNode(int t1, bool leaf1) {
    t = t1;
    leaf = leaf1;

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

    n = 0;
}

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

    if (keys[i] == k)
        return this;

    if (leaf == true)
        return NULL;

    return C[i]->search(k);
}

// A utility function to display the structure of the tree
void BTreeNode::display() {
    int i;
    for (i = 0; i < n; i++) {
        if (leaf == false)
            C[i]->display();
        cout << " " << keys[i];
    }

    if (leaf == false)
        C[i]->display();
}

// Function to insert a new key in this B-tree
void BTree::insert(int k) {
    if (root == NULL) {
        root = new BTreeNode(t, true);
        root->keys[0] = k;
        root->n = 1;
    } else {
        if (root->n == 2 * t - 1) {
            BTreeNode *s = new BTreeNode(t, false);

            s->C[0] = root;

            s->splitChild(0, root);

            int i = 0;
            if (s->keys[0] < k)
                i++;
            s->C[i]->insertNonFull(k);

            root = s;
        } else
            root->insertNonFull(k);
    }
}

// Function to insert a new key in this node
void BTreeNode::insertNonFull(int k) {
    int i = n - 1;

    if (leaf == true) {
        while (i >= 0 && keys[i] > k) {
            keys[i + 1] = keys[i];
            i--;
        }

        keys[i + 1] = k;
        n = n + 1;
    } else {
        while (i >= 0 && keys[i] > k)
            i--;

        if (C[i + 1]->n == 2 * t - 1) {
            splitChild(i + 1, C[i + 1]);

            if (keys[i + 1] < k)
                i++;
        }
        C[i + 1]->insertNonFull(k);
    }
}

// Function to split the child y of this node
void BTreeNode::splitChild(int i, BTreeNode *y) {
    BTreeNode *z = new BTreeNode(y->t, y->leaf);
    z->n = t - 1;

    for (int j = 0; j < t - 1; j++)
        z->keys[j] = y->keys[j + t];

    if (y->leaf == false) {
        for (int j = 0; j < t; j++)
            z->C[j] = y->C[j + t];
    }

    y->n = t - 1;

    for (int j = n; j >= i + 1; j--)
        C[j + 1] = C[j];

    C[i + 1] = z;

    for (int j = n - 1; j >= i; j--)
        keys[j + 1] = keys[j];

    keys[i] = y->keys[t - 1];

    n = n + 1;
}

int main() {
    BTree t(ORDER);

    int arr[10];
    cout << "Enter 10 unique integer elements: ";
    for (int i = 0; i < 10; i++)
        cin >> arr[i];

    for (int i = 0; i < 10; i++)
        t.insert(arr[i]);

    cout << "B-Tree constructed." << endl;
    cout << "B-Tree structure: ";
    t.display();
    cout << endl;

    int x;
    cout << "Enter the element to search: ";
    cin >> x;

    if (t.search(x) != NULL)
        cout << "Present" << endl;
    else
        cout << "Not Present" << endl;

    return 0;
}