ट्री घूर्णन: Difference between revisions
(Created page with "{{Short description|A local change in a binary tree that preserves leaf order}} File:BinaryTreeRotations.svg|alt=|thumb|300x300px|जेनेरिक ट्री रो...") |
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|पेड़ों के घूमने का एनीमेशन।]]जैसा कि आसन्न छवि में दिखाया गया है, सही रोटेशन ऑपरेशन को जड़ के रूप में क्यू के साथ निष्पादित किया जाता है और इसलिए यह क्यू पर या रूट पर सही रोटेशन है। इस ऑपरेशन के परिणामस्वरूप पेड़ का घूर्णन दक्षिणावर्त दिशा में होता है। उलटा ऑपरेशन बायां घुमाव है, जिसके परिणामस्वरूप वामावर्त दिशा में गति होती है (ऊपर दिखाया गया बायां घुमाव पी पर निहित है)। यह समझने की कुंजी कि घूर्णन कैसे कार्य करता है, इसकी बाधाओं को समझना है। विशेष रूप से पेड़ की पत्तियों का क्रम (उदाहरण के लिए बाएं से दाएं पढ़ने पर) नहीं बदल सकता (इसके बारे में सोचने का दूसरा तरीका यह है कि इन-ऑर्डर ट्रैवर्सल में पत्तियों का दौरा करने का क्रम वही होना चाहिए जो बाद में होता है) पहले की तरह संचालन)। अन्य बाधा [[बाइनरी सर्च ट्री]] की मुख्य संपत्ति है, अर्थात् दायां बच्चा माता-पिता से बड़ा है और [[बायां बच्चा]] मूल नोड | माता-पिता से कम है। ध्यान दें कि उप-वृक्ष की जड़ के बाएं बच्चे का दायां बच्चा (उदाहरण के लिए क्यू पर जड़े पेड़ के लिए आरेख में नोड बी) जड़ का बायां बच्चा बन सकता है, वह स्वयं नए का दायां बच्चा बन जाता है इनमें से किसी भी बाधा का उल्लंघन किए बिना, घुमाए गए उप-वृक्ष में जड़ डालें। जैसा कि आप चित्र में देख सकते हैं, पत्तियों का क्रम नहीं बदलता है। विपरीत ऑपरेशन भी क्रम को बरकरार रखता है और दूसरे प्रकार का रोटेशन है। | ||
यह मानते हुए कि यह | यह मानते हुए कि यह द्विआधारी खोज वृक्ष है, जैसा कि ऊपर बताया गया है, तत्वों की व्याख्या वेरिएबल के रूप में की जानी चाहिए जिनकी दूसरे से तुलना की जा सकती है। बाईं ओर के वर्णमाला वर्णों का उपयोग इन चरों के लिए प्लेसहोल्डर के रूप में किया जाता है। दाईं ओर के एनीमेशन में, बड़े अक्षर वाले वर्णों का उपयोग वेरिएबल प्लेसहोल्डर के रूप में किया जाता है जबकि लोअरकेस ग्रीक अक्षर वेरिएबल के पूरे सेट के लिए प्लेसहोल्डर होते हैं। वृत्त व्यक्तिगत नोड्स का प्रतिनिधित्व करते हैं और त्रिकोण उपवृक्षों का प्रतिनिधित्व करते हैं। प्रत्येक उपवृक्ष खाली हो सकता है, नोड से युक्त हो सकता है, या किसी भी संख्या में नोड्स से युक्त हो सकता है। | ||
==विस्तृत चित्रण== | ==विस्तृत चित्रण== | ||
[[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 19: | Line 19: | ||
जड़ = धुरी | जड़ = धुरी | ||
यह | यह निरंतर समय का ऑपरेशन है. | ||
प्रोग्रामर को यह भी सुनिश्चित करना होगा कि रूट का पैरेंट रोटेशन के बाद धुरी की ओर इंगित करता है। साथ ही, प्रोग्रामर को ध्यान देना चाहिए कि इस ऑपरेशन के परिणामस्वरूप पूरे पेड़ के लिए | प्रोग्रामर को यह भी सुनिश्चित करना होगा कि रूट का पैरेंट रोटेशन के बाद धुरी की ओर इंगित करता है। साथ ही, प्रोग्रामर को ध्यान देना चाहिए कि इस ऑपरेशन के परिणामस्वरूप पूरे पेड़ के लिए नई जड़ बन सकती है और तदनुसार पॉइंटर्स को अपडेट करने का ध्यान रखना चाहिए। | ||
==इनऑर्डर इनवेरिएंस== | ==इनऑर्डर इनवेरिएंस== | ||
| Line 30: | Line 30: | ||
</पूर्व> | </पूर्व> | ||
से दूसरे की गणना करना बहुत सरल है। निम्नलिखित उदाहरण [[पायथन (प्रोग्रामिंग भाषा)]] कोड है जो उस गणना को निष्पादित करता है: | |||
<syntaxhighlight lang="python"> | <syntaxhighlight lang="python"> | ||
| Line 63: | Line 63: | ||
अन्य सभी कनेक्शन वैसे ही छोड़ दिए गए हैं। | अन्य सभी कनेक्शन वैसे ही छोड़ दिए गए हैं। | ||
इसमें दोहरे घुमाव भी होते हैं, जो बाएँ और दाएँ घुमावों का संयोजन होते हैं। एक्स पर | इसमें दोहरे घुमाव भी होते हैं, जो बाएँ और दाएँ घुमावों का संयोजन होते हैं। एक्स पर डबल बाएं रोटेशन को एक्स के दाएं बच्चे पर दाएं रोटेशन के बाद एक्स पर बाएं रोटेशन के रूप में परिभाषित किया जा सकता है; इसी तरह, एक्स पर डबल दाएं रोटेशन को एक्स के बाएं बच्चे पर बाएं रोटेशन के बाद एक्स पर दाएं रोटेशन के रूप में परिभाषित किया जा सकता है। | ||
[[फँसाना]] रोटेशन का उपयोग कई ट्री डेटा संरचनाओं में किया जाता है जैसे कि [[एवीएल पेड़]], लाल-काले पेड़, डब्ल्यूएवीएल पेड़, स्प्ले पेड़ और ट्रेप्स। उन्हें केवल निरंतर समय की आवश्यकता होती है क्योंकि वे स्थानीय परिवर्तन होते हैं: वे केवल 5 नोड्स पर काम करते हैं, और बाकी पेड़ की जांच करने की आवश्यकता नहीं होती है। | [[फँसाना]] रोटेशन का उपयोग कई ट्री डेटा संरचनाओं में किया जाता है जैसे कि [[एवीएल पेड़]], लाल-काले पेड़, डब्ल्यूएवीएल पेड़, स्प्ले पेड़ और ट्रेप्स। उन्हें केवल निरंतर समय की आवश्यकता होती है क्योंकि वे स्थानीय परिवर्तन होते हैं: वे केवल 5 नोड्स पर काम करते हैं, और बाकी पेड़ की जांच करने की आवश्यकता नहीं होती है। | ||
==पुनर्संतुलन के लिए घुमाव== | ==पुनर्संतुलन के लिए घुमाव== | ||
[[Image:Tree Rebalancing.gif|thumb|एवीएल वृक्ष में घूर्णन कैसे पुनर्संतुलन का कारण बनता है, इसका सचित्र वर्णन।]]घूर्णन का उपयोग करके | [[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 प्रकारों में नोड्स के वर्गीकरण पर निर्भर करता है, और प्रकार के नोड को दूसरे में बदलने के लिए आवश्यक घुमावों की संख्या जानने के लिए लुकअप तालिका का उपयोग किया जाता है। | ||
[[डेनियल स्लेटर]], [[रॉबर्ट टार्जन]] और [[विलियम थर्स्टन]] ने दिखाया कि किन्हीं दो एन-नोड पेड़ों (एन ≥ 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:34, 16 July 2023
असतत गणित में, ट्री रोटेशन द्विआधारी वृक्ष पर ऑपरेशन है जो तत्वों के क्रम में हस्तक्षेप किए बिना संरचना को बदलता है। ट्री रोटेशन पेड़ में नोड को ऊपर और नोड को नीचे ले जाता है। इसका उपयोग पेड़ के आकार को बदलने के लिए किया जाता है, और विशेष रूप से छोटे उपवृक्षों को नीचे और बड़े उपवृक्षों को ऊपर ले जाकर इसकी ऊंचाई कम करने के लिए किया जाता है, जिसके परिणामस्वरूप कई वृक्ष संचालन के प्रदर्शन में सुधार होता है।
घूर्णन की दिशा की परिभाषा के संबंध में विभिन्न विवरणों में असंगतता मौजूद है। कुछ लोग कहते हैं कि घूर्णन की दिशा उस दिशा को दर्शाती है जिसमें नोड घूर्णन पर आगे बढ़ रहा है (बायां बच्चा अपने मूल स्थान में घूम रहा है जो दायां घूर्णन है) जबकि अन्य कहते हैं कि घूर्णन की दिशा दर्शाती है कि कौन सा उपवृक्ष घूम रहा है (बायां उपवृक्ष अपने मूल स्थान में घूम रहा है) इसके मूल का स्थान बाएँ घुमाव पर है, जो पहले वाले के विपरीत है)। यह आलेख घूर्णन नोड के दिशात्मक आंदोलन का दृष्टिकोण लेता है।
चित्रण
जैसा कि आसन्न छवि में दिखाया गया है, सही रोटेशन ऑपरेशन को जड़ के रूप में क्यू के साथ निष्पादित किया जाता है और इसलिए यह क्यू पर या रूट पर सही रोटेशन है। इस ऑपरेशन के परिणामस्वरूप पेड़ का घूर्णन दक्षिणावर्त दिशा में होता है। उलटा ऑपरेशन बायां घुमाव है, जिसके परिणामस्वरूप वामावर्त दिशा में गति होती है (ऊपर दिखाया गया बायां घुमाव पी पर निहित है)। यह समझने की कुंजी कि घूर्णन कैसे कार्य करता है, इसकी बाधाओं को समझना है। विशेष रूप से पेड़ की पत्तियों का क्रम (उदाहरण के लिए बाएं से दाएं पढ़ने पर) नहीं बदल सकता (इसके बारे में सोचने का दूसरा तरीका यह है कि इन-ऑर्डर ट्रैवर्सल में पत्तियों का दौरा करने का क्रम वही होना चाहिए जो बाद में होता है) पहले की तरह संचालन)। अन्य बाधा बाइनरी सर्च ट्री की मुख्य संपत्ति है, अर्थात् दायां बच्चा माता-पिता से बड़ा है और बायां बच्चा मूल नोड | माता-पिता से कम है। ध्यान दें कि उप-वृक्ष की जड़ के बाएं बच्चे का दायां बच्चा (उदाहरण के लिए क्यू पर जड़े पेड़ के लिए आरेख में नोड बी) जड़ का बायां बच्चा बन सकता है, वह स्वयं नए का दायां बच्चा बन जाता है इनमें से किसी भी बाधा का उल्लंघन किए बिना, घुमाए गए उप-वृक्ष में जड़ डालें। जैसा कि आप चित्र में देख सकते हैं, पत्तियों का क्रम नहीं बदलता है। विपरीत ऑपरेशन भी क्रम को बरकरार रखता है और दूसरे प्रकार का रोटेशन है।
यह मानते हुए कि यह द्विआधारी खोज वृक्ष है, जैसा कि ऊपर बताया गया है, तत्वों की व्याख्या वेरिएबल के रूप में की जानी चाहिए जिनकी दूसरे से तुलना की जा सकती है। बाईं ओर के वर्णमाला वर्णों का उपयोग इन चरों के लिए प्लेसहोल्डर के रूप में किया जाता है। दाईं ओर के एनीमेशन में, बड़े अक्षर वाले वर्णों का उपयोग वेरिएबल प्लेसहोल्डर के रूप में किया जाता है जबकि लोअरकेस ग्रीक अक्षर वेरिएबल के पूरे सेट के लिए प्लेसहोल्डर होते हैं। वृत्त व्यक्तिगत नोड्स का प्रतिनिधित्व करते हैं और त्रिकोण उपवृक्षों का प्रतिनिधित्व करते हैं। प्रत्येक उपवृक्ष खाली हो सकता है, नोड से युक्त हो सकता है, या किसी भी संख्या में नोड्स से युक्त हो सकता है।
विस्तृत चित्रण
जब उपवृक्ष को घुमाया जाता है, तो जिस उपवृक्ष पक्ष पर इसे घुमाया जाता है, उसकी ऊंचाई नोड बढ़ जाती है जबकि दूसरे उपवृक्ष की ऊंचाई कम हो जाती है। यह पेड़ के पुनर्संतुलन के लिए पेड़ के घूर्णन को उपयोगी बनाता है।
उपवृक्षों के मूल नोड को घुमाने के लिए रूट की शब्दावली पर विचार करें, उस नोड के लिए पिवोट जो नया मूल नोड बन जाएगा, घूर्णन के पक्ष के लिए आरएस और घूर्णन के विपरीत पक्ष के लिए ओएस की शब्दावली पर विचार करें। उपरोक्त चित्र में मूल 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 नोड्स पर काम करते हैं, और बाकी पेड़ की जांच करने की आवश्यकता नहीं होती है।
पुनर्संतुलन के लिए घुमाव
घूर्णन का उपयोग करके पेड़ को पुनः संतुलित किया जा सकता है। घूर्णन के बाद, घूर्णन का पक्ष अपनी ऊंचाई 1 बढ़ा देता है जबकि घूर्णन के विपरीत पक्ष अपनी ऊंचाई उसी प्रकार कम कर देता है। इसलिए, कोई रणनीतिक रूप से उन नोड्स पर रोटेशन लागू कर सकता है जिनके बाएं बच्चे और दाएं बच्चे की ऊंचाई 1 से अधिक है। स्व-संतुलन बाइनरी खोज पेड़ इस ऑपरेशन को स्वचालित रूप से लागू करते हैं। प्रकार का पेड़ जो इस पुनर्संतुलन तकनीक का उपयोग करता है वह एवीएल पेड़ है।
रोटेशन दूरी
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 प्रकारों में नोड्स के वर्गीकरण पर निर्भर करता है, और प्रकार के नोड को दूसरे में बदलने के लिए आवश्यक घुमावों की संख्या जानने के लिए लुकअप तालिका का उपयोग किया जाता है।
डेनियल स्लेटर, रॉबर्ट टार्जन और विलियम थर्स्टन ने दिखाया कि किन्हीं दो एन-नोड पेड़ों (एन ≥ 11 के लिए) के बीच घूर्णन दूरी अधिकतम 2एन − 6 है, और जैसे ही एन पर्याप्त रूप से बड़ा होता है तो पेड़ों के कुछ जोड़े इतनी दूर हो जाते हैं .[1] लियोनेल पौर्निन ने दिखाया कि, वास्तव में, ऐसे जोड़े तब भी मौजूद होते हैं जब n ≥ 11 होता है।[2]
यह भी देखें
- एवीएल ट्री, रेड-ब्लैक ट्री और स्प्ले ट्री, बाइनरी सर्च ट्री डेटा संरचनाओं के प्रकार जो संतुलन बनाए रखने के लिए रोटेशन का उपयोग करते हैं।
- बाइनरी ऑपरेशन की संबद्धता का अर्थ है कि उस पर ट्री रोटेशन करने से अंतिम परिणाम नहीं बदलता है।
- डे-स्टाउट-वॉरेन एल्गोरिदम असंतुलित बीएसटी को संतुलित करता है।
- तमरी जाली, आंशिक रूप से क्रमबद्ध सेट जिसमें तत्वों को बाइनरी पेड़ों के रूप में परिभाषित किया जा सकता है और तत्वों के बीच क्रम को पेड़ के घूमने से परिभाषित किया जाता है।
संदर्भ
- ↑ 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.
- ↑ 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.
बाहरी संबंध
- The AVL Tree Rotations Tutorial (RTF) by John Hargrove
