परिचय
B-ट्री बाइनरी सर्च ट्री का सामान्यीकरण है जिसमें एक नोड में दो से अधिक बच्चे हो सकते हैं। यह एक स्व-संतुलन ट्री डेटा संरचना है जो सॉर्टेड डेटा बनाए रखती है और लॉगरिदमिक समय में क्रमिक पहुंच, खोज, सम्मिलन और विलोपन की अनुमति देती है।
एल्गोरिदम
insert() फ़ंक्शन: रूट को x के रूप में प्रारंभ करें। यदि x लीफ है और इसमें एक और जानकारी के लिए जगह है तो a को x में डालें। अन्यथा यदि x लीफ नहीं है, तो x के उस बच्चे को खोजें जिसे आगे पार करना है। यदि बच्चा भरा नहीं है, तो x को उस बच्चे की ओर इंगित करें। यदि बच्चा भरा है, तो उसे विभाजित करें और x को बच्चे के दो भागों में से एक की ओर इंगित करें। विभाजन के समय बच्चे से एक कुंजी उसके पैरेंट x में ले जाएं।
उदाहरण कोड
#include <iostream>
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];
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 << "डालने के लिए तत्वों की संख्या दर्ज करें\n";
cin >> n;
for (i = 0; i < n; i++) {
cout << "तत्व दर्ज करें\n";
cin >> t;
insert(t);
}
cout << "निर्मित B ट्री का ट्रैवर्सल\n";
traverse(r);
return 0;
}आउटपुट
डालने के लिए तत्वों की संख्या दर्ज करें 7 तत्व दर्ज करें 10 तत्व दर्ज करें 20 तत्व दर्ज करें 30 तत्व दर्ज करें 40 तत्व दर्ज करें 50 तत्व दर्ज करें 60 तत्व दर्ज करें 70 निर्मित B ट्री का ट्रैवर्सल 10 20 30 40 50 60 70
