मान लीजिए हमारे पास एक बाइनरी सर्च ट्री (BST) है। हमें एक कुंजी k दी जाती है, जिसे BST से हटाकर अपडेटेड BST लौटाना है।
उदाहरण: ट्री [5,3,6,2,4,null,7] से कुंजी 3 हटाने पर ट्री [5,4,6,2,null,null,7] बनता है।
BST डिलीशन एल्गोरिदम
deleteRoot(root)हेल्पर: रूट नोड को हटाता है।- यदि राइट सबट्री नहीं है, तो लेफ्ट सबट्री लौटाएँ।
- इनऑर्डर सक्सेसर (राइट सबट्री का सबसे बायाँ नोड) ढूंढें।
- सक्सेसर का लेफ्ट = रूट का लेफ्ट सेट करें।
- रूट का राइट लौटाएँ।
- मुख्य
deleteNode(root, key):- यदि रूट null है या रूट का मान key है, तो
deleteRoot(root)लौटाएँ। curr = rootसे BST में key ढूंढें।- जब key मिल जाए (पैरेंट के लेफ्ट या राइट में), तो उस चाइल्ड को
deleteRootसे बदलें। - रूट लौटाएँ।
- यदि रूट null है या रूट का मान key है, तो
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) { val = data; left = NULL; right = NULL; }
};
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root || root->val == key) return deleteRoot(root);
TreeNode* curr = root;
while (true) {
int x = curr->val;
if (key < x) {
if (!curr->left || curr->left->val == key) {
curr->left = deleteRoot(curr->left);
break;
}
curr = curr->left;
} else {
if (!curr->right || curr->right->val == key) {
curr->right = deleteRoot(curr->right);
break;
}
curr = curr->right;
}
}
return root;
}
TreeNode* deleteRoot(TreeNode* root) {
if (!root) return NULL;
if (!root->right) return root->left;
TreeNode* x = root->right;
while (x->left) x = x->left;
x->left = root->left;
return root->right;
}
};
int main() {
// ट्री बनाने और टेस्ट करने का कोड
return 0;
}
इनपुट
[5,3,6,2,4,null,7] 3
आउटपुट
[5, 4, 6, 2, null, 7, ]