C++ प्रोग्राम: B-Tree का उपयोग करके सॉर्टिंग करना

यहां हम देखेंगे कि B-Tree का उपयोग करके क्रमबद्ध अनुक्रम कैसे प्राप्त करें। B-Tree एक n-ary ट्री है। क्रमबद्ध अनुक्रम प्राप्त करने के लिए, हम एक B-Tree बना सकते हैं, फिर इसमें नंबर जोड़ सकते हैं। यहां B-Tree अधिकतम 5 नोड्स रख सकता है। यदि नोड्स की संख्या बढ़ती है, तो नोड को विभाजित करें और नया स्तर बनाएं। चूंकि नोड्स केवल कुछ एलिमेंट्स (अधिकतम 5) रखते हैं, हम उन्हें सॉर्ट करने के लिए बबल सॉर्टिंग तकनीक का उपयोग कर रहे हैं। चूंकि एलिमेंट्स की संख्या बहुत कम है, इसलिए यह प्रदर्शन को अधिक प्रभावित नहीं करेगा।

ट्री को ट्रैवर्स करने के बाद, हमें विभिन्न नोड्स के सभी मान मिल जाएंगे। ये एलिमेंट्स गैर-घटते क्रम में सॉर्टेड होंगे।

एल्गोरिदम

traverse(p)

इनपुट: ट्री नोड p
आउटपुट: ट्री का ट्रैवर्सल अनुक्रम

Begin
    i को 0 से n-1 तक रेंज में, करें:
        यदि p लीफ नोड नहीं है, तो
            traverse(p के पोजीशन i पर चाइल्ड)
        प्रिंट p के पोजीशन i पर डेटा
    किया
    यदि p लीफ नोड नहीं है, तो
        traverse(p के पोजीशन i पर चाइल्ड)
    किया
End

sort(a, n)

इनपुट: सरणी a जिसे सॉर्ट किया जाएगा, एलिमेंट्स की संख्या n
आउटपुट: सॉर्टेड सरणी

Begin
    i को 0 से n-1 तक रेंज में, करें:
        j को 0 से n-1 तक रेंज में, करें:
            यदि a[i] > a[j], तो
                a[i] और a[j] को स्वैप करें
        किया
    किया
End

split_node(x, i):

इनपुट: विभाजित होने वाला नोड x, i लीफ नोड के लिए -1 होगा, अन्यथा कुछ पॉजिटिव मान
आउटपुट: विभाजन के बाद नोड का मध्य एलिमेंट

Begin
    np3 नामक एक नोड बनाएं, और इसे लीफ नोड मार्क करें
    यदि i -1 है, तो
        mid := x के पोजीशन 2 से डेटा
        x के पोजीशन 2 का डेटा 0 पर सेट करें
        x में डेटा की संख्या 1 से घटाएं
        np1 नामक एक नया नोड बनाएं, और इसे नॉन-लीफ नोड मार्क करें
        x को लीफ नोड मार्क करें
        x के नोड्स को पोजीशन 3 से 5 तक np3 में डालें
        x के चाइल्ड रेफरेंस को भी पोजीशन 3 से 5 तक np3 में डालें
        x से डाले गए एलिमेंट्स हटाएं
        mid को np1 के पहले पोजीशन में डालें
        x को बायां चाइल्ड और np3 को दायां चाइल्ड बनाएं np1 का
        np1 का एलिमेंट काउंट बढ़ाएं, और इसे रूट बनाएं
    अन्यथा
        y := लोकेशन i पर सबट्री
        mid := y के पोजीशन 2 से डेटा
        y के पोजीशन 2 का डेटा 0 पर सेट करें
        y में डेटा की संख्या 1 से घटाएं
        y के नोड्स को पोजीशन 3 से 5 तक np3 में डालें
        np3 का एलिमेंट काउंट बढ़ाएं, और y से डाले गए एलिमेंट्स हटाएं
        y चाइल्ड को पोजीशन i पर जोड़ें, और np3 को पोजीशन i+1 पर जोड़ें
    इफ खत्म
End

insert(a):

इनपुट: एक एलिमेंट a जिसे डाला जाएगा
आउटपुट: अपडेटेड B-Tree

Begin
    x := root
    यदि x नल है, तो
        एक रूट नोड बनाएं और root को x में लें
    अन्यथा
        यदि x लीफ नोड है और इसमें 5 एलिमेंट्स हैं, तो
            temp_node := split_child(x, -1)
            x := root
            a डालने के लिए सही पोजीशन i खोजें
            x := x के पोजीशन i पर चाइल्ड
        अन्यथा
            जब तक x लीफ नोड नहीं है, करें:
                a डालने के लिए सही पोजीशन i खोजें
                यदि x के पोजीशन i पर चाइल्ड में 5 एलिमेंट्स हैं, तो
                    temp_node := split_child(x, i)
                    temp_node डेटा को x के पोजीशन x->n पर जोड़ें
                अन्यथा
                    x := x के पोजीशन i पर चाइल्ड
                इफ खत्म
            किया
        इफ खत्म
    इफ खत्म
    a को x के पोजीशन x->n में डालें
    x के एलिमेंट्स सॉर्ट करें
