ट्री घूर्णन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|A local change in a binary tree that preserves leaf order}}
{{Short description|A local change in a binary tree that preserves leaf order}}
[[File:BinaryTreeRotations.svg|alt=|thumb|300x300px|जेनेरिक ट्री रोटेशन।]]असतत गणित में, ट्री रोटेशन [[ द्विआधारी वृक्ष ]] पर ऑपरेशन है जो तत्वों के क्रम में हस्तक्षेप किए बिना संरचना को बदलता है। ट्री रोटेशन पेड़ में नोड को ऊपर और नोड को नीचे ले जाता है। इसका उपयोग पेड़ के आकार को बदलने के लिए किया जाता है, और विशेष रूप से छोटे उपवृक्षों को नीचे और बड़े उपवृक्षों को ऊपर ले जाकर इसकी ऊंचाई कम करने के लिए किया जाता है, जिसके परिणामस्वरूप कई वृक्ष संचालन के प्रदर्शन में सुधार होता है।
[[File:BinaryTreeRotations.svg|alt=|thumb|300x300px|जेनेरिक ट्री घूर्णन।]]असतत गणित में, ट्री घूर्णन [[ द्विआधारी वृक्ष |द्विआधारी ट्री]] पर ऑपरेशन है जो तत्वों के क्रम में हस्तक्षेप किए बिना संरचना को परिवर्तित करता है। ट्री घूर्णन ट्री में नोड को ऊपर और नोड को नीचे ले जाता है। इसका उपयोग ट्री के आकार को परिवर्तित करने के लिए किया जाता है, और विशेष रूप से छोटे अर्ध ट्री को नीचे और बड़े अर्ध ट्री को ऊपर ले जाकर इसकी ऊंचाई कम करने के लिए किया जाता है, जिसके परिणामस्वरूप कई ट्री संचालन के प्रदर्शन में सुधार होता है।


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


==चित्रण==
==चित्रण==
[[Image:Tree rotation.png|left|540px]] [[Image:Tree rotation animation 250x250.gif|right|पेड़ों के घूमने का एनीमेशन।]]जैसा कि आसन्न छवि में दिखाया गया है, सही रोटेशन ऑपरेशन को जड़ के रूप में क्यू के साथ निष्पादित किया जाता है और इसलिए यह क्यू पर या रूट पर सही रोटेशन है। इस ऑपरेशन के परिणामस्वरूप पेड़ का घूर्णन दक्षिणावर्त दिशा में होता है। उलटा ऑपरेशन बायां घुमाव है, जिसके परिणामस्वरूप वामावर्त दिशा में गति होती है (ऊपर दिखाया गया बायां घुमाव पी पर निहित है)। यह समझने की कुंजी कि घूर्णन कैसे कार्य करता है, इसकी बाधाओं को समझना है। विशेष रूप से पेड़ की पत्तियों का क्रम (उदाहरण के लिए बाएं से दाएं पढ़ने पर) नहीं बदल सकता (इसके बारे में सोचने का दूसरा तरीका यह है कि इन-ऑर्डर ट्रैवर्सल में पत्तियों का दौरा करने का क्रम वही होना चाहिए जो बाद में होता है) पहले की तरह संचालन)। अन्य बाधा [[बाइनरी सर्च ट्री]] की मुख्य संपत्ति है, अर्थात् दायां बच्चा माता-पिता से बड़ा है और [[बायां बच्चा]] मूल नोड | माता-पिता से कम है। ध्यान दें कि उप-वृक्ष की जड़ के बाएं बच्चे का दायां बच्चा (उदाहरण के लिए क्यू पर जड़े पेड़ के लिए आरेख में नोड बी) जड़ का बायां बच्चा बन सकता है, वह स्वयं नए का दायां बच्चा बन जाता है इनमें से किसी भी बाधा का उल्लंघन किए बिना, घुमाए गए उप-वृक्ष में जड़ डालें। जैसा कि आप चित्र में देख सकते हैं, पत्तियों का क्रम नहीं बदलता है। विपरीत ऑपरेशन भी क्रम को बरकरार रखता है और दूसरे प्रकार का रोटेशन है।
[[Image:Tree rotation.png|left|540px]] [[Image:Tree rotation animation 250x250.gif|right|ट्रीों के घूमने का एनीमेशन।]]जैसा कि आसन्न छवि में दिखाया गया है, सही घूर्णन ऑपरेशन को जड़ के रूप में Q के साथ निष्पादित किया जाता है और इसलिए यह Q पर या रूट पर सही घूर्णन है। इस ऑपरेशन के परिणामस्वरूप ट्री का घूर्णन दक्षिणावर्त दिशा में होता है। उलटा ऑपरेशन बायां घूर्णन है, जिसके परिणामस्वरूप वामावर्त दिशा में गति होती है (ऊपर दिखाया गया बायां घूर्णन पी पर निहित है)। यह समझने की कुंजी कि घूर्णन कैसे कार्य करता है, इसकी बाधाओं का अध्ययन करना है। विशेष रूप से ट्री की लीफ का क्रम (उदाहरण के लिए बाएं से दाएं पढ़ने पर) नहीं परिवर्तित हो सकता (इसके बारे में सोचने का दूसरी विधि यह है कि इन-ऑर्डर ट्रैवर्सल में लीफ का क्रमांक करने का क्रम वही होना चाहिए जो पश्चात में होता है) पूर्व के जैसे संचालन)। अन्य बाधा [[बाइनरी सर्च ट्री]] का मुख्य गुण है, अर्थात् दायां बच्चा माता-पिता से बड़ा है और [[बायां बच्चा]] मूल नोड माता-पिता से कम है। ध्यान दें कि उप-ट्री की जड़ के बाएं बच्चे का दायां बच्चा (उदाहरण के लिए Q पर जड़े ट्री के लिए आरेख में नोड B) जड़ का बायां बच्चा बन सकता है, वह स्वयं नए का दायां बच्चा बन जाता है इनमें से किसी भी बाधा का उल्लंघन किए बिना, घूर्णन किये गए उप-ट्री में जड़ डालें। जैसा कि आप चित्र में देख सकते हैं, लीफ का क्रम नहीं परिवर्तित होता है। विपरीत ऑपरेशन भी क्रम को स्थिर रखता है और दूसरे प्रकार का घूर्णन है।


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


