ट्री घूर्णन

Error creating thumbnail:

सामान्य ट्री घूर्णन।

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

घूर्णन की दिशा की परिभाषा के संबंध में विभिन्न विवरणों में असंगतता उपस्तिथ है। कुछ लोग कहते हैं कि घूर्णन की दिशा उस दिशा को दर्शाती है जिसमें नोड घूर्णन पर आगे बढ़ रहा है (बायां चाइल्ड अपने मूल स्थान में घूम रहा है जो दायां घूर्णन है) जबकि अन्य कहते हैं कि घूर्णन की दिशा दर्शाती है कि कौन सा अर्ध ट्री घूम रहा है (बायां अर्धट्री अपने मूल स्थान में घूम रहा है) इसके मूल का स्थान बाएँ घूर्णन पर है, जो पहले वाले के विपरीत है)। यह आलेख घूर्णन नोड के दिशात्मक नियम का दृष्टिकोण लेता है।

चित्रण

File:Tree rotation.png

ट्रीों के घूमने का एनीमेशन।

जैसा कि आसन्न छवि में दिखाया गया है, सही घूर्णन ऑपरेशन को जड़ के रूप में Q के साथ निष्पादित किया जाता है और इसलिए यह Q पर या रूट पर सही घूर्णन है। इस ऑपरेशन के परिणामस्वरूप ट्री का घूर्णन दक्षिणावर्त दिशा में होता है। उलटा ऑपरेशन बायां घूर्णन है, जिसके परिणामस्वरूप वामावर्त दिशा में गति होती है (ऊपर दिखाया गया बायां घूर्णन पी पर निहित है)। यह समझने की कुंजी कि घूर्णन कैसे कार्य करता है, इसकी बाधाओं का अध्ययन करना है। विशेष रूप से ट्री की लीफ का क्रम (उदाहरण के लिए बाएं से दाएं पढ़ने पर) नहीं परिवर्तित हो सकता (इसके बारे में सोचने का दूसरी विधि यह है कि इन-ऑर्डर ट्रैवर्सल में लीफ का क्रमांक करने का क्रम वही होना चाहिए जो पश्चात में होता है) पूर्व के जैसे संचालन)। अन्य बाधा बाइनरी सर्च ट्री का मुख्य गुण है, अर्थात् दायां बच्चा माता-पिता से बड़ा है और बायां बच्चा मूल नोड माता-पिता से कम है। ध्यान दें कि उप-ट्री की जड़ के बाएं बच्चे का दायां बच्चा (उदाहरण के लिए Q पर जड़े ट्री के लिए आरेख में नोड B) जड़ का बायां बच्चा बन सकता है, वह स्वयं नए का दायां बच्चा बन जाता है इनमें से किसी भी बाधा का उल्लंघन किए बिना, घूर्णन किये गए उप-ट्री में जड़ डालें। जैसा कि आप चित्र में देख सकते हैं, लीफ का क्रम नहीं परिवर्तित होता है। विपरीत ऑपरेशन भी क्रम को स्थिर रखता है और दूसरे प्रकार का घूर्णन है।

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

विस्तृत चित्रण

File:Tree Rotations.gif

घूर्णन कैसे किया जाता है इसका सचित्र वर्णन।

जब अर्धट्री को घुमाया जाता है, तो जिस अर्धट्री पक्ष पर इसे घुमाया जाता है, उसकी ऊंचाई नोड बढ़ जाती है जबकि दूसरे अर्धट्री की ऊंचाई कम हो जाती है। यह ट्री के पुनर्संतुलन के लिए ट्री के घूर्णन को उपयोगी बनाता है।

अर्धट्री के मूल नोड को घुमाने के लिए रूट की शब्दावली पर विचार करें, उस नोड के लिए पिवोट जो नया मूल नोड बन जाएगा, घूर्णन के पक्ष के लिए RS और घूर्णन के विपरीत पक्ष के लिए OS की शब्दावली पर विचार करें। उपरोक्त चित्र में मूल Q के लिए, RS, C है और OS, P है। इन शब्दों का उपयोग करते हुए, घूर्णन के लिए छद्म कोड है:

Pivot = Root.OS
Root.OS = Pivot.RS
Pivot.RS = Root
Root = Pivot

यह निरंतर समय का ऑपरेशन है।

प्रोग्रामर को यह भी सुनिश्चित करना होगा कि रूट का पैरेंट घूर्णन के पश्चात धुरी की ओर प्रदर्शित करता है। साथ ही, प्रोग्रामर को ध्यान देना चाहिए कि इस ऑपरेशन के परिणामस्वरूप पूर्ण ट्री के लिए नई जड़ बन सकती है और तदनुसार पॉइंटर्स को अपडेट करने का ध्यान रखना चाहिए।

इनऑर्डर इनवेरिएंस

ट्री घूर्णन बाइनरी ट्री इनवेरिएंट (कंप्यूटर विज्ञान) के इनऑर्डर ट्रैवर्सल को प्रस्तुत करता है। इसका तात्पर्य यह है कि जब ट्री के किसी भी भाग में घूर्णन किया जाता है तो तत्वों का क्रम प्रभावित नहीं होता है। ऊपर दिखाए गए ट्री के क्रमबद्ध ट्रैवर्सल यहां दिए गए हैं:

