ধরুন আমাদের একটি বাইনারি সার্চ ট্রি আছে। আমরা একটি কী k নেব, এবং আমাদের BST থেকে প্রদত্ত কী k মুছে ফেলতে হবে এবং আপডেট করা BST ফেরত দিতে হবে। তাই গাছটি যদি −
এর মত হয়
এবং কী k =3, তাহলে আউটপুট ট্রি হবে −
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
রুট নোড মুছে ফেলার জন্য deleteRoot() নামে একটি পদ্ধতি নির্ধারণ করুন, এটি নিম্নরূপ কাজ করবে
-
যদি রুট নাল হয়, তাহলে null রিটার্ন করুন
-
যদি root-এর কোন ডান সাবট্রি না থাকে, তাহলে রুটের বাম দিকে ফিরে যান
-
x :=রুটের অভ্যন্তরীণ উত্তরাধিকারী
-
x এর বাম বাম হিসাবে সেট করুন :=রুটের বাম
-
রুটের ডানদিকে ফিরে যান
-
মুছে ফেলার পদ্ধতিটি এরকম হবে
-
যদি রুট নাল হয় বা রুটের মান কী হয়, তাহলে deleteRoot(root)
রিটার্ন করুন -
curr :=root
-
একটি অসীম লুপ তৈরি করুন, এবং নিম্নলিখিতগুলি চালান
-
x :=curr নোডের মান
-
যদি কী
-
যদি curr এর left =নাল বা curr =কী এর বাম মান, তাহলে
-
curr এর বাম :=deleteRoot(curr এর বাম) এবং লুপ থেকে বেরিয়ে আসুন।
-
-
curr :=curr এর বাম
-
-
অন্যথায়
-
যদি curr এর ডান =নাল বা curr এর ডানের মান =কী, তাহলে
-
curr এর ডান:=deleteRoot(curr এর ডান) এবং লুপ থেকে বেরিয়ে আসুন।
-
-
curr :=curr এর ডান
-
-
-
রিটার্ন রুট
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; void insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; } else { q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; } else { q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } void tree_level_trav(TreeNode*root){ if (root == NULL) return; cout << "["; queue<TreeNode *> q; TreeNode *curr; q.push(root); q.push(NULL); while (q.size() > 1) { curr = q.front(); q.pop(); if (curr == NULL){ q.push(NULL); } else { if(curr->left) q.push(curr->left); if(curr->right) q.push(curr->right); if(curr == NULL || curr->val == 0){ cout << "null" << ", "; } else { cout << curr->val << ", "; } } } cout << "]"<<endl; } class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(root == NULL || root->val == key) return deleteRoot(root); TreeNode* curr = root; while(1) { int x = curr->val; if(key < x){ if(curr->left == NULL || curr->left->val == key){ curr->left = deleteRoot(curr->left); break; } curr = curr->left; } else { if(curr->right == NULL || curr->right->val == key){ curr->right = deleteRoot(curr->right); break; } curr = curr->right; } } return root; } TreeNode* deleteRoot(TreeNode* root){ if(!root || root->val == 0)return NULL; if(root->right == NULL) return root->left; TreeNode* x = root->right; while(x->left)x = x->left; x->left = root->left; return root->right; } }; main(){ vector<int> v = {5,3,6,2,4,NULL,7}; TreeNode *root = make_tree(v); Solution ob; tree_level_trav(ob.deleteNode(root, 3)); }
ইনপুট
[5,3,6,2,4,null,7] 3
আউটপুট
[5, 4, 6, 2, null, 7, ]