जावास्क्रिप्ट में ट्री में की इंसर्ट करना

नव निर्मित बाइनरी ट्री में पहली इंसर्शन रूट पर एक नोड बनाती है। आगे की इंसर्शन बाइनरी सर्च ट्री के गुण के अनुसार इंसर्ट की जाएंगी कि बाएं चाइल्ड पैरेंट से छोटे होते हैं और दाएं वाले पैरेंट से बड़े होते हैं।

आइए देखते हैं कि हम इस एल्गोरिदम को कोड में कैसे लागू कर सकते हैं:

उदाहरण

insertIter(data) {
    let node = new this.Node(data);
    // जांचें कि ट्री खाली है या नहीं
    if (this.root === null) {
        // पहले एलिमेंट के रूप में इंसर्ट करें
        this.root = node;
        return;
    }
    let currNode = this.root;
    while (true) {
        if (data < currNode.data) {
            // यहां वैल्यू सेट करें क्योंकि हम लीफ नोड पर पहुंच गए हैं
            if (currNode.left === null) {
                currNode.left = node;
                break;
            } else {
                currNode = currNode.left;
            }
        } else {
            // यहां वैल्यू सेट करें क्योंकि हम लीफ नोड पर पहुंच गए हैं
            if (currNode.right === null) {
                currNode.right = node;
                break;
            } else {
                currNode = currNode.right;
            }
        }
    }
}

आइए समझते हैं कि यह फ़ंक्शन कैसे काम करता है। पहले, हम जांचते हैं कि रूट नल है या नहीं जिसका अर्थ है कि ट्री खाली है, अगर हां तो हम नए नोड को रूट असाइन करते हैं और हमारा काम हो गया। अगर नहीं, तो हम एक currNode वेरिएबल बनाते हैं और इसे रूट पर इंगित करते हैं। फिर हम जांचते हैं कि हमारा डेटा currNode से कम है या नहीं, अगर है, तो हम जांचते हैं कि इसका बायां चाइल्ड नल है या नहीं। अगर है तो हम अपना डेटा यहां रखते हैं और बाहर निकल जाते हैं। अन्यथा हम तब तक पुनरावृत्ति करते रहते हैं जब तक हम लीफ पर नहीं पहुंच जाते और अंत में अपना डेटा वहां रख देते हैं।

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

उदाहरण

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

हम इस फ़ंक्शन को रिकर्सिव भी बना सकते हैं। ट्री अंतर्निहित रूप से रिकर्सिव संरचनाएं हैं और हम इस रिकर्सिव गुण का काफी आसानी से उपयोग कर सकते हैं। आइए इंसर्ट के रिकर्सिव वर्जन को देखते हैं:

उदाहरण

insertRec(data) {
    let node = new this.Node(data);
    // जांचें कि ट्री खाली है या नहीं
    if (this.root === null) {
        // पहले एलिमेंट के रूप में इंसर्ट करें
        this.root = node;
    } else {
        insertRecHelper(this.root, node);
    }
}

हमें एक हेल्पर फ़ंक्शन बनाने की आवश्यकता है जो रिकर्स कर सके लेकिन हम उसे क्लास की प्रॉपर्टी के रूप में उजागर नहीं करना चाहते, इसलिए यह फ़ंक्शन क्लास परिभाषा से बाहर होगा।

उदाहरण

function insertRecHelper(root, node) {
    if (node.data < root.data) {
        // यहां वैल्यू सेट करें क्योंकि हम लीफ नोड पर पहुंच गए हैं
        if (root.left === null) {
            root.left = node;
        } else {
            // लेफ्ट सबट्री के साथ इस फ़ंक्शन को रिकर्सिवली कॉल करें
            insertRecHelper(root.left, node);
        }
    } else {
        // यहां वैल्यू सेट करें क्योंकि हम लीफ नोड पर पहुंच गए हैं
        if (root.right === null) {
            root.right = node;
        } else {
            // राइट सबट्री के साथ इस फ़ंक्शन को रिकर्सिवली कॉल करें
            insertRecHelper(root.right, node);
        }
    }
}

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

उदाहरण

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);