जावास्क्रिप्ट ट्री में नोड हटाना

ट्री से नोड हटाना दूर से देखने पर काफी जटिल लगता है। नोड हटाते समय 3 केस पर विचार करना होता है। ये निम्न फ़ंक्शन की टिप्पणी में उल्लिखित हैं। जैसा कि हम पहले करते रहे हैं, हम क्लास में एक मेथड और रिकर्सिव कॉल के लिए एक हेल्पर बनाएंगे।

क्लास मेथड

deleteNode(key) {
    // यदि नोड सफलतापूर्वक हटा दिया जाता है, तो एक रेफरेंस प्राप्त होगा।
    return !(deleteNodeHelper(this.root, key) === false);
}

हेल्पर मेथड

/**
 * रूट और की लेता है और की के लिए रिकर्सिवली खोजता है।
 * अगर यह की ढूंढ लेता है, तो 3 केस हो सकते हैं:
 *
 * 1. यह नोड एक लीफ नोड है।
 *
 * उदाहरण: F हटाना
 * A
 * / \
 * B C
 * / / \
 * D E F
 *
 * इसे हटाने के लिए, हम बस इसके पैरेंट के कनेक्शन को इससे हटा सकते हैं।
 *
 * A
 * / \
 * B C
 * / /
 * D E
 *
 * 2. यह नोड ट्री में कहीं बीच में है जिसमें एक चाइल्ड है।
 *
 * उदाहरण: B हटाना
 * A
 * / \
 * B C
 * / / \
 * D E F
 *
 * इसे हटाने के लिए, हम बस चाइल्ड नोड को ऊपर के कनेक्शन में पैरेंट नोड से बदल सकते हैं
 * A
 * / \
 * D C
 * / \
 * E F
 *
 * 3. इस नोड के दोनों चाइल्ड हैं। यह एक मुश्किल केस है।
 *
 * उदाहरण: C हटाना
 *
 * A
 * / \
 * B C
 * / / \
 * D E F
 * / / \
 * G H I
 *
 * इस मामले में, हमें नोड के सक्सेसर या प्रीडिसेसर को ढूंढना होगा और इस नोड को उससे बदलना होगा। उदाहरण के लिए, अगर हम सक्सेसर के साथ जाते हैं, तो उसका सक्सेसर उससे थोड़ा बड़ा एलिमेंट होगा, यानी राइट सबट्री में मिन एलिमेंट। तो डिलीशन के बाद, ट्री इस तरह दिखेगा:
 *
 * A
 * / \
 * B H
 * / / \
 * D E F
 * / \
 * G I
 *
 * इस एलिमेंट को हटाने के लिए, हमें सक्सेसर के पैरेंट को ढूंढना होगा, उनका लिंक तोड़ना होगा, सक्सेसर के लेफ्ट और राइट को करंट नोड के लेफ्ट और राइट पर इंगित करना होगा। आसान तरीका यह है कि डिलीट किए जाने वाले नोड के डेटा को सक्सेसर से बदल दें और सक्सेसर को डिलीट कर दें।
 */
function deleteNodeHelper(root, key) {
    if (root === null) {
        // खाली ट्री
        return false;
    }
    if (key < root.data) {
        root.left = deleteNodeHelper(root.left, key);
        return root;
    } else if (key > root.data) {
        root.right = deleteNodeHelper(root.right, key);
        return root;
    } else {
        // कोई चाइल्ड नहीं
        // केस 1 - एक लीफ नोड
        if (root.left === null && root.right === null) {
            root = null;
            return root;
        }
        // सिंगल चाइल्ड केस
        if (root.left === null) return root.right;
        if (root.right === null) return root.left;
        // दोनों चाइल्ड, इसलिए सक्सेसर ढूंढने की जरूरत है
        let currNode = root.right;
        while (currNode.left !== null) {
            currNode = currNode.left;
        }
        root.data = currNode.data;
        // राइट सबट्री से वैल्यू डिलीट करें।
        root.right = deleteNodeHelper(root.right, currNode.data);
        return root;
    }
}

आप इसका परीक्षण इस तरह कर सकते हैं:

उदाहरण

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
BST.inOrder();
BST.deleteNode(15);
BST.deleteNode(10);
BST.deleteNode(3);
BST.inOrder();

आउटपुट

इससे निम्न आउटपुट मिलेगा:

5 7 12 50