==विस्तृत चित्रण==
==विस्तृत चित्रण==
[[Image:Tree Rotations.gif|thumb|upright=1.3|घूर्णन कैसे किया जाता है इसका सचित्र वर्णन।]]जब उपवृक्ष को घुमाया जाता है, तो जिस उपवृक्ष पक्ष पर इसे घुमाया जाता है, उसकी ऊंचाई नोड बढ़ जाती है जबकि दूसरे उपवृक्ष की ऊंचाई कम हो जाती है। यह पेड़ के पुनर्संतुलन के लिए पेड़ के घूर्णन को उपयोगी बनाता है।
[[Image:Tree Rotations.gif|thumb|upright=1.3|घूर्णन कैसे किया जाता है इसका सचित्र वर्णन।]]जब उपट्री को घुमाया जाता है, तो जिस उपट्री पक्ष पर इसे घुमाया जाता है, उसकी ऊंचाई नोड बढ़ जाती है जबकि दूसरे उपट्री की ऊंचाई कम हो जाती है। यह ट्री के पुनर्संतुलन के लिए ट्री के घूर्णन को उपयोगी बनाता है।


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


  धुरी = रूट.ओएस
  धुरी = रूट.ओएस
Line 21: Line 21:
यह निरंतर समय का ऑपरेशन है.
यह निरंतर समय का ऑपरेशन है.


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


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


<पूर्व>
<पूर्व>
बायां पेड़: ((ए, पी, बी), क्यू, सी) दायां पेड़: (ए, पी, (बी, क्यू, सी))
बायां ट्री: ((ए, पी, बी), क्यू, सी) दायां ट्री: (ए, पी, (बी, क्यू, सी))
</पूर्व>
</पूर्व>


Line 39: Line 39:
     return (A, P, (B, Q, C))
     return (A, P, (B, Q, C))
</syntaxhighlight>
</syntaxhighlight>
इसे देखने का दूसरा तरीका यह है:
इसे देखने का दूसरा विधि यह है:


नोड Q का सही घुमाव:
नोड Q का सही घूर्णन:


<पूर्व>
<पूर्व>
Line 51: Line 51:
</पूर्व>
</पूर्व>


नोड P का बायां घुमाव:
नोड P का बायां घूर्णन:


<पूर्व>
<पूर्व>
Line 63: Line 63:
अन्य सभी कनेक्शन वैसे ही छोड़ दिए गए हैं।
अन्य सभी कनेक्शन वैसे ही छोड़ दिए गए हैं।


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


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


