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

स्वयं को बैलेंस करने के लिए, एक AVL ट्री निम्नलिखित चार प्रकार के रोटेशन कर सकता है:

• लेफ्ट रोटेशन
• राइट रोटेशन
• लेफ्ट-राइट रोटेशन
• राइट-लेफ्ट रोटेशन

पहले दो रोटेशन सिंगल रोटेशन हैं और अगले दो डबल रोटेशन हैं। एक अनबैलेंस्ड ट्री होने के लिए, हमें कम से कम ऊंचाई 2 के ट्री की आवश्यकता होती है। इस सरल ट्री के साथ, आइए उन्हें एक-एक करके समझते हैं।

लेफ्ट रोटेशन

यदि एक ट्री अनबैलेंस्ड हो जाता है, जब एक नोड को राइट सबट्री के राइट सबट्री में इंसर्ट किया जाता है, तो हम एक सिंगल लेफ्ट रोटेशन करते हैं:

हमारे उदाहरण में, नोड A अनबैलेंस्ड हो गया है क्योंकि A के राइट सबट्री के राइट सबट्री में एक नोड इंसर्ट किया गया है। हम A को B का लेफ्ट-सबट्री बनाकर लेफ्ट रोटेशन करते हैं। इस रोटेशन को LL रोटेशन भी कहा जाता है। आइए देखते हैं कि हम इसे कैसे लागू कर सकते हैं:

function rotationLL(node) {
    let tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
}

राइट रोटेशन

AVL ट्री अनबैलेंस्ड हो सकता है अगर एक नोड को लेफ्ट सबट्री के लेफ्ट सबट्री में इंसर्ट किया जाता है। ट्री को तब राइट रोटेशन की आवश्यकता होती है।

चित्रण के अनुसार, अनबैलेंस्ड नोड राइट रोटेशन करके अपने लेफ्ट चाइल्ड का राइट चाइल्ड बन जाता है। इसे RR रोटेशन भी कहा जाता है। आइए देखते हैं कि यह कोड में कैसा दिखता है:

function rotationRR(node) {
    let tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    return tmp;
}

लेफ्ट-राइट रोटेशन

डबल रोटेशन पहले से समझाए गए रोटेशन के थोड़े जटिल वर्जन हैं। उन्हें बेहतर ढंग से समझने के लिए, हमें रोटेशन के दौरान किए गए प्रत्येक एक्शन पर ध्यान देना चाहिए। आइए पहले देखते हैं कि लेफ्ट-राइट रोटेशन कैसे किया जाता है। लेफ्ट-राइट रोटेशन लेफ्ट रोटेशन के बाद राइट रोटेशन का संयोजन है।

स्टेट	एक्शन
	एक नोड को लेफ्ट सबट्री के राइट सबट्री में इंसर्ट किया गया है। यह C को अनबैलेंस्ड नोड बनाता है। ये परिदृश्य AVL ट्री को लेफ्ट-राइट रोटेशन करने का कारण बनते हैं।
	हम पहले C के लेफ्ट सबट्री पर लेफ्ट रोटेशन करते हैं। यह A को B का लेफ्ट सबट्री बनाता है।
	नोड C अभी भी अनबैलेंस्ड है, हालांकि अब यह लेफ्ट-सबट्री के लेफ्ट-सबट्री के कारण है।
	अब हम ट्री को राइट-रोटेट करेंगे, जिससे B इस सबट्री का नया रूट नोड बन जाएगा। C अब अपने लेफ्ट सबट्री का राइट सबट्री बन जाता है।
	ट्री अब बैलेंस्ड है।

इसे LR रोटेशन भी कहा जाता है क्योंकि हम पहले लेफ्ट रोटेशन और फिर राइट रोटेशन करते हैं। इसे पिछले 2 मेथड्स का उपयोग करके इस तरह लागू किया जा सकता है:

function rotationLR(node) {
    node.left = rotationRR(node.left);
    return rotationLL(node);
}

राइट-लेफ्ट रोटेशन

दूसरे प्रकार का डबल रोटेशन राइट-लेफ्ट रोटेशन है। यह राइट रोटेशन के बाद लेफ्ट रोटेशन का संयोजन है।

स्टेट	एक्शन
	एक नोड को राइट सबट्री के लेफ्ट सबट्री में इंसर्ट किया गया है। यह A को बैलेंस फैक्टर 2 के साथ अनबैलेंस्ड नोड बनाता है।
	पहले, हम C नोड के साथ राइट रोटेशन करते हैं, जिससे C अपने लेफ्ट सबट्री B का राइट सबट्री बन जाता है। अब, B A का राइट सबट्री बन जाता है।
	नोड A अभी भी अनबैलेंस्ड है क्योंकि इसके राइट सबट्री के राइट सबट्री के कारण और इसे लेफ्ट रोटेशन की आवश्यकता है।
	लेफ्ट रोटेशन B को सबट्री का नया रूट नोड बनाकर किया जाता है। A अपने राइट सबट्री B का लेफ्ट सबट्री बन जाता है।
	ट्री अब बैलेंस्ड है।

इसे RL रोटेशन भी कहा जाता है क्योंकि हम पहले राइट रोटेशन और फिर लेफ्ट रोटेशन करते हैं। इसे पिछले 2 मेथड्स का उपयोग करके इस तरह लागू किया जा सकता है:

function rotationRL(node) {
    node.right = rotationLL(node.right);
    return rotationRR(node);
}