ट्री घूर्णन: 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|सामान्य ट्री घूर्णन।]]असतत गणित में, ट्री घूर्णन [[ द्विआधारी वृक्ष |द्विआधारी ट्री]] पर ऑपरेशन है जो तत्वों के क्रम में हस्तक्षेप किए बिना संरचना को परिवर्तित करता है। ट्री घूर्णन ट्री में नोड को ऊपर और नोड को नीचे ले जाता है। इसका उपयोग ट्री के आकार को परिवर्तित करने के लिए किया जाता है, और विशेष रूप से छोटे अर्ध ट्री को नीचे और बड़े अर्ध ट्री को ऊपर ले जाकर इसकी ऊंचाई कम करने के लिए किया जाता है, जिसके परिणामस्वरूप कई ट्री संचालन के प्रदर्शन में सुधार होता है।


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


==चित्रण==
==चित्रण==
Line 10: Line 10:


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


उपट्रीों के मूल नोड को घुमाने के लिए रूट की शब्दावली पर विचार करें, उस नोड के लिए पिवोट जो नया मूल नोड बन जाएगा, घूर्णन के पक्ष के लिए आरएस और घूर्णन के विपरीत पक्ष के लिए ओएस की शब्दावली पर विचार करें। उपरोक्त चित्र में मूल Q के लिए, RS C है और OS P है। इन शब्दों का उपयोग करते हुए, घूर्णन के लिए छद्म कोड है:
अर्धट्री के मूल नोड को घुमाने के लिए रूट की शब्दावली पर विचार करें, उस नोड के लिए पिवोट जो नया मूल नोड बन जाएगा, घूर्णन के पक्ष के लिए 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))
<पूर्व>
एक से दूसरे की गणना करना अधिक सरल है। निम्नलिखित उदाहरण [[पायथन (प्रोग्रामिंग भाषा)]] कोड है जो उस गणना को निष्पादित करता है:
बायां ट्री: ((ए, पी, बी), क्यू, सी) दायां ट्री: (ए, पी, (बी, क्यू, सी))
</पूर्व>
 
से दूसरे की गणना करना बहुत सरल है। निम्नलिखित उदाहरण [[पायथन (प्रोग्रामिंग भाषा)]] कोड है जो उस गणना को निष्पादित करता है:


<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
Line 39: Line 35:
     return (A, P, (B, Q, C))
     return (A, P, (B, Q, C))
</syntaxhighlight>
</syntaxhighlight>
इसे देखने का दूसरा विधि यह है:
इसे देखने का दूसरी विधि यह है:
 
नोड Q का सही घूर्णन है:
Let P be Q's left child.


नोड Q का सही घूर्णन:
Set Q's left child to be P's right child.


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


नोड P का बायां घूर्णन:
Set P's right child to be Q.


<पूर्व>
[Set Q's parent to P]
माना Q, P की दाहिनी संतान है।
नोड P का बायां घूर्णन है:
P की दाईं संतान को Q की बाईं संतान के रूप में सेट करें।
Let Q be P's right child.
[Q के बाएं बच्चे के माता-पिता को P पर सेट करें]
Q के बाएँ बच्चे को P निर्धारित करें।
[P के माता-पिता को Q पर सेट करें]
</पूर्व>


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


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


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


यह [[खुली समस्या]] है कि क्या [[घूर्णन दूरी]] की गणना के लिए कोई बहुपद समय [[कलन विधि]] उपस्तिथ है। फिर भी, फोर्डहैम का एल्गोरिदम रैखिक समय में दूरी की गणना करता है, लेकिन केवल 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>
[[डेनियल स्लेटर]], [[रॉबर्ट टार्जन]] और [[विलियम थर्स्टन]] ने दिखाया कि किन्हीं दो n-नोड ट्री (n ≥ 11 के लिए) के मध्य घूर्णन दूरी अधिकतम 2n − 6 है, और जैसे ही n पर्याप्त रूप से बड़ा होता है तो ट्री के कुछ जोड़े इतनी दूर हो जाते हैं,<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 19:28, 16 July 2023

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

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

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

चित्रण

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 पर्याप्त रूप से बड़ा होता है तो ट्री के कुछ जोड़े इतनी दूर हो जाते हैं,[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=227584’