==पुनर्संतुलन के लिए घुमाव==
==पुनर्संतुलन के लिए घूर्णन==
[[Image:Tree Rebalancing.gif|thumb|एवीएल वृक्ष में घूर्णन कैसे पुनर्संतुलन का कारण बनता है, इसका सचित्र वर्णन।]]घूर्णन का उपयोग करके पेड़ को पुनः संतुलित किया जा सकता है। घूर्णन के बाद, घूर्णन का पक्ष अपनी ऊंचाई 1 बढ़ा देता है जबकि घूर्णन के विपरीत पक्ष अपनी ऊंचाई उसी प्रकार कम कर देता है। इसलिए, कोई रणनीतिक रूप से उन नोड्स पर रोटेशन लागू कर सकता है जिनके बाएं बच्चे और दाएं बच्चे की ऊंचाई 1 से अधिक है। स्व-संतुलन बाइनरी खोज पेड़ इस ऑपरेशन को स्वचालित रूप से लागू करते हैं। प्रकार का पेड़ जो इस पुनर्संतुलन तकनीक का उपयोग करता है वह एवीएल पेड़ है।
[[Image:Tree Rebalancing.gif|thumb|एवीएल ट्री में घूर्णन कैसे पुनर्संतुलन का कारण बनता है, इसका सचित्र वर्णन।]]घूर्णन का उपयोग करके ट्री को पुनः संतुलित किया जा सकता है। घूर्णन के पश्चात, घूर्णन का पक्ष अपनी ऊंचाई 1 बढ़ा देता है जबकि घूर्णन के विपरीत पक्ष अपनी ऊंचाई उसी प्रकार कम कर देता है। इसलिए, कोई रणनीतिक रूप से उन नोड्स पर घूर्णन लागू कर सकता है जिनके बाएं बच्चे और दाएं बच्चे की ऊंचाई 1 से अधिक है। स्व-संतुलन बाइनरी खोज ट्री इस ऑपरेशन को स्वचालित रूप से लागू करते हैं। प्रकार का ट्री जो इस पुनर्संतुलन तकनीक का उपयोग करता है वह एवीएल ट्री है।


==रोटेशन दूरी==
==घूर्णन दूरी==
{{main|Rotation distance}}
{{main|Rotation distance}}
{{unsolved|computer science|Can the rotation distance between two binary trees be computed in polynomial time?}}
{{unsolved|computer science|Can the rotation distance between two binary trees be computed in polynomial time?}}
समान संख्या में नोड्स वाले किन्हीं दो बाइनरी पेड़ों के बीच रोटेशन की दूरी को दूसरे में बदलने के लिए आवश्यक रोटेशन की न्यूनतम संख्या है। इस दूरी के साथ, एन-नोड बाइनरी पेड़ों का सेट [[मीट्रिक स्थान]] बन जाता है: दो अलग-अलग पेड़ दिए जाने पर दूरी सममित, सकारात्मक होती है, और त्रिकोण असमानता को संतुष्ट करती है।
समान संख्या में नोड्स वाले किन्हीं दो बाइनरी ट्रीों के बीच घूर्णन की दूरी को दूसरे में बदलने के लिए आवश्यक घूर्णन की न्यूनतम संख्या है। इस दूरी के साथ, एन-नोड बाइनरी ट्रीों का सेट [[मीट्रिक स्थान]] बन जाता है: दो अलग-अलग ट्री दिए जाने पर दूरी सममित, सकारात्मक होती है, और त्रिकोण असमानता को संतुष्ट करती है।


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


