Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में BST से नोड हटाना


मान लीजिए हमारे पास एक बाइनरी सर्च ट्री (BST) है। हमें एक कुंजी k दी जाती है, जिसे BST से हटाकर अपडेटेड BST लौटाना है।

उदाहरण: ट्री [5,3,6,2,4,null,7] से कुंजी 3 हटाने पर ट्री [5,4,6,2,null,null,7] बनता है।

BST डिलीशन एल्गोरिदम

  1. deleteRoot(root) हेल्पर: रूट नोड को हटाता है।
    • यदि राइट सबट्री नहीं है, तो लेफ्ट सबट्री लौटाएँ।
    • इनऑर्डर सक्सेसर (राइट सबट्री का सबसे बायाँ नोड) ढूंढें।
    • सक्सेसर का लेफ्ट = रूट का लेफ्ट सेट करें।
    • रूट का राइट लौटाएँ।
  2. मुख्य deleteNode(root, key):
    • यदि रूट null है या रूट का मान key है, तो deleteRoot(root) लौटाएँ।
    • curr = root से BST में key ढूंढें।
    • जब key मिल जाए (पैरेंट के लेफ्ट या राइट में), तो उस चाइल्ड को deleteRoot से बदलें।
    • रूट लौटाएँ।

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, ]
  1. C++ में सिमेट्रिक ट्री C++ में सिमेट्रिक ट्री

    मान लीजिए हमारे पास एक बाइनरी ट्री है और कार्य यह जांचना है कि क्या यह स्वयं की समरूपता का निर्माण करता है या नहीं। एक सिमेट्रिक बाइनरी ट्री स्वयं की दर्पण छवि का निर्माण करता है। उदाहरण के लिए इनपुट-1:             आउटपुट: True व्याख्या: चूंकि दिया गया बाइनरी ट्री

  1. C++ में BST में Inorder Successor (द्वितीय संस्करण) C++ में BST में Inorder Successor (द्वितीय संस्करण)

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री में एक नोड है, हमें उस नोड का इन-ऑर्डर सक्सेसर BST में ढूंढना है। यदि कोई इन-ऑर्डर सक्सेसर नहीं है, तो null लौटाएँ। जैसा कि हम जानते हैं कि एक नोड का सक्सेसर वह नोड है जिसका कुंजी मान नोड के मान से सबसे छोटा बड़ा होता है। हमें नोड तक सीधी पहुंच होगी लेकिन ट्र

  1. C++ में BST के प्रत्येक नोड में सभी बड़े मान जोड़ें C++ में BST के प्रत्येक नोड में सभी बड़े मान जोड़ें

    समस्या विवरण एक बाइनरी सर्च ट्री (BST) दी गई है, प्रत्येक नोड को उसके मान और उससे बड़े सभी नोड्स के मानों के योग में बदलें। हल दृष्टिकोण रिवर्स इनऑर्डर ट्रैवर्सल (दाएं → नोड → बाएं) का उपयोग करें और एक चर में अब तक देखे गए नोड्स का योग बनाए रखें। प्रत्येक नोड के लिए, उसका मान वर्तमान योग में जोड़े