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

हम सीख सकते हैं कि AVL ट्री में नोड कैसे इंसर्ट करते हैं। AVL ट्री में इंसर्शन BST के समान ही होते हैं, हमें बस इंसर्ट के दौरान ट्री को बैलेंस करने नामक एक अतिरिक्त चरण करने की आवश्यकता होती है जब भी हम ट्री में नीचे जाते हैं।

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

हम फिर से रिकर्सिव कॉल के लिए एक क्लास मेथड और एक हेल्पर फ़ंक्शन बनाते हैं:

उदाहरण

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

हेल्पर मेथड

function insertHelper(self, root, node) {
    if (root === null) {
        root = node;
    } else if (node.data < root.data) {
        // बाएं जाएं!
        root.left = insertHelper(self, root.left, node);
        // बैलेंस फैक्टर की जांच करें और उपयुक्त रोटेशन करें
        if (root.left !== null && self.getBalanceFactor(root) > 1) {
            if (node.data > root.left.data) {
                root = rotationLL(root);
            } else {
                root = rotationLR(root);
            }
        }
    } else if (node.data > root.data) {
        // दाएं जाएं!
        root.right = insertHelper(self, root.right, node);
        // बैलेंस फैक्टर की जांच करें और उपयुक्त रोटेशन करें
        if (root.right !== null && self.getBalanceFactor(root) < -1) {
            if (node.data > root.right.data) {
                root = rotationRR(root);
            } else {
                root = rotationRL(root);
            }
        }
    }
    return root;
}

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

उदाहरण

let AVL = new AVLTree();
AVL.insert(10);
AVL.insert(15);
AVL.insert(5);
AVL.insert(50);
AVL.insert(3);
AVL.insert(7);
AVL.insert(12);
AVL.inOrder();

आउटपुट

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

3 5 7 10 12 15 50