[[डेनियल स्लेटर]], [[रॉबर्ट टार्जन]] और [[विलियम थर्स्टन]] ने दिखाया कि किन्हीं दो एन-नोड पेड़ों (एन ≥ 11 के लिए) के बीच घूर्णन दूरी अधिकतम 2एन − 6 है, और जैसे ही एन पर्याप्त रूप से बड़ा होता है तो पेड़ों के कुछ जोड़े इतनी दूर हो जाते हैं .<ref>{{citation|last1=Sleator|first1=Daniel D.|authorlink1=Daniel Sleator|last2=Tarjan|first2=Robert E.|authorlink2=Robert Tarjan|last3=Thurston|first3=William P.|authorlink3=William Thurston|title=Rotation distance, triangulations, and hyperbolic geometry|journal=[[Journal of the American Mathematical Society]]|volume=1|issue=3|year=1988|pages=647–681|doi=10.2307/1990951|mr=928904 |jstor=1990951|doi-access=free}}.</ref> लियोनेल पौर्निन ने दिखाया कि, वास्तव में, ऐसे जोड़े तब भी मौजूद होते हैं जब n ≥ 11 होता है।<ref>{{citation | last = Pournin | first = Lionel | arxiv = 1207.6296 | doi = 10.1016/j.aim.2014.02.035 | doi-access=free | journal = [[Advances in Mathematics]] | mr = 3197650 | pages = 13–42 | title = The diameter of associahedra | volume = 259 | year = 2014}}.</ref>
[[डेनियल स्लेटर]], [[रॉबर्ट टार्जन]] और [[विलियम थर्स्टन]] ने दिखाया कि किन्हीं दो एन-नोड ट्रीों (एन ≥ 11 के लिए) के बीच घूर्णन दूरी अधिकतम 2एन − 6 है, और जैसे ही एन पर्याप्त रूप से बड़ा होता है तो ट्रीों के कुछ जोड़े इतनी दूर हो जाते हैं .<ref>{{citation|last1=Sleator|first1=Daniel D.|authorlink1=Daniel Sleator|last2=Tarjan|first2=Robert E.|authorlink2=Robert Tarjan|last3=Thurston|first3=William P.|authorlink3=William Thurston|title=Rotation distance, triangulations, and hyperbolic geometry|journal=[[Journal of the American Mathematical Society]]|volume=1|issue=3|year=1988|pages=647–681|doi=10.2307/1990951|mr=928904 |jstor=1990951|doi-access=free}}.</ref> लियोनेल पौर्निन ने दिखाया कि, वास्तव में, ऐसे जोड़े तब भी उपस्तिथ होते हैं जब n ≥ 11 होता है।<ref>{{citation | last = Pournin | first = Lionel | arxiv = 1207.6296 | doi = 10.1016/j.aim.2014.02.035 | doi-access=free | journal = [[Advances in Mathematics]] | mr = 3197650 | pages = 13–42 | title = The diameter of associahedra | volume = 259 | year = 2014}}.</ref>


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


==संदर्भ==
==संदर्भ==

Revision as of 14:49, 16 July 2023

File:BinaryTreeRotations.svg
जेनेरिक ट्री घूर्णन।

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

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

चित्रण

File:Tree rotation.png
ट्रीों के घूमने का एनीमेशन।

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

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

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

File:Tree Rotations.gif
घूर्णन कैसे किया जाता है इसका सचित्र वर्णन।

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

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

धुरी = रूट.ओएस
रूट.ओएस = पिवोट.आरएस
धुरी.आरएस = जड़
जड़ = धुरी

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

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

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

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

<पूर्व> बायां ट्री: ((ए, पी, बी), क्यू, सी) दायां ट्री: (ए, पी, (बी, क्यू, सी)) </पूर्व>

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

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 का सही घूर्णन:

<पूर्व> माना P, Q का बायां बच्चा है। Q के बाएँ बच्चे को P का दाएँ बच्चे के रूप में सेट करें। [P के दाएँ बच्चे के माता-पिता को Q पर सेट करें] P का दाहिना बच्चा Q निर्धारित करें। [Q के मूल को P पर सेट करें] </पूर्व>

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

<पूर्व> माना Q, P की दाहिनी संतान है। P की दाईं संतान को Q की बाईं संतान के रूप में सेट करें। [Q के बाएं बच्चे के माता-पिता को P पर सेट करें] Q के बाएँ बच्चे को P निर्धारित करें। [P के माता-पिता को Q पर सेट करें] </पूर्व>

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

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

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

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

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

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

घूर्णन दूरी

Main article: Rotation distance
Unsolved problem in computer science:

Can the rotation distance between two binary trees be computed in polynomial time?

(more unsolved problems in computer science)

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

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

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

यह भी देखें

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

संदर्भ

  1. ↑ Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988), "Rotation distance, triangulations, and hyperbolic geometry", Journal of the American Mathematical Society, 1 (3): 647–681, doi:10.2307/1990951, JSTOR 1990951, MR 0928904.
  2. ↑ Pournin, Lionel (2014), "The diameter of associahedra", Advances in Mathematics, 259: 13–42, arXiv:1207.6296, doi:10.1016/j.aim.2014.02.035, MR 3197650.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ट्री_घूर्णन&oldid=227583’