C++ প্রোগ্রাম: B ট্রি বাস্তবায়ন

B-ট্রি হল বাইনারি সার্চ ট্রির একটি জেনারালাইজেশন যেখানে একটি নোডে দুইটির বেশি চাইল্ড থাকতে পারে। এটি মূলত একটি সেলফ-ব্যালেন্সিং ট্রি ডেটা স্ট্রাকচার যা সোর্টেড ডেটা রক্ষা করে এবং সিকোয়েন্সিয়াল অ্যাক্সেস, সার্চ, ইনসার্শন এবং ডিলিশন লগারিদমিক টাইমে করতে দেয়।

নিচে অর্ডার 6-এর B ট্রি বাস্তবায়নের একটি C++ প্রোগ্রাম দেওয়া হলো।

শুরু
  insert() ফাংশন ট্রিতে নোড ইনসার্ট করতে:
    x কে রুট হিসেবে ইনিশিয়ালাইজ করুন।
    যদি x ليف হয় এবং একটা আরো ইনফোর জন্য জায়গা থাকে, a কে x-এ ইনসার্ট করুন।
    অন্যথায় যদি x ليف না হয়, তবে
      x-এর চাইল্ড খুঁজুন যা নেক্সট ট্রভার্স হবে।
      যদি চাইল্ড ফুল না হয়, x কে চাইল্ডকে পয়েন্ট করতে পরিবর্তন করুন।
      যদি চাইল্ড ফুল হয়, এটিকে স্প্লিট করুন এবং x কে চাইল্ডের দুটি অংশের একটিকে পয়েন্ট করতে পরিবর্তন করুন। যদি a চাইল্ডের মিড কী থেকে ছোট হয়, x কে চাইল্ডের প্রথম অংশ হিসেবে সেট করুন। অন্যথায় দ্বিতীয় অংশ।
      চাইল্ড স্প্লিট করার সময়, একটি কী চাইল্ড থেকে তার পেরেন্ট x-এ মুভ করুন।
শেষ

#include 
using namespace std;

struct BTree { // নোড ঘোষণা
    int *d;
    BTree **child_ptr;
    bool l;
    int n;
} *r = NULL, *np = NULL, *x = NULL;

BTree* init() { // নোড তৈরি
    int i; np = new BTree;
    np->d = new int[6]; // অর্ডার 6
    np->child_ptr = new BTree*[7];
    np->l = true; np->n = 0;
    for (i = 0; i < 7; i++) np->child_ptr[i] = NULL;
    return np;
}

void traverse(BTree *p) { // ট্রি ট্রভার্স
    cout << endl; int i;
    for (i = 0; i < p->n; i++) {
        if (p->l == false) traverse(p->child_ptr[i]);
        cout << " " << p->d[i];
    }
    if (p->l == false) traverse(p->child_ptr[i]);
    cout << endl;
}

void sort(int *p, int n) { // ট্রি সর্ট
    int i, j, t;
    for (i = 0; i < n; i++) {
        for (j = i; j <= n; j++) {
            if (p[i] > p[j]) { t = p[i]; p[i] = p[j]; p[j] = t; }
        }
    }
}

int split_child(BTree *x, int i) {
    int j, mid; BTree *np1, *np3, *y;
    np3 = init(); np3->l = true;
    if (i == -1) {
        mid = x->d[2]; x->d[2] = 0; x->n--;
        np1 = init(); np1->l = false; x->l = true;
        for (j = 3; j < 6; j++) {
            np3->d[j-3] = x->d[j];
            np3->child_ptr[j-3] = x->child_ptr[j];
            np3->n++; x->d[j] = 0; x->n--;
        }
        for (j = 0; j < 6; j++) x->child_ptr[j] = NULL;
        np1->d[0] = mid;
        np1->child_ptr[np1->n] = x;
        np1->child_ptr[np1->n+1] = np3;
        np1->n++; r = np1;
    } else {
        y = x->child_ptr[i];
        mid = y->d[2]; y->d[2] = 0; y->n--;
        for (j = 3; j < 6; j++) {
            np3->d[j-3] = y->d[j]; np3->n++; y->d[j] = 0; y->n--;
        }
        x->child_ptr[i+1] = y; x->child_ptr[i+1] = np3;
    }
    return mid;
}

void insert(int a) {
    int i, t; x = r;
    if (x == NULL) { r = init(); x = r; }
    else {
        if (x->l == true && x->n == 6) {
            t = split_child(x, -1); x = r;
            for (i = 0; i < (x->n); i++) {
                if ((a > x->d[i]) && (a < x->d[i+1])) { i++; break; }
                else if (a < x->d[0]) break;
                else continue;
            }
            x = x->child_ptr[i];
        } else {
            while (x->l == false) {
                for (i = 0; i < (x->n); i++) {
                    if ((a > x->d[i]) && (a < x->d[i+1])) { i++; break; }
                    else if (a < x->d[0]) break;
                    else continue;
                }
                if ((x->child_ptr[i])->n == 6) {
                    t = split_child(x, i); x->d[x->n] = t; x->n++; continue;
                } else x = x->child_ptr[i];
            }
        }
    }
    x->d[x->n] = a; sort(x->d, x->n); x->n++;
}

int main() {
    int i, n, t;
    cout << "enter the no of elements to be inserted\n"; cin >> n;
    for (i = 0; i < n; i++) { cout << "enter the element\n"; cin >> t; insert(t); }
    cout << "traversal of constructed B tree\n"; traverse(r);
}

enter the no of elements to be inserted 7
enter the element 10
enter the element 20
enter the element 30
enter the element 40
enter the element 50
enter the element 60
enter the element 70
traversal of constructed B tree
10 20 30 40 50 60 70