বাইনারী সার্চ ট্রি (BST) একটি বিশেষ ধরনের গাছ যা নিম্নলিখিত নিয়মগুলি অনুসরণ করে -
-
বাম চাইল্ড নোডের মান সবসময়ই প্যারেন্ট নোটের চেয়ে কম হয়
-
ডান চাইল্ড নোডের প্যারেন্ট নোডের চেয়ে বেশি মূল্য রয়েছে৷
-
সমস্ত নোড পৃথকভাবে একটি বাইনারি অনুসন্ধান গাছ গঠন করে।
একটি বাইনারি অনুসন্ধান গাছের উদাহরণ (BST) −
সার্চ, ন্যূনতম এবং সর্বোচ্চ সন্ধানের মতো ক্রিয়াকলাপের জটিলতা কমাতে একটি বাইনারি অনুসন্ধান ট্রি তৈরি করা হয়েছে৷
অপারেশন বাইনারি সার্চ ট্রি (BST) মুছুন
ডিলিট অপারেশন গাছ থেকে নির্দিষ্ট নোড ড্রপ করছে। নোড মুছে ফেলার ক্ষেত্রে, তিনটি সম্ভাবনা রয়েছে -
-
গাছ থেকে একটি লিফ নোড মুছে ফেলা:সহজতম মুছে ফেলা হল বাইনারি অনুসন্ধান গাছ থেকে একটি পাতার নোড মুছে ফেলা। লিফ নোড মুছে ফেলার জন্য শুধুমাত্র পাতা প্রভাবিত হয়। উদাহরণ,
লিফ নোড 7 মুছে দিলে,
-
একটি চাইল্ড নোড সহ নোড মুছে ফেলা:এই মুছে ফেলার জন্য, আপনাকে মুছে ফেলা নোডের সাথে চাইল্ড নোডটি প্রতিস্থাপন করতে হবে এবং তারপরে এটি মুছে ফেলতে হবে। উদাহরণ,
BST থেকে 2 মুছে ফেলা হচ্ছে
-
দুটি চাইল্ড নোড সহ নোড মুছে ফেলা:এখানে নোডটি মুছে ফেলা হবে দুটি চাইল্ড নোড রয়েছে। সুতরাং, আমরা গাছের ক্রম আকারে ব্যবহার করব, এখানে আমরা উপাদানটি মুছে ফেলব এবং তার স্থানের জন্য তার অভ্যন্তরীণ প্রতিবেশী নির্বাচন করব এবং বাকিটি পুনরায় তৈরি করব। উদাহরণ,
BST থেকে 5 মুছে দিলে নিচের গাছটি ফিরে আসবে।
উদাহরণ
#include#include struct node{int key; struct node *left, *right;};struct node *newNode(int item){struct node *temp =(struct node *)malloc(sizeof(struct node)); temp->কী =আইটেম; temp->left =temp->right =NULL; রিটার্ন temp;}void inordertraversal(struct node *root){ if (root !=NULL){ inordertraversal(root->left); printf("%d", root->কী); inordertraversal(root->ডান); }}struct node* insert(struct node* node, int key){ if (node ==NULL) রিটার্ন newNode(key); যদি (কী <নোড->কী) নোড->বাম =সন্নিবেশ (নোড->বাম, কী); else node->right =insert(node->right, key); রিটার্ন নোড;}স্ট্রাক্ট নোড *মিনভ্যাল্যুনোড(স্ট্রাকট নোড* নোড){স্ট্রাকট নোড* বর্তমান =নোড; যখন (বর্তমান &&বর্তমান->বাম!=শূন্য) বর্তমান =বর্তমান->বাম; রিটার্ন কারেন্ট;}স্ট্রাক্ট নোড* ডিলিট নোড(স্ট্রাক্ট নোড* রুট, int কী){ if (root ==NULL) রিটার্ন রুট; যদি (কী <রুট->কী) রুট->লেফ্ট =ডিলিট নোড(রুট->বাম, কী); অন্যথায় যদি (কী> রুট->কী) রুট->রাইট =ডিলিট নোড(রুট->ডান, কী); else{ if (root->left ==NULL){ struct node *temp =root->right; বিনামূল্যে (মূল); রিটার্ন temp; } else if (root->right ==NULL){ struct node *temp =root->left; বিনামূল্যে (মূল); রিটার্ন temp; } struct node* temp =minValueNode(root->right); root->key =temp->কী; root->right =deleteNode(root->right, temp->key); } return root;}int main(){ struct node *root =NULL; root =insert(root, 50); root =insert(root, 30); root =insert(root, 20); root =insert(root, 40); root =insert(root, 70); root =insert(root, 60); root =insert(root, 80); printf("প্রদত্ত গাছের ইনঅর্ডার ট্রাভার্সাল \n"); inordertraversal(root); printf("\n20 মুছুন\n"); root =deleteNode(root, 20); printf("পরিবর্তিত ট্রির ইনঅর্ডার ট্রাভার্সাল \n"); inordertraversal(root); printf("\n30 মুছুন\n"); root =deleteNode(root, 30); printf("পরিবর্তিত ট্রির ইনঅর্ডার ট্রাভার্সাল \n"); inordertraversal(root); printf("\n50 মুছুন\n"); root =deleteNode(root, 50); printf("পরিবর্তিত ট্রির ইনঅর্ডার ট্রাভার্সাল \n"); inordertraversal(root); রিটার্ন 0;
আউটপুট
প্রদত্ত ট্রির ইনঅর্ডার ট্রাভার্সাল20 30 40 50 60 70 80 মুছুন 20 পরিবর্তিত ট্রির অর্ডার ট্র্যাভার্সাল30 40 50 60 70 80 মুছুন 30 পরিবর্তিত ট্রির ইনঅর্ডার ট্রাভার্সাল 40 50 40 70 80 70 ডিলিট করা