End

उदाहरण कोड

#include <iostream>
using namespace std;

struct BTreeNode {
    int *data;
    BTreeNode **child_ptr;
    bool leaf;
    int n;
} *root = NULL, *np = NULL, *x = NULL;

BTreeNode* getNode() {
    np = new BTreeNode;
    np->data = new int[5];
    np->child_ptr = new BTreeNode*[6];
    np->leaf = true;
    np->n = 0;
    for (int i = 0; i < 6; i++)
        np->child_ptr[i] = NULL;
    return np;
}

void traverse(BTreeNode *p) {
    cout << endl;
    for (int i = 0; i < p->n; i++) {
        if (!p->leaf)
            traverse(p->child_ptr[i]);
        cout << " " << p->data[i];
    }
    if (!p->leaf)
        traverse(p->child_ptr[p->n]);
    cout << endl;
}

void sort(int *p, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j <= n; j++) {
            if (p[i] > p[j])
                swap(p[i], p[j]);
        }
    }
}

int split_child(BTreeNode *x, int i) {
    int mid;
    BTreeNode *np1, *np3, *y;
    np3 = getNode();
    np3->leaf = true;
    
    if (i == -1) {
        mid = x->data[2];
        x->data[2] = 0;
        x->n--;
        np1 = getNode();
        np1->leaf = false;
        x->leaf = true;
        for (int j = 3; j < 5; j++) {
            np3->data[j-3] = x->data[j];
            np3->child_ptr[j-3] = x->child_ptr[j];
            np3->n++;
            x->data[j] = 0;
            x->n--;
        }
        for (int j = 0; j < 6; j++)
            x->child_ptr[j] = NULL;
        np1->data[0] = mid;
        np1->child_ptr[np1->n] = x;
        np1->child_ptr[np1->n + 1] = np3;
        np1->n++;
        root = np1;
    } else {
        y = x->child_ptr[i];
        mid = y->data[2];
        y->data[2] = 0;
        y->n--;
        for (int j = 3; j < 5; j++) {
            np3->data[j-3] = y->data[j];
            np3->n++;
            y->data[j] = 0;
            y->n--;
        }
        x->child_ptr[i] = y;
        x->child_ptr[i+1] = np3;
    }
    return mid;
}

void insert(int a) {
    int i, tmp_node;
    x = root;
    if (x == NULL) {
        root = getNode();
        x = root;
    } else {
        if (x->leaf && x->n == 5) {
            tmp_node = split_child(x, -1);
            x = root;
            for (i = 0; i < x->n; i++) {
                if ((a > x->data[i]) && (a < x->data[i+1])) {
                    i++; break;
                } else if (a < x->data[0]) {
                    break;
                }
            }
            x = x->child_ptr[i];
        } else {
            while (!x->leaf) {
                for (i = 0; i < x->n; i++) {
                    if ((a > x->data[i]) && (a < x->data[i+1])) {
                        i++; break;
                    } else if (a < x->data[0]) {
                        break;
                    }
                }
                if (x->child_ptr[i]->n == 5) {
                    tmp_node = split_child(x, i);
                    x->data[x->n] = tmp_node;
                    x->n++;
                    continue;
                } else {
                    x = x->child_ptr[i];
                }
            }
        }
    }
    x->data[x->n] = a;
    sort(x->data, x->n);
    x->n++;
}

int main() {
    int n, t;
    cout << "डालने के लिए एलिमेंट्स की संख्या दर्ज करें: ";
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "एलिमेंट दर्ज करें: ";
        cin >> t;
        insert(t);
    }
    cout << "निर्मित ट्री का ट्रैवर्सल:";
    traverse(root);
    return 0;
}

आउटपुट

डालने के लिए एलिमेंट्स की संख्या दर्ज करें: 8
एलिमेंट दर्ज करें: 54
एलिमेंट दर्ज करें: 23
एलिमेंट दर्ज करें: 98
एलिमेंट दर्ज करें: 52
एलिमेंट दर्ज करें: 10
एलिमेंट दर्ज करें: 23
एलिमेंट दर्ज करें: 47
एलिमेंट दर्ज करें: 84
निर्मित ट्री का ट्रैवर्सल:
10 23 23 47 52 54 84 98

टिप्पणी

यह एक शैक्षिक कार्यान्वयन है जो B-Tree के मूल सिद्धांतों को दर्शाता है। उत्पादन कोड के लिए, std::map/std::set (रेड-ब्लैक ट्री) या std::vector + std::sort का उपयोग करें जो अधिक कुशल और परीक्षण किए गए हैं।