বি-ট্রি ব্যবহার করে বাছাই করার জন্য C++ প্রোগ্রাম

এখানে আমরা দেখব কিভাবে B-Tree ব্যবহার করে সাজানো সিকোয়েন্স পেতে হয়। B-বৃক্ষ হল n-ary গাছ। সাজানো ক্রমগুলি পেতে, আমরা একটি বি-ট্রি তৈরি করতে পারি, তারপরে সংখ্যাগুলি যোগ করতে পারি। এখানে বি-ট্রি সর্বোচ্চ 5টি নোড ধরে রাখতে পারে। যদি নোডের সংখ্যা বৃদ্ধি পায়, নোডকে বিভক্ত করুন এবং নতুন স্তর তৈরি করুন। যেহেতু নোডগুলিতে 5 এর মত কিছু সংখ্যক উপাদান রয়েছে (সর্বাধিক), আমরা সেগুলি সাজানোর জন্য বুদ্বুদ সাজানোর কৌশল ব্যবহার করছি। যেহেতু উপাদানের সংখ্যা খুবই কম, তাহলে এটি এর কার্যক্ষমতার উপর খুব বেশি প্রভাব ফেলবে না।

গাছটি অতিক্রম করার পরে, আমরা বিভিন্ন নোডের সমস্ত মান পাব। এই উপাদানগুলি অ-হ্রাস ক্রমে সাজানো হবে৷

অ্যালগরিদম

ট্রাভার্স(p)

ইনপুট:ট্রি নোড পি
আউটপুট:গাছের ট্রাভার্সাল সিকোয়েন্স

 0 থেকে n-1 রেঞ্জের মধ্যে i এর জন্য শুরু করুন, যদি p একটি লিফ নোড না হয় তাহলে করুন, তারপর ট্র্যাভার্স করুন (i পজিশনে p এর সন্তান) শেষ করুন যদি পজিশনে ডেটা প্রিন্ট করা হয় যদি p একটি লিফ নোড না হয়, তারপর ট্রাভার্স (i অবস্থানে p এর সন্তান) শেষ ifEnd

সর্ট(a, n)

ইনপুট অ্যারে নিন, যা সাজানো হবে, সেই অ্যারের উপাদানের সংখ্যা, যা n

আউটপুট:সাজানো অ্যারে

 0 থেকে n-1 রেঞ্জে i এর জন্য শুরু করুন, 0 থেকে n-1 রেঞ্জের j এর জন্য করুন, যদি a[i]> a[j] করেন, তারপর a[i] এবং a[j] শেষ হলে সম্পন্ন করা শেষ 

split_node(x, i):

ইনপুট:নোড x বিভক্ত করা হবে, আমি লিফ নোডের জন্য (-1) হবে, অন্যথায় কিছু ইতিবাচক মান

আউটপুট:বিভক্ত করার পরে নোডের মাঝের উপাদান

শুরু করুন একটি নোড np3 তৈরি করুন, এবং এটিকে লিফ নোড হিসাবে চিহ্নিত করুন যদি i -1 হয়, তারপরে মধ্য :=x এর অবস্থান 2 থেকে ডেটা x-এর অবস্থান 2-এ ডেটা সেট করুন x-এ ডেটা সংখ্যা 1 দ্বারা হ্রাস করুন np1 নামে একটি নতুন নোড তৈরি করুন এবং এটিকে নন-লিফ নোড হিসাবে চিহ্নিত করুন x লিফ নোড হিসাবে চিহ্নিত করুন x এর সমস্ত নোড 3 থেকে 5 অবস্থান থেকে np3 তে সন্নিবেশ করুন এছাড়াও np3 তে অবস্থান 3 থেকে 5 পর্যন্ত x এর সমস্ত চাইল্ড রেফারেন্স সন্নিবেশ করুন। নোড থেকে সন্নিবেশিত উপাদানগুলিকে সরিয়ে ফেলুন x np1-এর প্রথম অবস্থানের মধ্যবর্তী স্থানে X-কে বাম সন্তান এবং np3-এর ডান সন্তান হিসাবে np1-এর উপাদান সংখ্যা বৃদ্ধি করুন এবং এটিকে রুট হিসাবে করুন। else y :=সাবট্রি লোকেশন i mid :=y এর অবস্থান 2 থেকে ডেটা y এর 2 পজিশনে ডেটা সেট করুন y থেকে 0 এ y এর ডেটা সংখ্যা 1 দ্বারা কমিয়ে 3 থেকে 5 অবস্থানের মধ্যে y এর সমস্ত নোড সন্নিবেশ করুন np3 np3-এর উপাদান সংখ্যা বাড়ায়, এবং y থেকে সন্নিবেশিত উপাদানগুলি সরিয়ে দেয় i অবস্থানে y চাইল্ড যোগ করে, এবং i+1 শেষে np3 যোগ করে ifEnd

ঢোকান(a):

ইনপুট:একটি উপাদান a, যা সন্নিবেশ করা হবে।

আউটপুট:আপডেট করা বি-ট্রি