Left tree: ((A, P, B), Q, C)        Right tree: (A, P, (B, Q, C))

एक से दूसरे की गणना करना अधिक सरल है। निम्नलिखित उदाहरण पायथन (प्रोग्रामिंग भाषा) कोड है जो उस गणना को निष्पादित करता है:

def right_rotation(treenode):
    """Rotate the specified tree to the right."""
    left, Q, C = treenode
    A, P, B = left
    return (A, P, (B, Q, C))

इसे देखने का दूसरी विधि यह है:

नोड Q का सही घूर्णन है:

Let P be Q's left child.

Set Q's left child to be P's right child.

[Set P's right-child's parent to Q]

Set P's right child to be Q.

[Set Q's parent to P]

नोड P का बायां घूर्णन है:

Let Q be P's right child.

Set P's right child to be Q's left child.

[Set Q's left-child's parent to P]

Set Q's left child to be P.

[Set P's parent to Q]

अन्य सभी कनेक्शन वैसे ही छोड़ दिए गए हैं।

इसमें दोहरे घूर्णन भी होते हैं, जो बाएँ और दाएँ घूर्णनों का संयोजन होते हैं। X पर डबल बाएं घूर्णन को X के दाएं बच्चे पर दाएं घूर्णन के पश्चात X पर बाएं घूर्णन के रूप में परिभाषित किया जा सकता है; इसी प्रकार, X पर डबल दाएं घूर्णन को X के बाएं बच्चे पर बाएं घूर्णन के पश्चात X पर दाएं घूर्णन के रूप में परिभाषित किया जा सकता है।

ट्री घूर्णन का उपयोग कई ट्री डेटा संरचनाओं में किया जाता है जैसे कि एवीएल ट्री, रेड-ब्लैक ट्री, डब्ल्यूएवीएल ट्री, स्प्ले ट्री और ट्रेप्स है। उन्हें केवल निरंतर समय की आवश्यकता होती है क्योंकि वे स्थानीय परिवर्तन होते हैं: वे केवल 5 नोड्स पर कार्य करते हैं, और शेष ट्री का परिक्षण करने की आवश्यकता नहीं होती है।

पुनर्संतुलन के लिए घूर्णन

File:Tree Rebalancing.gif

एवीएल ट्री में घूर्णन कैसे पुनर्संतुलन का कारण बनता है, इसका सचित्र वर्णन।

घूर्णन का उपयोग करके ट्री को पुनः संतुलित किया जा सकता है। घूर्णन के पश्चात, घूर्णन का पक्ष अपनी ऊंचाई 1 बढ़ा देता है जबकि घूर्णन के विपरीत पक्ष अपनी ऊंचाई उसी प्रकार कम कर देता है। इसलिए, कोई रणनीतिक रूप से उन नोड्स पर घूर्णन प्रारम्भ कर सकता है जिनके बाएं बच्चे और दाएं बच्चे की ऊंचाई 1 से अधिक है। स्व-संतुलन बाइनरी शोध ट्री इस ऑपरेशन को स्वचालित रूप से प्रारम्भ करते हैं। इस प्रकार का ट्री जो इस पुनर्संतुलन तकनीक का उपयोग करता है वह एवीएल ट्री है।

घूर्णन दूरी

Main article: घूर्णन दूरी

Unsolved problem in कंप्यूटर विज्ञान:

क्या दो बाइनरी ट्री के मध्य की घूर्णन दूरी की गणना बहुपद समय में की जा सकती है?

(more unsolved problems in कंप्यूटर विज्ञान)

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

यह संवृत समस्या है कि क्या घूर्णन दूरी की गणना के लिए कोई बहुपद समय कलन विधि उपस्तिथ है। फिर भी, फोर्डहैम का एल्गोरिदम रैखिक समय में दूरी की गणना करता है, किंतु केवल 2 प्रकार के घूर्णनों की अनुमति देता है: (ab)c = a(bc) और a((bc)d) = a(b(cd)) है। फोर्डहम का एल्गोरिदम 7 प्रकारों में नोड्स के वर्गीकरण पर निर्भर करता है, और प्रकार के नोड को दूसरे में परिवर्तित करने के लिए आवश्यक घूर्णनों की संख्या जानने के लिए लुकअप तालिका का उपयोग किया जाता है।

डेनियल स्लेटर, रॉबर्ट टार्जन और विलियम थर्स्टन ने दिखाया कि किन्हीं दो n-नोड ट्री (n ≥ 11 के लिए) के मध्य घूर्णन दूरी अधिकतम 2n − 6 है, और जैसे ही n पर्याप्त रूप से बड़ा होता है तो ट्री के कुछ जोड़े इतनी दूर हो जाते हैं, लियोनेल पौर्निन ने दिखाया कि, वास्तव में, ऐसे जोड़े तब भी उपस्तिथ होते हैं जब n ≥ 11 होता है।

यह भी देखें

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

बाहरी संबंध

• The AVL Tree Rotations Tutorial (RTF) by John Hargrove