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

स्वयं को संतुलित करने के लिए, एक AVL वृक्ष निम्नलिखित चार प्रकार के घूर्णन कर सकता है -

• बाएं घुमाव
• राइट रोटेशन
• बाएं-दाएं घुमाव
• दाएं-बाएं घुमाव

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

बाएं घुमाव

यदि कोई पेड़ असंतुलित हो जाता है, जब एक नोड को दाएँ उपट्री के दाएँ उपप्रकार में डाला जाता है, तो हम एक बाएँ घुमाव करते हैं -

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

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

राइट रोटेशन

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

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

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

बाएं-दाएं घुमाव

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

State
	बाएं सबट्री के दाएं सबट्री में एक नोड डाला गया है। यह C . बनाता है एक असंतुलित नोड। इन परिदृश्यों के कारण AVL ट्री बाएँ-दाएँ घुमाव करता है।
	हम सबसे पहले C. . के बाएं उपप्रकार पर बायां घुमाव करते हैं यह A . बनाता है , B . का बायां उपप्रकार ।
	नोड C अभी भी असंतुलित है, हालाँकि अब, यह लेफ्ट-सबट्री के लेफ्ट-सबट्री के कारण है।
	अब हम पेड़ को दाईं ओर घुमाएंगे, जिससे B . बन जाएगा इस सबट्री का नया रूट नोड। सी अब अपने स्वयं के बाएँ उप-वृक्ष का दायाँ उपप्रकार बन जाता है।
	पेड़ अब संतुलित है।

इसे LR रोटेशन भी कहा जाता है क्योंकि हम पहले एक लेफ्ट रोटेशन और उसके बाद राइट रोटेशन करते हैं। इसे पिछली 2 विधियों का उपयोग करके निम्नानुसार कार्यान्वित किया जा सकता है -

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

दाएं-बाएं घुमाव

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

State
	राइट सबट्री के लेफ्ट सबट्री में एक नोड डाला गया है। यह A, . बनाता है बैलेंस फैक्टर 2 के साथ एक असंतुलित नोड।
	सबसे पहले, हम C . के साथ सही घुमाव करते हैं नोड, C . बनाना अपने स्वयं के बाएँ उपप्रकार का दायाँ उपप्रकार B . अब, B A . का सही उपप्रकार बन जाता है ।
	नोड A अभी भी असंतुलित है क्योंकि इसके दाएँ उप-वृक्ष के दाएँ उपप्रकार के लिए और एक बाएँ घुमाव की आवश्यकता है।
	बाएं घुमाव B . बनाकर किया जाता है सबट्री का नया रूट नोड। ए अपने दाएँ उप-वृक्ष का बायाँ उप-वृक्ष बन जाता है B ।
	पेड़ अब संतुलित है।

इसे एक आरएल रोटेशन भी कहा जाता है क्योंकि हम पहले एक दायां रोटेशन करते हैं और उसके बाद बाएं रोटेशन करते हैं। इसे पिछली 2 विधियों का उपयोग करके निम्नानुसार कार्यान्वित किया जा सकता है -

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