শুরু করুন x :=রুট যদি x নাল হয়, তারপর একটি রুট নোড তৈরি করুন এবং x এ রুট নিন অন্যথা x যদি লিফ নোড হয় এবং এতে 5টি উপাদান থাকে, তাহলে temp_node :=split_child(x, -1) x :=root i :=x ঢোকাতে সঠিক অবস্থান খুঁজুন :=স্প্লিট_চাইল্ড(x, i) x->n এর অবস্থানে temp_node ডেটা যোগ করুন x else x :=চাইল্ড অব x অবস্থানে i শেষ হলে শেষ হয় যদি শেষ হয় তাহলে x এ x->n অবস্থানে x->n সাজানোর উপাদান যোগ করুন 

উদাহরণ কোড

#includeনেমস্পেস ব্যবহার করে std;struct BTreeNode//একটি B-tree int *data এর একটি নোড গঠন তৈরি করুন; BTreeNode **child_ptr; বুল পাতা; int n;}*root =NULL, *np =NULL, *x =NULL;BTreeNode * getNode(){ int i; np =নতুন BTreeNode; np->ডেটা =নতুন int[5]; // পাঁচটি ডেটা ফিয়েল সেট করুন এবং 6 টি লিঙ্ক ফিল্ড np->child_ptr =নতুন BTreeNode *[6]; np->পাতা =সত্য; //প্রাথমিকভাবে নোডটি একটি পাতা np->n =0; জন্য (i =0; i <6; i++) { np->child_ptr[i] =NULL; //শুরুতে সমস্ত পয়েন্টার চালু করুন } রিটার্ন np;} void traverse(BTreeNode *p) { cout<n; i++) { //পুনরাবৃত্তভাবে পুরো বি-গাছটি অতিক্রম করুন যদি (p->পাতা ==মিথ্যা){ ট্রাভার্স(p->child_ptr[i]); } cout <<" " <ডেটা[i]; } যদি (p->পাতা ==মিথ্যা) { traverse(p->child_ptr[i]); } cout< p[j]){ swap(p[i], p[j]); } } }}int split_child(BTreeNode *x, int i){ //নোডটিকে তিনটি নোডে বিভক্ত করুন, একটি রুট এবং দুটি শিশু int মধ্যম; BTreeNode *np1, *np3, *y; np3 =getNode(); // np3 np3 নামে একটি নতুন লিফ নোড তৈরি করুন->পাতা =সত্য; যদি (i ==-1) { মধ্য =x->ডেটা[2]; // মধ্যম উপাদান x->ডেটা[2] =0 পান; x->n--; np1 =getNode(); np1->পাতা =মিথ্যা; x->পাতা =সত্য; (int j =3; j <5; j++) { np3->ডেটা[j - 3] =x->ডেটা[j]; np3->child_ptr[j - 3] =x->child_ptr[j]; np3->n++; x->ডেটা[j] =0; x->n--; } এর জন্য (int j =0; j <6; j++) { x->child_ptr[j] =NULL; } np1->ডেটা[0] =মধ্য; np1->child_ptr[np1->n] =x; np1->child_ptr[np1->n + 1] =np3; np1->n++; root =np1; } অন্য { y =x->child_ptr[i]; মধ্য =y->ডেটা[2]; y->ডেটা[2] =0; y->n--; (int j =3; j <5; j++) { np3->ডেটা[j - 3] =y->ডেটা[j]; np3->n++; y->ডেটা[j] =0; y->n--; } x->child_ptr[i] =y; x->child_ptr[i + 1] =np3; } রিটার্ন মিড;} void insert(int a){ // Insert in BTree int i, tmp_node; x =root; যদি (x ==NULL) { root =getNode(); x =root; } else { if (x->leaf ==true &&x->n ==5){ // যখন নোডটি একটি লিফ নোড এবং এতে 5 ডেটা থাকে tmp_node =split_child(x, -1); // নোড x =রুট বিভক্ত করে একটি নতুন স্তর তৈরি করুন; (i =0; i <(x->n); i++) { যদি (a> x->ডেটা[i]) &&(a ডেটা[i + 1])) { i++; বিরতি } অন্যথায় যদি (a ডেটা[0]) { বিরতি; } অন্য { চালিয়ে যান; } } x =x->child_ptr[i]; } অন্য { যখন (x->পাতা ==মিথ্যা) { (i =0; i <(x->n); i++) { যদি (a> x->ডেটা[i]) &&(a ডেটা[i + 1])) { i++; বিরতি } অন্যথায় যদি (a ডেটা[0]) { বিরতি; } অন্য { চালিয়ে যান; } } যদি ((x->child_ptr[i])->n ==5) { tmp_node =split_child(x, i); x->ডেটা[x->n] =tmp_node; x->n++; চালিয়ে যাওয়া } অন্য { x =x->child_ptr[i]; } } } } x->ডেটা[x->n] =a; sort(x->ডেটা, x->n); x->n++;}int main() { int i, n, t; cout<<"ঢোকানো উপাদানের সংখ্যা লিখুন\n"; cin>>n; for(i =0; i >t; সন্নিবেশ (টি); } cout<<"গঠিত গাছের ট্রাভার্সাল\n"; traverse(root);}

আউটপুট

ঢোকাতে হবে উপাদানের সংখ্যা লিখুন8 উপাদানটি প্রবেশ করুন54 উপাদানটি প্রবেশ করুন23 উপাদানটি প্রবেশ করুন98 উপাদানটি প্রবেশ করুন52 উপাদানটি প্রবেশ করুন10 উপাদানটি 23টি উপাদানটি প্রবেশ করান47টি উপাদানটি প্রবেশ করান