एवीएल ट्री: Difference between revisions
No edit summary |
No edit summary |
||
Line 14: | Line 14: | ||
|delete_worst=<math>\text{O}(\log n)</math><ref name="wiscurl"/> | |delete_worst=<math>\text{O}(\log n)</math><ref name="wiscurl"/> | ||
}} | }} | ||
[[File:AVL Tree Example.gif|thumb|एवीएल पेड़ में | [[File:AVL Tree Example.gif|thumb|एवीएल पेड़ में अनेक तत्वों को सम्मिलित करने वाला एनीमेशन। इसमें बाएँ, दाएँ, बाएँ-दाएँ और दाएँ-बाएँ घुमाव सम्मिलित हैं।]] | ||
[[Image:AVL-tree-wBalance_K.svg|thumb|right|262px|चित्र 1: संतुलन कारकों के साथ एवीएल वृक्ष (हरा)]][[कंप्यूटर विज्ञान]] में, '''एवीएल पेड़''' (आविष्कारकों एडेलसन-वेल्स्की और लैंडिस के नाम पर) [[स्व-संतुलन द्विआधारी खोज वृक्ष|स्व-संतुलन द्विआधारी परीक्षण वृक्ष]] है। एवीएल पेड़ में, किसी भी ग्रंथि के दो [[ बाल नोड्स |बाल ग्रंथि]] उपपेड़ की ऊंचाई अधिकतम से भिन्न होती है; यदि किसी भी समय उनमें से अधिक का अंतर होता है, तो इस संपत्ति को पुनर्स्थापित करने के लिए पुनर्संतुलन किया जाता है। लुकअप, सम्मिलन और विलोपन सभी लेते हैं I {{math|[[big O notation|O]](log ''n'')}} औसत और सबसे अमान्य दोनों विषयों में समय, जहां <math>n</math> संचालन से | [[Image:AVL-tree-wBalance_K.svg|thumb|right|262px|चित्र 1: संतुलन कारकों के साथ एवीएल वृक्ष (हरा)]][[कंप्यूटर विज्ञान]] में, '''एवीएल पेड़''' (आविष्कारकों एडेलसन-वेल्स्की और लैंडिस के नाम पर) [[स्व-संतुलन द्विआधारी खोज वृक्ष|स्व-संतुलन द्विआधारी परीक्षण वृक्ष]] है। एवीएल पेड़ में, किसी भी ग्रंथि के दो [[ बाल नोड्स |बाल ग्रंथि]] उपपेड़ की ऊंचाई अधिकतम से भिन्न होती है; यदि किसी भी समय उनमें से अधिक का अंतर होता है, तो इस संपत्ति को पुनर्स्थापित करने के लिए पुनर्संतुलन किया जाता है। लुकअप, सम्मिलन और विलोपन सभी लेते हैं I {{math|[[big O notation|O]](log ''n'')}} औसत और सबसे अमान्य दोनों विषयों में समय, जहां <math>n</math> संचालन से पूर्व पेड़ में ग्रंथि की संख्या है। सम्मिलन और विलोपन के लिए पेड़ को या अधिक वृक्ष घुमावों द्वारा पुनर्संतुलित करने की आवश्यकता हो सकती है I | ||
एवीएल पेड़ का नाम इसके दो [[सोवियत संघ]] के आविष्कारकों, [[जॉर्जी एडेल्सन-वेल्स्की]] और [[एवगेनी लैंडिस]] के नाम पर रखा गया है, जिन्होंने इसे अपने 1962 के पेपर एन एल्गोरिदम फॉर द ऑर्गनाइजेशन ऑफ इंफॉर्मेशन में प्रकाशित किया था।<ref>{{cite journal|last1=Adelson-Velsky|first1=Georgy|last2=Landis|first2=Evgenii|year=1962|title=सूचना के संगठन के लिए एक एल्गोरिदम|journal=[[Proceedings of the USSR Academy of Sciences]]|volume=146|pages=263–266|language=ru}} [https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf English translation] by Myron J. Ricci in ''Soviet Mathematics - Doklady'', 3:1259–1263, 1962.</ref> यह आविष्कार किया जाने वाला सबसे प्राचीन स्व-संतुलन द्विआधारी सर्च पेड़ [[डेटा संरचना]] है।<ref>{{cite book |last=Sedgewick |first=Robert |title=एल्गोरिदम|publisher=Addison-Wesley |year=1983 |isbn=0-201-06672-6 |page=[https://archive.org/details/algorithms00sedg/page/199 199] |chapter=Balanced Trees |author-link1=Robert Sedgewick (computer scientist) |chapter-url=https://archive.org/details/algorithms00sedg/page/199 |chapter-url-access=registration}}</ref> एवीएल पेड़ों की तुलना प्रायः लाल-काले पेड़ों से की जाती है, क्योंकि दोनों संचालन और टेक के समान समूह का समर्थन करते हैं I <math>\text{O}(\log n)</math> प्रारंभिक कार्यों के लिए समय लुकअप-गहन अनुप्रयोगों के लिए, एवीएल पेड़ लाल-काले पेड़ों की तुलना में तीव्र होते हैं, क्योंकि वे अधिक कठोरता से संतुलित होते हैं।<ref name="Pfaff1">{{cite web|last = Pfaff|first = Ben|title = सिस्टम सॉफ्टवेयर में बीएसटी का प्रदर्शन विश्लेषण| publisher = [[Stanford University]]|date=June 2004|url = http://www.stanford.edu/~blp/papers/libavl.pdf}}</ref> लाल-काले पेड़ों के समान, एवीएल पेड़ ऊंचाई-संतुलित होते हैं। सामान्यतः, दोनों न तो [[वजन-संतुलित पेड़]] हैं, न ही वजन-संतुलित <math>\mu</math>-किसी के लिए संतुलित <math>\mu\leq\tfrac{1}{2}</math>;<ref>[https://cs.stackexchange.com/q/421 AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?)] <br />Thereby: A Binary Tree is called <math>\mu</math>-balanced, with <math>0 \le\mu\leq\tfrac12</math>, if for every node <math>N</math>, the inequality | एवीएल पेड़ का नाम इसके दो [[सोवियत संघ]] के आविष्कारकों, [[जॉर्जी एडेल्सन-वेल्स्की]] और [[एवगेनी लैंडिस]] के नाम पर रखा गया है, जिन्होंने इसे अपने 1962 के पेपर एन एल्गोरिदम फॉर द ऑर्गनाइजेशन ऑफ इंफॉर्मेशन में प्रकाशित किया था।<ref>{{cite journal|last1=Adelson-Velsky|first1=Georgy|last2=Landis|first2=Evgenii|year=1962|title=सूचना के संगठन के लिए एक एल्गोरिदम|journal=[[Proceedings of the USSR Academy of Sciences]]|volume=146|pages=263–266|language=ru}} [https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf English translation] by Myron J. Ricci in ''Soviet Mathematics - Doklady'', 3:1259–1263, 1962.</ref> यह आविष्कार किया जाने वाला सबसे प्राचीन स्व-संतुलन द्विआधारी सर्च पेड़ [[डेटा संरचना]] है।<ref>{{cite book |last=Sedgewick |first=Robert |title=एल्गोरिदम|publisher=Addison-Wesley |year=1983 |isbn=0-201-06672-6 |page=[https://archive.org/details/algorithms00sedg/page/199 199] |chapter=Balanced Trees |author-link1=Robert Sedgewick (computer scientist) |chapter-url=https://archive.org/details/algorithms00sedg/page/199 |chapter-url-access=registration}}</ref> एवीएल पेड़ों की तुलना प्रायः लाल-काले पेड़ों से की जाती है, क्योंकि दोनों संचालन और टेक के समान समूह का समर्थन करते हैं I <math>\text{O}(\log n)</math> प्रारंभिक कार्यों के लिए समय लुकअप-गहन अनुप्रयोगों के लिए, एवीएल पेड़ लाल-काले पेड़ों की तुलना में तीव्र होते हैं, क्योंकि वे अधिक कठोरता से संतुलित होते हैं।<ref name="Pfaff1">{{cite web|last = Pfaff|first = Ben|title = सिस्टम सॉफ्टवेयर में बीएसटी का प्रदर्शन विश्लेषण| publisher = [[Stanford University]]|date=June 2004|url = http://www.stanford.edu/~blp/papers/libavl.pdf}}</ref> लाल-काले पेड़ों के समान, एवीएल पेड़ ऊंचाई-संतुलित होते हैं। सामान्यतः, दोनों न तो [[वजन-संतुलित पेड़]] हैं, न ही वजन-संतुलित <math>\mu</math>-किसी के लिए संतुलित <math>\mu\leq\tfrac{1}{2}</math>;<ref>[https://cs.stackexchange.com/q/421 AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?)] <br />Thereby: A Binary Tree is called <math>\mu</math>-balanced, with <math>0 \le\mu\leq\tfrac12</math>, if for every node <math>N</math>, the inequality | ||
Line 209: | Line 209: | ||
समय की आवश्यकता है I {{math|O(log ''n'')}} लुकअप के लिए, साथ ही अधिकतम {{math|O(log ''n'')}} पुनः अनुरेखण स्तर ({{math|O(1)}} औसतन) मार्ग पर पुनःजा रहा है, जिससे संचालन {{math|O(log ''n'')}} समय में पूर्ण किया जा सके। | समय की आवश्यकता है I {{math|O(log ''n'')}} लुकअप के लिए, साथ ही अधिकतम {{math|O(log ''n'')}} पुनः अनुरेखण स्तर ({{math|O(1)}} औसतन) मार्ग पर पुनःजा रहा है, जिससे संचालन {{math|O(log ''n'')}} समय में पूर्ण किया जा सके। | ||
===संचालन और थोक संचालन | ===संचालन और थोक संचालन संग्रह करें=== | ||
एकल तत्व इंसर्ट, डिलीट और लुकअप विकल्प के अतिरिक्त, एवीएल पेड़ पर अनेक समूह विकल्प को परिभाषित किया गया है: [[ संघ (सेट सिद्धांत) |संघ (समूह सिद्धांत)]], [[ प्रतिच्छेदन (सेट सिद्धांत) |प्रतिच्छेदन (समूह सिद्धांत)]] और [[ अंतर सेट करें |अंतर समूह]] आदि I इन समूह फलन के आधार पर सम्मिलन या विलोपन पर तीव्र बल्क संचालन प्रस्तावित किया जा सकता है। ये समूह संचालन दो सहायक संचालन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, एवीएल पेड़ों का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है।<ref name="join-based">{{citation | |||
| last1 = Blelloch | first1 = Guy E. | | last1 = Blelloch | first1 = Guy E. | ||
| last2 = Ferizovic | first2 = Daniel | | last2 = Ferizovic | first2 = Daniel | ||
Line 222: | Line 222: | ||
| year = 2016| arxiv = 1602.02120 | | year = 2016| arxiv = 1602.02120 | ||
| s2cid = 2897793 | | s2cid = 2897793 | ||
}}.</ref> | }}.</ref> फलन दो एवीएल पेड़ों पर जुड़ें {{math|''t''<sub>1</sub>}} और {{math|''t''<sub>2</sub>}} और कुंजी {{mvar|k}} सभी तत्वों वाला पेड़ लौटाएगा I {{math|''t''<sub>1</sub>}}, {{math|''t''<sub>2</sub>}} साथ ही {{mvar|k}}. उसकी आवश्यकता हैं I {{mvar|k}} सभी कुंजियों से बड़ा {{math|''t''<sub>1</sub>}} और सभी कुंजियों से छोटा {{math|''t''<sub>2</sub>}} होना चाहिए I यदि दो पेड़ों की ऊंचाई अधिकतम से भिन्न है, तो जॉइन बस बाएं उपवृक्ष के साथ नया ग्रंथि {{math|''t''<sub>1</sub>}} बनाएं, जड़ {{mvar|k}} और दायां उपवृक्ष {{math|''t''<sub>2</sub>}}. अन्यथा, मान लीजिये {{math|''t''<sub>1</sub>}} ये उससे ऊंचा है, {{math|''t''<sub>2</sub>}} से अधिक के लिए (दूसरा विषय सममित है)। जॉइन की दाहिनी रीढ़ का अनुसरण {{math|''t''<sub>1</sub>}} करता है, ग्रंथि {{mvar|c}} तक जिसके साथ {{math|''t''<sub>2</sub>}} संतुलित है I इस बिंदु पर बाएँ बच्चे के साथ नया ग्रंथि {{mvar|c}}, जड़ {{mvar|k}} और सही बच्चा {{math|''t''<sub>2</sub>}} c को प्रतिस्थापित करने के लिए बनाया गया है। नया ग्रंथि एवीएल अपरिवर्तनीय को संतुष्ट करता है, और इसकी ऊंचाई इससे अधिक है, {{mvar|c}} ऊंचाई में वृद्धि से इसके पूर्वजों की ऊंचाई बढ़ सकती है, संभवतः उन ग्रंथि के एवीएल अपरिवर्तनीय को अमान्य कर दिया जा सकता है। इसे या तो दोगुने घुमाव के साथ ठीक किया जा सकता है, यदि मूल पर अमान्य है या यदि पेड़ में उच्चतर अमान्य है तो एकल बाएं घुमाव के साथ, दोनों ही विषयों में किसी भी पूर्वज ग्रंथि के लिए ऊंचाई को बहाल किया जा सकता है। इसलिए जॉइन के लिए अधिकतम दो घुमावों की आवश्यकता होगी। इस फलन की लागत दो इनपुट पेड़ों के मध्य की ऊंचाई का अंतर है। | ||
फलन दो एवीएल पेड़ों पर जुड़ें {{math|''t''<sub>1</sub>}} और {{math|''t''<sub>2</sub>}} और कुंजी {{mvar|k}} सभी तत्वों वाला पेड़ लौटाएगा {{math|''t''<sub>1</sub>}}, {{math|''t''<sub>2</sub>}} साथ ही {{mvar|k}}. उसकी आवश्यकता हैं {{mvar|k}} सभी कुंजियों से बड़ा | |||
{{Collapse top|बांधना कलन विधि के लिए छदमकोड कार्यान्वयन}} | {{Collapse top|बांधना कलन विधि के लिए छदमकोड कार्यान्वयन}} | ||
function JoinRightAVL(TL, k, TR) | function JoinRightAVL(TL, k, TR) | ||
Line 244: | Line 243: | ||
{{Collapse bottom}} | {{Collapse bottom}} | ||
एवीएल वृक्ष को दो छोटे वृक्षों में विभाजित करना, जो कुंजी | एवीएल वृक्ष को दो छोटे वृक्षों में विभाजित करना, जो कुंजी {{mvar|k}} से छोटे हों, और वे कुंजी {{mvar|k}} से बड़े हैं, पूर्व मार्ग से {{mvar|k}} एवीएल में हैं। इस प्रविष्टि के पश्चात्, सभी मान इससे कम होंगे {{mvar|k}} पथ के बायीं ओर मिलेगा, और सभी मान इससे बड़े होंगे {{mvar|k}} दाहिनी ओर मिलेगा I जॉइन प्रस्तावित करने से, बायीं ओर के सभी उपवृक्षों को नीचे से ऊपर की ओर मध्यवर्ती ग्रंथि के रूप में पथ पर कुंजियों का उपयोग करके बाएँ वृक्ष बनाने के लिए विलय किया जाता है, और दायाँ भाग असममित होता है। विभाजित {{math|O(log ''n'')}}, पेड़ की ऊंचाई का क्रम की लागत है I | ||
{{Collapse top|Pseudocode implementation for the Split algorithm}} | {{Collapse top|Pseudocode implementation for the Split algorithm}} | ||
फ़ंक्शन स्प्लिट (टी, के) | फ़ंक्शन स्प्लिट (टी, के) | ||
Line 258: | Line 257: | ||
{{Collapse bottom}} | {{Collapse bottom}} | ||
दो एवीएल पेड़ों का मिलन {{math|''t''<sub>1</sub>}} और {{math|''t''<sub>2</sub>}} समूह का प्रतिनिधित्व करना {{mvar|A}} और {{mvar|B}}, एवीएल है {{mvar|''t''}} जो | दो एवीएल पेड़ों का मिलन {{math|''t''<sub>1</sub>}} और {{math|''t''<sub>2</sub>}} समूह का प्रतिनिधित्व करना {{mvar|A}} और {{mvar|B}}, एवीएल है, {{mvar|''t''}} जो {{math|''A'' ∪ ''B''}} प्रतिनिधित्व करता है I | ||
{{Collapse top|Pseudocode implementation for the Union algorithm}} | {{Collapse top|Pseudocode implementation for the Union algorithm}} | ||
Line 277: | Line 276: | ||
==पुनर्संतुलन== | ==पुनर्संतुलन== | ||
यदि संशोधित संचालन के दौरान दो चाइल्ड उपवृक्षों के | यदि संशोधित संचालन के दौरान दो चाइल्ड उपवृक्षों के मध्य ऊंचाई का अंतर बदलता है, तो यह, जब तक कि यह <2 है, मूल पर संतुलन जानकारी के अनुकूलन द्वारा परिलक्षित हो सकता है। सम्मिलित करने और हटाने के संचालन के दौरान 2 का (अस्थायी) ऊंचाई अंतर उत्पन्न हो सकता है, जिसका अर्थ है कि मूल उपवृक्ष को पुनर्संतुलित करना होगा। दिए गए मरम्मत उपकरण तथाकथित पेड़ घुमाव हैं, क्योंकि वे कुंजियों को केवल लंबवत रूप से घुमाते हैं, जिससे कुंजियों का (क्षैतिज) क्रम क्रम पूरी प्रकार से संरक्षित रहे (जो द्विआधारी-सर्च पेड़ के लिए आवश्यक है)।<ref name="Knuth"/>{{rp|458–481}} <ref name="Pfaff"/>{{rp|33}} | ||
मान लीजिए कि X वह ग्रंथि है जिसका (अस्थायी) संतुलन कारक -2 या +2 है। इसके बाएँ या दाएँ उपवृक्ष को संशोधित किया गया था। मान लीजिए कि Z बड़ा बच्चा है (आंकड़े 2 और 3 देखें)। ध्यान दें कि दोनों बच्चे [[गणितीय प्रेरण]] द्वारा एवीएल आकार में हैं। | मान लीजिए कि X वह ग्रंथि है जिसका (अस्थायी) संतुलन कारक -2 या +2 है। इसके बाएँ या दाएँ उपवृक्ष को संशोधित किया गया था। मान लीजिए कि Z बड़ा बच्चा है (आंकड़े 2 और 3 देखें)। ध्यान दें कि दोनों बच्चे [[गणितीय प्रेरण]] द्वारा एवीएल आकार में हैं। | ||
सम्मिलन के विषय में यह सम्मिलन Z के बच्चों में से के साथ इस प्रकार से हुआ है कि Z की ऊंचाई बढ़ गई है। | सम्मिलन के विषय में यह सम्मिलन Z के बच्चों में से के साथ इस प्रकार से हुआ है कि Z की ऊंचाई बढ़ गई है। | ||
विलोपन के विषय में यह विलोपन सहोदर टी को हुआ है<sub>1</sub> Z का प्रकार से जिससे t<sub>1</sub>की ऊंचाई | विलोपन के विषय में यह विलोपन सहोदर टी को हुआ है<sub>1</sub> Z का प्रकार से जिससे t<sub>1</sub>की ऊंचाई पूर्व से ही कम होने के कारण कम हो गई है। (यह मात्र मामला है जहां Z का संतुलन कारक 0 भी हो सकता है।) | ||
उल्लंघन के चार संभावित प्रकार हैं: | उल्लंघन के चार संभावित प्रकार हैं: | ||
Line 309: | Line 308: | ||
जिससे स्थितियों को निरूपित किया जाता है {{nowrap|''C B'',}} जहां C (= बच्चे की दिशा) और B (= संतुलन) समूह से आते हैं {{nowrap|{ ''Left'', ''Right'' }}} साथ {{nowrap|1=''Right'' := −''Left''.}}विषय का शेष उल्लंघन {{nowrap|1=''C'' == ''B''}} की मरम्मत साधारण घुमाव द्वारा की जाती है {{nowrap|<code>rotate_</code>(−''C''),}} जबकि मामला {{nowrap|1=''C'' != ''B''}} की मरम्मत दोहरे घुमाव द्वारा की जाती है {{nowrap|<code>rotate_</code>''CB''.}} | जिससे स्थितियों को निरूपित किया जाता है {{nowrap|''C B'',}} जहां C (= बच्चे की दिशा) और B (= संतुलन) समूह से आते हैं {{nowrap|{ ''Left'', ''Right'' }}} साथ {{nowrap|1=''Right'' := −''Left''.}}विषय का शेष उल्लंघन {{nowrap|1=''C'' == ''B''}} की मरम्मत साधारण घुमाव द्वारा की जाती है {{nowrap|<code>rotate_</code>(−''C''),}} जबकि मामला {{nowrap|1=''C'' != ''B''}} की मरम्मत दोहरे घुमाव द्वारा की जाती है {{nowrap|<code>rotate_</code>''CB''.}} | ||
घुमाव की लागत, चाहे वह साधारण हो या दोगुनी, स्थिर होती है। | |||
===सरल घुमाव=== | ===सरल घुमाव=== | ||
चित्र 2 सही सही स्थिति दिखाता है। इसके ऊपरी आधे भाग में, ग्रंथि X में <span style= color:#FF0000; के संतुलन कारक के साथ दो चाइल्ड ट्री हैं; >+2</span>. इसके | चित्र 2 सही सही स्थिति दिखाता है। इसके ऊपरी आधे भाग में, ग्रंथि X में <span style= color:#FF0000; के संतुलन कारक के साथ दो चाइल्ड ट्री हैं; >+2</span>. इसके अतिरिक्त, आंतरिक बच्चा टी<sub>23</sub> Z का (अर्थात, बायां बच्चा जब Z दायां बच्चा है, या दायां बच्चा जब Z बायां बच्चा है) अपने सहोदर से अधिक नहीं है<sub>4</sub>. यह सबपेड़ टी की ऊंचाई बढ़ने से हो सकता है<sub>4</sub> या उपवृक्ष टी की ऊंचाई में कमी से<sub>1</sub>. पश्चात् वाले विषय में भी, पीली स्थिति जहां टी<sub>23</sub> इसकी ऊँचाई t के समान है<sub>4</sub> तब हो सकती है। | ||
बाएँ घुमाव का परिणाम चित्र के निचले आधे भाग में दिखाया गया है। तीन लिंक (चित्र 2 में मोटे किनारे) और दो संतुलन कारकों को अद्यतन किया जाना है। | बाएँ घुमाव का परिणाम चित्र के निचले आधे भाग में दिखाया गया है। तीन लिंक (चित्र 2 में मोटे किनारे) और दो संतुलन कारकों को अद्यतन किया जाना है। | ||
जैसा कि चित्र से पता चलता है, सम्मिलन से | जैसा कि चित्र से पता चलता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और घूमने के पश्चात् फिर से स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 स्तर पर थी, जहां यह फिर से है, जब t<sub>23</sub> और टी<sub>4</sub> ही कद के थे. अन्यथा पत्ती की परत h+1 स्तर तक पहुंच जाती है, जिससे घूमने वाले पेड़ की ऊंचाई कम हो जाती है। | ||
[[File:AVL-simple-left_K.svg|thumb|right|194px|चित्र 2: सरल घुमाव<br />rotate_Left(X,Z)]];सरल बाएँ घुमाव का कोड स्निपेट | [[File:AVL-simple-left_K.svg|thumb|right|194px|चित्र 2: सरल घुमाव<br />rotate_Left(X,Z)]];सरल बाएँ घुमाव का कोड स्निपेट | ||
Line 352: | Line 351: | ||
</सिंटैक्सहाइलाइट> | </सिंटैक्सहाइलाइट> | ||
===डबल | ===डबल घुमाव === | ||
चित्र 3 दाएँ बाएँ स्थिति को दर्शाता है। इसके ऊपरी तीसरे भाग में, ग्रंथि X में <span style= color:#FF0000; के संतुलन कारक के साथ दो चाइल्ड ट्री हैं; >+2</span>. किन्तु चित्र 2 के विपरीत, Z का आंतरिक बच्चा Y उसके भाई t से ऊंचा है<sub>4</sub>. यह स्वयं Y के सम्मिलन या इसके किसी उपवृक्ष t की ऊँचाई में वृद्धि से हो सकता है<sub>2</sub> या टी<sub>3</sub> (इस परिणाम के साथ कि वे अलग-अलग ऊंचाई के हैं) या उपवृक्ष टी की ऊंचाई में कमी से<sub>1</sub>. पश्चात् वाले विषय में, यह भी हो सकता है कि टी<sub>2</sub> और टी<sub>3</sub> समान ऊंचाई के हैं. | चित्र 3 दाएँ बाएँ स्थिति को दर्शाता है। इसके ऊपरी तीसरे भाग में, ग्रंथि X में <span style= color:#FF0000; के संतुलन कारक के साथ दो चाइल्ड ट्री हैं; >+2</span>. किन्तु चित्र 2 के विपरीत, Z का आंतरिक बच्चा Y उसके भाई t से ऊंचा है<sub>4</sub>. यह स्वयं Y के सम्मिलन या इसके किसी उपवृक्ष t की ऊँचाई में वृद्धि से हो सकता है<sub>2</sub> या टी<sub>3</sub> (इस परिणाम के साथ कि वे अलग-अलग ऊंचाई के हैं) या उपवृक्ष टी की ऊंचाई में कमी से<sub>1</sub>. पश्चात् वाले विषय में, यह भी हो सकता है कि टी<sub>2</sub> और टी<sub>3</sub> समान ऊंचाई के हैं. | ||
पूर्व, दाएँ, घुमाव का परिणाम चित्र के मध्य तीसरे में दिखाया गया है। (संतुलन कारकों के संबंध में, यह घुमाव अन्य एवीएल ल घुमावों के समान नहीं है, क्योंकि Y और t के मध्य ऊंचाई का अंतर है<sub>4</sub> केवल 1 है।) अंतिम बाएँ घुमाव का परिणाम चित्र के निचले तीसरे भाग में दिखाया गया है। पांच लिंक (चित्रा 3 में मोटे किनारे) और तीन संतुलन कारकों को अद्यतन किया जाना है। | |||
जैसा कि चित्र से पता चलता है, सम्मिलन से | जैसा कि चित्र से पता चलता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और दोहरे घुमाव के पश्चात् फिर से स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 के स्तर पर थी और दोहरे घुमाव के पश्चात् यह h+1 के स्तर पर थी, जिससे कि घुमाए गए पेड़ की ऊंचाई कम हो गई। | ||
[[File:AVL-double-rl_K.svg|thumb|right|264px|चित्र 3: डबल | [[File:AVL-double-rl_K.svg|thumb|right|264px|चित्र 3: डबल घुमाव रोटेट_राइटलेफ्ट(्स,जेड)<br/>= रोटेट_राइट ज़ेड के चारों ओर और उसके पश्चात्<br/>रोटेट_लेफ्ट चारों ओर ्स]];दाएँ-बाएँ दोहरे घुमाव का कोड स्निपेट | ||
{| | {| | ||
|- | |- | ||
Line 408: | Line 407: | ||
==अन्य संरचनाओं से तुलना== | ==अन्य संरचनाओं से तुलना== | ||
एवीएल पेड़ और लाल-काले (आरबी) पेड़ दोनों स्व-संतुलन वाले द्विआधारी परीक्षण पेड़ हैं और वे गणितीय रूप से संबंधित हैं। दरअसल, प्रत्येक एवीएल पेड़ को लाल-काला रंग दिया जा सकता है,<ref>{{cite web|title=एवीएल पेड़|periodical=Dictionary of Algorithms and Data Structures|publisher=[[National Institute of Standards and Technology]]|url=https://xlinux.nist.gov/dads/HTML/avltree.html|access-date=2016-07-02|last=Paul E. Black|date=2015-04-13}}</ref> किन्तु ऐसे आरबी पेड़ हैं जो एवीएल संतुलित नहीं हैं। एवीएल (या आरबी) पेड़ के अपरिवर्तनीयों को बनाए रखने के लिए, घुमाव महत्वपूर्ण भूमिका निभाते हैं। सबसे अमान्य स्थिति में, | एवीएल पेड़ और लाल-काले (आरबी) पेड़ दोनों स्व-संतुलन वाले द्विआधारी परीक्षण पेड़ हैं और वे गणितीय रूप से संबंधित हैं। दरअसल, प्रत्येक एवीएल पेड़ को लाल-काला रंग दिया जा सकता है,<ref>{{cite web|title=एवीएल पेड़|periodical=Dictionary of Algorithms and Data Structures|publisher=[[National Institute of Standards and Technology]]|url=https://xlinux.nist.gov/dads/HTML/avltree.html|access-date=2016-07-02|last=Paul E. Black|date=2015-04-13}}</ref> किन्तु ऐसे आरबी पेड़ हैं जो एवीएल संतुलित नहीं हैं। एवीएल (या आरबी) पेड़ के अपरिवर्तनीयों को बनाए रखने के लिए, घुमाव महत्वपूर्ण भूमिका निभाते हैं। सबसे अमान्य स्थिति में, घुमाव के बिना भी, एवीएल या आरबी सम्मिलन या विलोपन की आवश्यकता होती है {{math|O(log ''n'')}} एवीएल संतुलन कारकों (या आरबी रंग) का निरीक्षण और/या अद्यतन। आरबी सम्मिलन और विलोपन और एवीएल सम्मिलन के लिए शून्य से तीन [[ पूँछ बुलाओ |पूँछ बुलाओ]] | टेल-रिकर्सिव घुमाव की आवश्यकता होती है और अमूर्त विश्लेषण में चलाया जाता है {{math|O(1)}} समय,<ref>[[Kurt Mehlhorn]], [[Peter Sanders (computer scientist)|Peter Sanders]]: "Algorithms and Data Structures. The Basic Toolbox." Springer, Berlin/Heidelberg 2008, {{ISBN|978-3-540-77977-3}}, {{doi|10.1007/978-3-540-77978-0}}.</ref>{{rp|pp.165,158}} <ref Name="Dinesh">Dinesh P. Mehta, Sartaj Sahni (Ed.) ''Handbook of Data Structures and Applications'' 10.4.2</ref> इस प्रकार औसतन समान रूप से स्थिर। एवीएल विलोपन की आवश्यकता है {{math|O(log ''n'')}}सबसे अमान्य स्थिति में भी घुमाव होते हैं {{math|O(1)}} औसत पर। आरबी पेड़ों को प्रत्येक ग्रंथि में बिट जानकारी (रंग) संग्रहीत करने की आवश्यकता होती है, जबकि एवीएल पेड़ ज्यादातर संतुलन कारक के लिए दो बिट्स का उपयोग करते हैं, हालांकि, जब बच्चों पर संग्रहीत किया जाता है, तो "सिबलिंग से कम" अर्थ वाला बिट पर्याप्त होता है। दो डेटा संरचनाओं के मध्य बड़ा अंतर उनकी ऊंचाई सीमा है। | ||
आकार के पेड़ के लिए {{math|''n'' ≥ 1}} | आकार के पेड़ के लिए {{math|''n'' ≥ 1}} | ||
Line 425: | Line 424: | ||
\end{array} | \end{array} | ||
</math> .<ref>[[Red–black tree#Proof of bounds]]</ref> | </math> .<ref>[[Red–black tree#Proof of bounds]]</ref> | ||
एवीएल पेड़ आरबी पेड़ों की तुलना में अधिक कठोरता से संतुलित होते हैं, जिसमें एसिम्प्टोटिक विश्लेषण संबंध एवीएल/आरबी ≈0.720 अधिकतम ऊंचाई का होता है। सम्मिलन और विलोपन के लिए, बेन पफ़्फ़ 79 मापों में माध्य ≈0.947 और ज्यामितीय माध्य ≈0.910 के साथ 0.677 और 1.077 के | एवीएल पेड़ आरबी पेड़ों की तुलना में अधिक कठोरता से संतुलित होते हैं, जिसमें एसिम्प्टोटिक विश्लेषण संबंध एवीएल/आरबी ≈0.720 अधिकतम ऊंचाई का होता है। सम्मिलन और विलोपन के लिए, बेन पफ़्फ़ 79 मापों में माध्य ≈0.947 और ज्यामितीय माध्य ≈0.910 के साथ 0.677 और 1.077 के मध्य एवीएल/आरबी का संबंध दिखाता है।<ref name="Pfaff1"/> | ||
==यह भी देखें== | ==यह भी देखें== | ||
*[[WAVL पेड़|Wएवीएल पेड़]] | *[[WAVL पेड़|Wएवीएल पेड़]] |
Revision as of 07:51, 13 July 2023
AVL tree | |||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | Tree | ||||||||||||||||||||||||||||
Invented | 1962 | ||||||||||||||||||||||||||||
Invented by | Georgy Adelson-Velsky and Evgenii Landis | ||||||||||||||||||||||||||||
Complexities in big O notation | |||||||||||||||||||||||||||||
|
कंप्यूटर विज्ञान में, एवीएल पेड़ (आविष्कारकों एडेलसन-वेल्स्की और लैंडिस के नाम पर) स्व-संतुलन द्विआधारी परीक्षण वृक्ष है। एवीएल पेड़ में, किसी भी ग्रंथि के दो बाल ग्रंथि उपपेड़ की ऊंचाई अधिकतम से भिन्न होती है; यदि किसी भी समय उनमें से अधिक का अंतर होता है, तो इस संपत्ति को पुनर्स्थापित करने के लिए पुनर्संतुलन किया जाता है। लुकअप, सम्मिलन और विलोपन सभी लेते हैं I O(log n) औसत और सबसे अमान्य दोनों विषयों में समय, जहां संचालन से पूर्व पेड़ में ग्रंथि की संख्या है। सम्मिलन और विलोपन के लिए पेड़ को या अधिक वृक्ष घुमावों द्वारा पुनर्संतुलित करने की आवश्यकता हो सकती है I
एवीएल पेड़ का नाम इसके दो सोवियत संघ के आविष्कारकों, जॉर्जी एडेल्सन-वेल्स्की और एवगेनी लैंडिस के नाम पर रखा गया है, जिन्होंने इसे अपने 1962 के पेपर एन एल्गोरिदम फॉर द ऑर्गनाइजेशन ऑफ इंफॉर्मेशन में प्रकाशित किया था।[2] यह आविष्कार किया जाने वाला सबसे प्राचीन स्व-संतुलन द्विआधारी सर्च पेड़ डेटा संरचना है।[3] एवीएल पेड़ों की तुलना प्रायः लाल-काले पेड़ों से की जाती है, क्योंकि दोनों संचालन और टेक के समान समूह का समर्थन करते हैं I प्रारंभिक कार्यों के लिए समय लुकअप-गहन अनुप्रयोगों के लिए, एवीएल पेड़ लाल-काले पेड़ों की तुलना में तीव्र होते हैं, क्योंकि वे अधिक कठोरता से संतुलित होते हैं।[4] लाल-काले पेड़ों के समान, एवीएल पेड़ ऊंचाई-संतुलित होते हैं। सामान्यतः, दोनों न तो वजन-संतुलित पेड़ हैं, न ही वजन-संतुलित -किसी के लिए संतुलित ;[5] अर्थात्, सहोदर ग्रंथि में वंशजों की संख्या बहुत भिन्न हो सकती है।
परिभाषा
संतुलन कारक
द्विआधारी वृक्ष में ग्रंथि के संतुलन कारक को ऊंचाई अंतर के रूप में परिभाषित किया गया है:-
- [6]: 459
इसके दो बाल उप-वृक्षों का द्विआधारी पेड़ को एवीएल पेड़ के रूप में परिभाषित किया गया है, यदि इनवेरिएंट (कंप्यूटर विज्ञान)
पेड़ में प्रत्येक ग्रंथि X के लिए धारण करता है।
ग्रंथि के साथ वाम-भारी कहा जाता है, के साथ दाएँ-भारी कहा जाता है, और के साथ कभी-कभी इसे केवल संतुलित कहा जाता है।
गुण
पूर्व संतुलन कारकों और ऊंचाई में परिवर्तन को समझकर संतुलन कारकों को अद्यतन रखा जा सकता है- पूर्ण ऊंचाई जानना आवश्यक नहीं है। एवीएल संतुलन जानकारी रखने के लिए, प्रति ग्रंथि दो बिट पर्याप्त हैं।[8] ऊंचाई (स्तरों की अधिकतम संख्या के रूप में गिना जाता है) एवीएल वृक्ष के साथ ग्रंथि अंतराल में निहित हैं:[6]: 460
- जहाँ सुनहरा अनुपात है और
इसका कारण ऊंचाई का एवीएल वृक्ष है, कम से कम सम्मिलित है I ग्रंथि जहाँ बीज मूल्यों के साथ फाइबोनैचि संख्या है I
संचालन
एवीएल पेड़ के रीड-ओनली संचालन में वही क्रियाएं सम्मिलित होती हैं, जो असंतुलित द्विआधारी परीक्षण पेड़ पर की जाती हैं, किन्तु संशोधनों में उप-पेड़ों की ऊंचाई संतुलन का निरीक्षण करना और पुनर्स्थापित करना होता है।
अन्वेषण
एवीएल पेड़ में विशिष्ट कुंजी के परीक्षण उसी प्रकार से किये जा सकते है जैसे किसी संतुलित या असंतुलित द्विआधारी परीक्षण पेड़ अन्वेषण की होती है।[9]: ch. 8 परीक्षण को प्रभावी प्रकार से काम करने के लिए इसे तुलना फलन को नियोजित करना होगा, जो कुंजियों के समूह पर कुल ऑर्डर (या कम से कम निर्बल ऑर्डर, कुल प्रीऑर्डर) स्थापित करता है।[10]: 23 सफल परीक्षण के लिए आवश्यक तुलनाओं की संख्या ऊंचाई h तक सीमित है, और असफल परीक्षण के लिए h बहुत निकट है, तो दोनों O(log n) अंदर हैं I[11]: 216
ट्रैवर्सल
रीड-ओनली विकल्प के रूप में एवीएल पेड़ का ट्रैवर्सल किसी अन्य द्विआधारी पेड़ के जैसे ही कार्य करता है। सभी का अन्वेषण n पेड़ के ग्रंथि प्रत्येक लिंक पर ठीक दो बार जाते हैं: नीचे की ओर जाने वाली यात्रा उस ग्रंथि द्वारा निहित उप-वृक्ष में प्रवेश करने के लिए, दूसरी ऊपर की ओर जाने वाली यात्रा उस ग्रंथि के उप-वृक्ष का पता लगाने के पश्चात् उसे त्यागने के लिए जाती है।
एवीएल पेड़ में ग्रंथि मिल जाने के पश्चात्, पूर्व ग्रंथि को अमूर्त जटिलता निरंतर समय में प्रवेश किया जा सकता है।[12]: 58 इन निकट के ग्रंथि की परीक्षण के कुछ उदाहरणों में ट्रैवर्सिंग की आवश्यकता होती है, h ∝ log(n) लिंक (विशेष रूप से जब जड़ के बाएं उपवृक्ष के सबसे दाहिने पत्ते से जड़ तक या जड़ से जड़ के दाएं उपवृक्ष के सबसे बाएं पत्ते तक नेविगेट करते हैं; चित्र 1 के एवीएल पेड़ में, ग्रंथि P से अगले-से-दाएँ तक नेविगेट करना ग्रंथि Q 3 चरण लेता है)। क्योंकि वहां n−1 हैं, किसी भी पेड़ में लिंक, परिशोधित लागत 2×(n−1)/n है, या लगभग 2 है I
सन्निविष्ट करना
एवीएल पेड़ में ग्रंथि के प्रवेश होते समय, आप प्रारम्भ में द्विआधारी परीक्षण पेड़ में प्रवेश जैसी ही प्रक्रिया का पालन करते हैं। यदि पेड़ रिक्त है, तो ग्रंथि को पेड़ की जड़ के रूप में डाला जाता है। यदि पेड़ रिक्त नहीं है, तो हम जड़ के नीचे जाते हैं, और नए ग्रंथि को सम्मिलित करने के लिए स्थान का परीक्षण करते हुए पुनरावर्ती रूप से पेड़ के नीचे जाते हैं। यह ट्रैवर्सल तुलना फलन द्वारा निर्देशित होता है। इस विषय में, ग्रंथि सदैव पेड़ में किसी बाहरी ग्रंथि के अशक्त संदर्भ (बाएं या दाएं) को प्रतिस्थापित करता है, जिससे, ग्रंथि को या तो बाहरी ग्रंथि का बायां-चाइल्ड या दायां-चाइल्ड बनाया जाता है।
इस प्रविष्टि के पश्चात्, यदि कोई पेड़ असंतुलित हो जाता है, तो केवल नए डाले गए ग्रंथि के पूर्वज असंतुलित होते हैं। ऐसा इसलिए है क्योंकि केवल उन ग्रंथि के उप-वृक्ष परिवर्तित किये गए हैं।[13] इसलिए एवीएल पेड़ों के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक ग्रंथि के पूर्वजों की जांच करना आवश्यक है: इसे अनुसंधान कहा जाता है। यह प्रत्येक ग्रंथि के संतुलन कारक पर विचार करके प्राप्त किया जाता है।[6]: 458–481 [12]: 108
चूंकि एकल सम्मिलन के साथ एवीएल अर्धपेड़ की ऊंचाई से अधिक नहीं बढ़ सकती है, सम्मिलन के पश्चात् ग्रंथि का अस्थायी संतुलन कारक सीमा [–2,+2]. में होगा I परीक्षण किये गए प्रत्येक ग्रंथि के लिए, यदि अस्थायी संतुलन कारक -1 से +1 तक की सीमा में रहता है, तो केवल संतुलन कारक का अद्यतन और कोई नियमित आवर्तन आवश्यक नहीं है। चूंकि, यदि अस्थायी संतुलन कारक ±2 है, तो इस ग्रंथि पर निहित उपवृक्ष एवीएल असंतुलित है, और नियमित आवर्तन की आवश्यकता है।[10]: 52 जैसा कि नीचे दिए गए कोड से ज्ञात होता है, सम्मिलन के साथ, पर्याप्त नियमित आवर्तन पेड़ को पुनः संतुलित करता है।
चित्र 1 में, ग्रंथि X के चाइल्ड के रूप में नया ग्रंथि Z डालने से उस उपपेड़ Z की ऊंचाई 0 से 1 तक बढ़ जाती है।
- सम्मिलन के लिए अनुसंधान लूप का लूप अपरिवर्तनीय
Z द्वारा मार्ग किए गए उपपेड़ की ऊंचाई 1 बढ़ गई है। यह पूर्व से ही एवीएल आकार में है।
style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | सम्मिलित संचालन के लिए उदाहरण कोड
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root) // BF(X) has to be updated: if (Z == right_child(X)) { // The right subtree increases if (BF(X) > 0) { // X is right-heavy // ==> the temporary BF(X) == +2 // ==> rebalancing is required. G = parent(X); // Save parent of X around rotations if (BF(Z) < 0) // Right Left Case (see figure 3) N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X) else // Right Right Case (see figure 2) N = rotate_Left(X, Z); // Single rotation Left(X) // After rotation adapt parent link } else { if (BF(X) < 0) { BF(X) = 0; // Z’s height increase is absorbed at X. break; // Leave the loop } BF(X) = +1; Z = X; // Height(Z) increases by 1 continue; } } else { // Z == left_child(X): the left subtree increases if (BF(X) < 0) { // X is left-heavy // ==> the temporary BF(X) == -2 // ==> rebalancing is required. G = parent(X); // Save parent of X around rotations if (BF(Z) > 0) // Left Right Case N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X) else // Left Left Case N = rotate_Right(X, Z); // Single rotation Right(X) // After rotation adapt parent link } else { if (BF(X) > 0) { BF(X) = 0; // Z’s height increase is absorbed at X. break; // Leave the loop } BF(X) = -1; Z = X; // Height(Z) increases by 1 continue; } } // After a rotation adapt parent link: // N is the new root of the rotated subtree // Height does not change: Height(N) == old Height(X) parent(N) = G; if (G != null) { if (X == left_child(G)) left_child(G) = N; else right_child(G) = N; } else tree->root = N; // N is the new root of the total tree break; // There is no fall thru, only break; or continue; } // Unless loop is left via break, the height of the total tree increases by 1.|}सभी ग्रंथि के संतुलन कारकों को अद्यतन करने के लिए, देखें कि सुधार की आवश्यकता वाले सभी ग्रंथि सम्मिलित पत्ते के पथ के साथ बच्चे से माता-पिता तक स्थित हैं। यदि उपरोक्त प्रक्रिया को पत्ती से प्रारम्भ करके इस पथ के ग्रंथि पर प्रस्तावित किया जाता है, तो पेड़ के प्रत्येक ग्रंथि में -1, 0, या 1 का संतुलन कारक होगा। यदि संतुलन कारक 0 हो जाता है, तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस उपवृक्ष की ऊंचाई अपरिवर्तित रहती है। यदि संतुलन कारक ±1 हो जाता है, तो उपवृक्ष की ऊंचाई बढ़ जाती है और अनुसंधान प्रारम्भ रखने की आवश्यकता होती है। यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा ठीक किया जाना चाहिए, जिसके पश्चात् उपवृक्ष की ऊंचाई पूर्व प्रकार ही हो जाती है (और इसकी जड़ में संतुलन कारक 0 होता है)। समय की आवश्यकता है, O(log n) लुकअप के लिए, साथ ही अधिकतम O(log n) पुनः अनुरेखण स्तर (O(1) औसतन) मार्ग पर पुनः जा रहा है, जिससे संचालन O(log n) समय में पूर्ण किया जा सके।[10]: 53 विलोपनकिसी ग्रंथि के विलोपन को प्रारंभिक चरण द्विआधारी परीक्षण पेड़ विलोपन अनुभाग में वर्णित किया गया हैं। वहां, विषय ग्रंथि या प्रतिस्थापन ग्रंथि का प्रभावी विलोपन संबंधित चाइल्ड पेड़ की ऊंचाई को 1 से 0 या 2 से 1 तक कम कर देता है, यदि उस ग्रंथि में बच्चा था। इस उपवृक्ष से प्रारम्भ करते हुए, एवीएल पेड़ों के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक पूर्वज की जांच करना आवश्यक है। इसे पुनः अनुरेखण कहा जाता है। चूँकि विलोपन से एवीएल उपवृक्ष की ऊँचाई से अधिक नहीं घट सकती, ग्रंथि का अस्थायी संतुलन कारक −2 से +2 तक की सीमा में होगा। यदि संतुलन कारक -1 से +1 की सीमा में रहता है, तो इसे एवीएल नियमों के अनुसार समायोजित किया जा सकता है। यदि यह ±2 हो जाता है, तो उपवृक्ष असंतुलित है, और इसे घुमाने की आवश्यकता है। (सम्मिलन के विपरीत जहां घुमाव सदैव पेड़ को संतुलित करता है, विलोपन के पश्चात्, BF(Z) ≠ 0 हो सकता है, (आंकड़े 2 और 3 देखें), जिससे उचित एकल या दोगुने घुमाव के पश्चात् पुनर्संतुलित उपपेड़ की ऊंचाई अर्थ से कम हो जाए कि पेड़ को उच्च स्तर पर पुनः से संतुलित करना होगा।) घूर्णन के विभिन्न विषयों को खंड पुनर्संतुलन में वर्णित किया गया है।
N द्वारा मार्ग किए गए उपवृक्ष की ऊंचाई 1 से कम हो गई है। यह पूर्व से ही एवीएल आकार में है।
यदि संतुलन कारक ±1 हो जाता है (यह 0 रहा होगा) तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस उपवृक्ष की ऊंचाई अपरिवर्तित रहती है। यदि संतुलन कारक 0 हो जाता है (यह ±1 होना चाहिए) तो उपवृक्ष की ऊंचाई कम हो जाती है और अनुसंधान प्रारम्भ रखने की आवश्यकता होती है। यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा सही करना होगा। यह सहोदर Z (चित्र 2 में उच्च संतान वृक्ष) के संतुलन कारक पर निर्भर करता है कि क्या उपवृक्ष की ऊंचाई से कम हो जाती है- और अनुसंधान प्रारम्भ रखने की आवश्यकता है - या नहीं परिवर्तित होता है (यदि Z का संतुलन कारक 0 है) और पूर्ण पेड़ एवीएल-आकार में है। समय की आवश्यकता है I O(log n) लुकअप के लिए, साथ ही अधिकतम O(log n) पुनः अनुरेखण स्तर (O(1) औसतन) मार्ग पर पुनःजा रहा है, जिससे संचालन O(log n) समय में पूर्ण किया जा सके। संचालन और थोक संचालन संग्रह करेंएकल तत्व इंसर्ट, डिलीट और लुकअप विकल्प के अतिरिक्त, एवीएल पेड़ पर अनेक समूह विकल्प को परिभाषित किया गया है: संघ (समूह सिद्धांत), प्रतिच्छेदन (समूह सिद्धांत) और अंतर समूह आदि I इन समूह फलन के आधार पर सम्मिलन या विलोपन पर तीव्र बल्क संचालन प्रस्तावित किया जा सकता है। ये समूह संचालन दो सहायक संचालन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, एवीएल पेड़ों का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है।[14] फलन दो एवीएल पेड़ों पर जुड़ें t1 और t2 और कुंजी k सभी तत्वों वाला पेड़ लौटाएगा I t1, t2 साथ ही k. उसकी आवश्यकता हैं I k सभी कुंजियों से बड़ा t1 और सभी कुंजियों से छोटा t2 होना चाहिए I यदि दो पेड़ों की ऊंचाई अधिकतम से भिन्न है, तो जॉइन बस बाएं उपवृक्ष के साथ नया ग्रंथि t1 बनाएं, जड़ k और दायां उपवृक्ष t2. अन्यथा, मान लीजिये t1 ये उससे ऊंचा है, t2 से अधिक के लिए (दूसरा विषय सममित है)। जॉइन की दाहिनी रीढ़ का अनुसरण t1 करता है, ग्रंथि c तक जिसके साथ t2 संतुलित है I इस बिंदु पर बाएँ बच्चे के साथ नया ग्रंथि c, जड़ k और सही बच्चा t2 c को प्रतिस्थापित करने के लिए बनाया गया है। नया ग्रंथि एवीएल अपरिवर्तनीय को संतुष्ट करता है, और इसकी ऊंचाई इससे अधिक है, c ऊंचाई में वृद्धि से इसके पूर्वजों की ऊंचाई बढ़ सकती है, संभवतः उन ग्रंथि के एवीएल अपरिवर्तनीय को अमान्य कर दिया जा सकता है। इसे या तो दोगुने घुमाव के साथ ठीक किया जा सकता है, यदि मूल पर अमान्य है या यदि पेड़ में उच्चतर अमान्य है तो एकल बाएं घुमाव के साथ, दोनों ही विषयों में किसी भी पूर्वज ग्रंथि के लिए ऊंचाई को बहाल किया जा सकता है। इसलिए जॉइन के लिए अधिकतम दो घुमावों की आवश्यकता होगी। इस फलन की लागत दो इनपुट पेड़ों के मध्य की ऊंचाई का अंतर है।
एवीएल वृक्ष को दो छोटे वृक्षों में विभाजित करना, जो कुंजी k से छोटे हों, और वे कुंजी k से बड़े हैं, पूर्व मार्ग से k एवीएल में हैं। इस प्रविष्टि के पश्चात्, सभी मान इससे कम होंगे k पथ के बायीं ओर मिलेगा, और सभी मान इससे बड़े होंगे k दाहिनी ओर मिलेगा I जॉइन प्रस्तावित करने से, बायीं ओर के सभी उपवृक्षों को नीचे से ऊपर की ओर मध्यवर्ती ग्रंथि के रूप में पथ पर कुंजियों का उपयोग करके बाएँ वृक्ष बनाने के लिए विलय किया जाता है, और दायाँ भाग असममित होता है। विभाजित O(log n), पेड़ की ऊंचाई का क्रम की लागत है I
दो एवीएल पेड़ों का मिलन t1 और t2 समूह का प्रतिनिधित्व करना A और B, एवीएल है, t जो A ∪ B प्रतिनिधित्व करता है I
प्रतिच्छेदन या अंतर के लिए एल्गोरिथ्म समान है, किन्तु इसके लिए Join2 हेल्पर मार्गीन की आवश्यकता होती है जो कि Join के समान है किन्तु मध्य कुंजी के बिना। यूनियन, इंटरसेक्शन या अंतर के नए कार्यों के आधार पर, एवीएल पेड़ में या तो कुंजी या ाधिक कुंजियाँ डाली जा सकती हैं या हटाई जा सकती हैं। चूंकि स्प्लिट कॉल जॉइन करता है किन्तु एवीएल पेड़ों के संतुलन मानदंडों से सीधे निपटता नहीं है, ऐसे कार्यान्वयन को आमतौर पर जॉइन-आधारित पेड़ एल्गोरिदम कहा जाता है | सम्मिलित-आधारित कार्यान्वयन। मिलन, प्रतिच्छेद और भेद प्रत्येक की जटिलता है आकार के एवीएल पेड़ों के लिए और . अधिक महत्वपूर्ण बात यह है कि चूंकि संघ, प्रतिच्छेदन या अंतर के लिए पुनरावर्ती कॉल -दूसरे से स्वतंत्र हैं, इसलिए उन्हें समानांतर एल्गोरिदम के विश्लेषण के साथ समानांतर प्रोग्रामिंग निष्पादित की जा सकती है। .[14]कब , जुड़ाव-आधारित कार्यान्वयन में ल-तत्व सम्मिलन और विलोपन के समान कम्प्यूटेशनल डीएजी है। पुनर्संतुलनयदि संशोधित संचालन के दौरान दो चाइल्ड उपवृक्षों के मध्य ऊंचाई का अंतर बदलता है, तो यह, जब तक कि यह <2 है, मूल पर संतुलन जानकारी के अनुकूलन द्वारा परिलक्षित हो सकता है। सम्मिलित करने और हटाने के संचालन के दौरान 2 का (अस्थायी) ऊंचाई अंतर उत्पन्न हो सकता है, जिसका अर्थ है कि मूल उपवृक्ष को पुनर्संतुलित करना होगा। दिए गए मरम्मत उपकरण तथाकथित पेड़ घुमाव हैं, क्योंकि वे कुंजियों को केवल लंबवत रूप से घुमाते हैं, जिससे कुंजियों का (क्षैतिज) क्रम क्रम पूरी प्रकार से संरक्षित रहे (जो द्विआधारी-सर्च पेड़ के लिए आवश्यक है)।[6]: 458–481 [12]: 33 मान लीजिए कि X वह ग्रंथि है जिसका (अस्थायी) संतुलन कारक -2 या +2 है। इसके बाएँ या दाएँ उपवृक्ष को संशोधित किया गया था। मान लीजिए कि Z बड़ा बच्चा है (आंकड़े 2 और 3 देखें)। ध्यान दें कि दोनों बच्चे गणितीय प्रेरण द्वारा एवीएल आकार में हैं। सम्मिलन के विषय में यह सम्मिलन Z के बच्चों में से के साथ इस प्रकार से हुआ है कि Z की ऊंचाई बढ़ गई है। विलोपन के विषय में यह विलोपन सहोदर टी को हुआ है1 Z का प्रकार से जिससे t1की ऊंचाई पूर्व से ही कम होने के कारण कम हो गई है। (यह मात्र मामला है जहां Z का संतुलन कारक 0 भी हो सकता है।) उल्लंघन के चार संभावित प्रकार हैं:
और पुनर्संतुलन अलग तरीके से किया जाता है:
जिससे स्थितियों को निरूपित किया जाता है C B, जहां C (= बच्चे की दिशा) और B (= संतुलन) समूह से आते हैं { Left, Right } साथ Right := −Left.विषय का शेष उल्लंघन C == B की मरम्मत साधारण घुमाव द्वारा की जाती है घुमाव की लागत, चाहे वह साधारण हो या दोगुनी, स्थिर होती है। सरल घुमावचित्र 2 सही सही स्थिति दिखाता है। इसके ऊपरी आधे भाग में, ग्रंथि X में +2. इसके अतिरिक्त, आंतरिक बच्चा टी23 Z का (अर्थात, बायां बच्चा जब Z दायां बच्चा है, या दायां बच्चा जब Z बायां बच्चा है) अपने सहोदर से अधिक नहीं है4. यह सबपेड़ टी की ऊंचाई बढ़ने से हो सकता है4 या उपवृक्ष टी की ऊंचाई में कमी से1. पश्चात् वाले विषय में भी, पीली स्थिति जहां टी23 इसकी ऊँचाई t के समान है4 तब हो सकती है। बाएँ घुमाव का परिणाम चित्र के निचले आधे भाग में दिखाया गया है। तीन लिंक (चित्र 2 में मोटे किनारे) और दो संतुलन कारकों को अद्यतन किया जाना है। जैसा कि चित्र से पता चलता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और घूमने के पश्चात् फिर से स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 स्तर पर थी, जहां यह फिर से है, जब t23 और टी4 ही कद के थे. अन्यथा पत्ती की परत h+1 स्तर तक पहुंच जाती है, जिससे घूमने वाले पेड़ की ऊंचाई कम हो जाती है। ;सरल बाएँ घुमाव का कोड स्निपेट
<सिंटैक्सहाइलाइट लैंग = सी स्टाइल = ओवरफ़्लो: हिडन लाइन = 1 > ग्रंथि *rotate_Left(ग्रंथि *X, ग्रंथि *Z) { // Z अपने सहोदर से 2 अधिक है t23 = बायाँ_बच्चा(Z); // Z का आंतरिक बच्चा दाएँ_बच्चे(्स) = t23; यदि (t23t!= शून्य) पैरेंट(t23) = ्स; लेफ्ट_चाइल्ड(जेड) = ्स; माता-पिता(्स) = जेड; // पहला मामला, बीएफ(जेड) == 0, // केवल हटाने से होता है, डालने से नहीं: यदि (BF(Z) == 0) {// t23 की ऊंचाई t4 के समान है बीएफ(्स) = +1; // t23 अब उच्चतर बीएफ(जेड) = -1; // t4 अब X से कम है } अन्य {//दूसरा मामला सम्मिलन या विलोपन के साथ होता है: बीएफ(्स) = 0; बीएफ(जेड) = 0; } वापसी Z; // घुमाए गए सबपेड़ की नई जड़ लौटाएं } </सिंटैक्सहाइलाइट> डबल घुमावचित्र 3 दाएँ बाएँ स्थिति को दर्शाता है। इसके ऊपरी तीसरे भाग में, ग्रंथि X में +2. किन्तु चित्र 2 के विपरीत, Z का आंतरिक बच्चा Y उसके भाई t से ऊंचा है4. यह स्वयं Y के सम्मिलन या इसके किसी उपवृक्ष t की ऊँचाई में वृद्धि से हो सकता है2 या टी3 (इस परिणाम के साथ कि वे अलग-अलग ऊंचाई के हैं) या उपवृक्ष टी की ऊंचाई में कमी से1. पश्चात् वाले विषय में, यह भी हो सकता है कि टी2 और टी3 समान ऊंचाई के हैं. पूर्व, दाएँ, घुमाव का परिणाम चित्र के मध्य तीसरे में दिखाया गया है। (संतुलन कारकों के संबंध में, यह घुमाव अन्य एवीएल ल घुमावों के समान नहीं है, क्योंकि Y और t के मध्य ऊंचाई का अंतर है4 केवल 1 है।) अंतिम बाएँ घुमाव का परिणाम चित्र के निचले तीसरे भाग में दिखाया गया है। पांच लिंक (चित्रा 3 में मोटे किनारे) और तीन संतुलन कारकों को अद्यतन किया जाना है। जैसा कि चित्र से पता चलता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और दोहरे घुमाव के पश्चात् फिर से स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 के स्तर पर थी और दोहरे घुमाव के पश्चात् यह h+1 के स्तर पर थी, जिससे कि घुमाए गए पेड़ की ऊंचाई कम हो गई। ;दाएँ-बाएँ दोहरे घुमाव का कोड स्निपेट
<सिंटैक्सहाइलाइट लैंग = सी स्टाइल = ओवरफ़्लो: हिडन लाइन = 1 > ग्रंथि *rotate_RightLeft(ग्रंथि *X, ग्रंथि *Z) { // Z अपने सहोदर से 2 अधिक है वाई = बायाँ_बच्चा(जेड); // Z का आंतरिक बच्चा //Y, सहोदर से 1 अधिक है t3 = राइट_चाइल्ड(Y); बायाँ_बच्चा(Z) = t3; यदि (t3�!= शून्य) पेरेंट(t3) = Z; दाएँ_बच्चे(Y) = Z; माता-पिता(जेड) = वाई; t2 = बायाँ_बच्चा(Y); दाएँ_बच्चे(्स) = t2; यदि (t2�!= शून्य) पेरेंट(t2) = ्स; लेफ्ट_चाइल्ड(वाई) = ्स; माता-पिता(्स) = वाई; // पहला मामला, बीएफ(वाई) == 0, // केवल हटाने से होता है, डालने से नहीं: अगर (बीएफ(वाई) == 0) { बीएफ(्स) = 0; बीएफ(जेड) = 0; } अन्य // अन्य विषय सम्मिलन या विलोपन के साथ होते हैं: यदि (BF(Y) > 0) {// t3 अधिक था बीएफ(्स) = -1; //t1 अब उच्चतर बीएफ(जेड) = 0; } अन्य { // t2 अधिक था बीएफ(्स) = 0; बीएफ(जेड) = +1; // t4 अब उच्चतर } बीएफ(वाई) = 0; वापसी वाई; // घुमाए गए सबपेड़ की नई जड़ लौटाएं } </सिंटैक्सहाइलाइट> अन्य संरचनाओं से तुलनाएवीएल पेड़ और लाल-काले (आरबी) पेड़ दोनों स्व-संतुलन वाले द्विआधारी परीक्षण पेड़ हैं और वे गणितीय रूप से संबंधित हैं। दरअसल, प्रत्येक एवीएल पेड़ को लाल-काला रंग दिया जा सकता है,[15] किन्तु ऐसे आरबी पेड़ हैं जो एवीएल संतुलित नहीं हैं। एवीएल (या आरबी) पेड़ के अपरिवर्तनीयों को बनाए रखने के लिए, घुमाव महत्वपूर्ण भूमिका निभाते हैं। सबसे अमान्य स्थिति में, घुमाव के बिना भी, एवीएल या आरबी सम्मिलन या विलोपन की आवश्यकता होती है O(log n) एवीएल संतुलन कारकों (या आरबी रंग) का निरीक्षण और/या अद्यतन। आरबी सम्मिलन और विलोपन और एवीएल सम्मिलन के लिए शून्य से तीन पूँछ बुलाओ | टेल-रिकर्सिव घुमाव की आवश्यकता होती है और अमूर्त विश्लेषण में चलाया जाता है O(1) समय,[16]: pp.165, 158 [17] इस प्रकार औसतन समान रूप से स्थिर। एवीएल विलोपन की आवश्यकता है O(log n)सबसे अमान्य स्थिति में भी घुमाव होते हैं O(1) औसत पर। आरबी पेड़ों को प्रत्येक ग्रंथि में बिट जानकारी (रंग) संग्रहीत करने की आवश्यकता होती है, जबकि एवीएल पेड़ ज्यादातर संतुलन कारक के लिए दो बिट्स का उपयोग करते हैं, हालांकि, जब बच्चों पर संग्रहीत किया जाता है, तो "सिबलिंग से कम" अर्थ वाला बिट पर्याप्त होता है। दो डेटा संरचनाओं के मध्य बड़ा अंतर उनकी ऊंचाई सीमा है। आकार के पेड़ के लिए n ≥ 1
एवीएल पेड़ आरबी पेड़ों की तुलना में अधिक कठोरता से संतुलित होते हैं, जिसमें एसिम्प्टोटिक विश्लेषण संबंध एवीएल/आरबी ≈0.720 अधिकतम ऊंचाई का होता है। सम्मिलन और विलोपन के लिए, बेन पफ़्फ़ 79 मापों में माध्य ≈0.947 और ज्यामितीय माध्य ≈0.910 के साथ 0.677 और 1.077 के मध्य एवीएल/आरबी का संबंध दिखाता है।[4] यह भी देखें
संदर्भ
अग्रिम पठन
बाहरी संबंधThe Wikibook Algorithm Implementation has a page on the topic of: AVL tree Wikimedia Commons has media related to AVL-trees.
|