एवीएल ट्री: 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: संतुलन कारकों के साथ एवीएल | [[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 | ||
:<math>\tfrac12-\mu\le\tfrac{|N_l|}{|N|+1}\le \tfrac12+\mu</math> | :<math>\tfrac12-\mu\le\tfrac{|N_l|}{|N|+1}\le \tfrac12+\mu</math> | ||
Line 25: | Line 25: | ||
===संतुलन कारक=== | ===संतुलन कारक=== | ||
[[ द्विआधारी वृक्ष | द्विआधारी | [[ द्विआधारी वृक्ष | द्विआधारी ट्री]] में ग्रंथि के संतुलन कारक को ऊंचाई अंतर के रूप में परिभाषित किया गया है:- | ||
:<math> \text{BF}(X) := \text{Height}(\text{RightSubtree}(X)) - \text{Height}(\text{LeftSubtree}(X)) </math><ref name="Knuth">{{cite book|last=Knuth|first=Donald E.|author-link=Donald Knuth|title=छाँटना और खोजना|year=2000|publisher=Addison-Wesley|location=Boston [u.a.]|isbn=0-201-89685-0|edition=2. ed., 6. printing, newly updated and rev.}}</ref>{{rp|459}} | :<math> \text{BF}(X) := \text{Height}(\text{RightSubtree}(X)) - \text{Height}(\text{LeftSubtree}(X)) </math><ref name="Knuth">{{cite book|last=Knuth|first=Donald E.|author-link=Donald Knuth|title=छाँटना और खोजना|year=2000|publisher=Addison-Wesley|location=Boston [u.a.]|isbn=0-201-89685-0|edition=2. ed., 6. printing, newly updated and rev.}}</ref>{{rp|459}} | ||
इसके दो बाल उप- | इसके दो बाल उप-ट्रीों का द्विआधारी ट्री को एवीएल ट्री के रूप में परिभाषित किया गया है, यदि इनवेरिएंट (कंप्यूटर विज्ञान) | ||
:<math>\text{BF}(X) \in {\{-1,0,1\}}</math><ref>{{Cite web|url=http://www.btechsmartclass.com/data_structures/avl-trees.html|title=AVL Tree : Data Structures|last=Rajinikanth|website=btechsmartclass.com|access-date=2018-03-09}}</ref> | :<math>\text{BF}(X) \in {\{-1,0,1\}}</math><ref>{{Cite web|url=http://www.btechsmartclass.com/data_structures/avl-trees.html|title=AVL Tree : Data Structures|last=Rajinikanth|website=btechsmartclass.com|access-date=2018-03-09}}</ref> | ||
ट्री में प्रत्येक ग्रंथि X के लिए धारण करता है। | |||
ग्रंथि के साथ <math>\text{BF}(X)<0</math> वाम-भारी कहा जाता है, <math>\text{BF}(X)>0</math> के साथ दाएँ-भारी कहा जाता है, और <math>\text{BF}(X)=0</math> के साथ कभी-कभी इसे केवल संतुलित कहा जाता है। | ग्रंथि के साथ <math>\text{BF}(X)<0</math> वाम-भारी कहा जाता है, <math>\text{BF}(X)>0</math> के साथ दाएँ-भारी कहा जाता है, और <math>\text{BF}(X)=0</math> के साथ कभी-कभी इसे केवल संतुलित कहा जाता है। | ||
===गुण=== | ===गुण=== | ||
पूर्व संतुलन कारकों और ऊंचाई में परिवर्तन को समझकर संतुलन कारकों को अद्यतन रखा जा सकता है- पूर्ण ऊंचाई जानना आवश्यक नहीं है। एवीएल संतुलन जानकारी रखने के लिए, प्रति ग्रंथि दो बिट पर्याप्त हैं।<ref>However, the balance information can be kept in the child nodes as one bit indicating whether the parent is higher by 1 or by 2; thereby higher by 2 cannot occur for both children. This way the AVL tree is a [[WAVL tree|"rank balanced" tree]], as coined by [[#Haeupler|Haeupler, Sen and Tarjan]].</ref> ऊंचाई <math>h</math> (स्तरों की अधिकतम संख्या के रूप में गिना जाता है) एवीएल | पूर्व संतुलन कारकों और ऊंचाई में परिवर्तन को समझकर संतुलन कारकों को अद्यतन रखा जा सकता है- पूर्ण ऊंचाई जानना आवश्यक नहीं है। एवीएल संतुलन जानकारी रखने के लिए, प्रति ग्रंथि दो बिट पर्याप्त हैं।<ref>However, the balance information can be kept in the child nodes as one bit indicating whether the parent is higher by 1 or by 2; thereby higher by 2 cannot occur for both children. This way the AVL tree is a [[WAVL tree|"rank balanced" tree]], as coined by [[#Haeupler|Haeupler, Sen and Tarjan]].</ref> ऊंचाई <math>h</math> (स्तरों की अधिकतम संख्या के रूप में गिना जाता है) एवीएल ट्री के साथ <math>n</math> ग्रंथि अंतराल में निहित हैं:<ref name="Knuth"/>{{rp|460}} | ||
:<math>\log_2(n+1) \le h < \log_\varphi(n+2) + b</math> जहाँ <math>\varphi := \tfrac{1+\sqrt 5}2 \approx 1.618</math>[[सुनहरा अनुपात]] है और <math>b := \frac{\log_2 5}{2 \log_2 \varphi} - 2 \approx \; -0.3277 .</math> | :<math>\log_2(n+1) \le h < \log_\varphi(n+2) + b</math> जहाँ <math>\varphi := \tfrac{1+\sqrt 5}2 \approx 1.618</math>[[सुनहरा अनुपात]] है और <math>b := \frac{\log_2 5}{2 \log_2 \varphi} - 2 \approx \; -0.3277 .</math> | ||
इसका कारण ऊंचाई <math>h</math> का एवीएल | इसका कारण ऊंचाई <math>h</math> का एवीएल ट्री है, <math>F_{h}-1</math> कम से कम सम्मिलित है I ग्रंथि जहाँ <math>\{F_n\}_{n\in\N}</math> बीज मूल्यों के साथ [[फाइबोनैचि संख्या]] <math>F_1=F_2=1 .</math> है I | ||
==संचालन== | ==संचालन== | ||
एवीएल | एवीएल ट्री के रीड-ओनली संचालन में वही क्रियाएं सम्मिलित होती हैं, जो असंतुलित [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण ट्री]] पर की जाती हैं, किन्तु संशोधनों में उप-ट्रीों की ऊंचाई संतुलन का निरीक्षण करना और पुनर्स्थापित करना होता है। | ||
===अन्वेषण=== | ===अन्वेषण=== | ||
एवीएल | एवीएल ट्री में विशिष्ट कुंजी के परीक्षण उसी प्रकार से किये जा सकते है जैसे किसी संतुलित या असंतुलित द्विआधारी परीक्षण ट्री अन्वेषण की होती है।<ref name="dixit-mastering-data-structures">{{Cite book|title='सी' भाषा के माध्यम से डेटा संरचनाओं में महारत हासिल करना|last=Dixit|first=J. B.|publisher=University Science Press, an imprint of Laxmi Publications Pvt. Ltd.|year=2010|isbn=9789380386720|location=New Delhi, India|oclc=939446542}}</ref>{{rp|ch. 8}} परीक्षण को प्रभावी प्रकार से काम करने के लिए इसे तुलना फलन को नियोजित करना होगा, जो कुंजियों के समूह पर [[कुल ऑर्डर]] (या कम से कम निर्बल ऑर्डर, कुल प्रीऑर्डर) स्थापित करता है।<ref name="brass-advanced-data-structures">{{Cite book|title=उन्नत डेटा संरचनाएँ|last=Brass|first=Peter|date=2008|publisher=Cambridge University Press|isbn=9780511438202|location=Cambridge|oclc=312435417}}</ref>{{rp|23}} सफल परीक्षण के लिए आवश्यक तुलनाओं की संख्या ऊंचाई {{math|''h''}} तक सीमित है, और असफल परीक्षण के लिए {{math|''h''}} बहुत निकट है, तो दोनों {{math|O(log ''n'')}} अंदर हैं I<ref name="hubbard-outline-theory-problems">{{Cite book|url=https://archive.org/details/schaumsoutlineof0000hubb|title=शाउम के सिद्धांत की रूपरेखा और जावा के साथ डेटा संरचनाओं की समस्याएं|last=Hubbard|first=John Rast|date=2000|publisher=McGraw-Hill|isbn=0071378707|location=New York|oclc=48139308|url-access=registration}}</ref>{{rp|216}} | ||
===ट्रैवर्सल=== | ===ट्रैवर्सल=== | ||
रीड-ओनली विकल्प के रूप में एवीएल | रीड-ओनली विकल्प के रूप में एवीएल ट्री का ट्रैवर्सल किसी अन्य द्विआधारी ट्री के जैसे ही कार्य करता है। सभी का अन्वेषण {{math|''n''}} ट्री के ग्रंथि प्रत्येक लिंक पर ठीक दो बार जाते हैं: नीचे की ओर जाने वाली यात्रा उस ग्रंथि द्वारा निहित उप-ट्री में प्रवेश करने के लिए, दूसरी ऊपर की ओर जाने वाली यात्रा उस ग्रंथि के उप-ट्री का पता लगाने के पश्चात् उसे त्यागने के लिए जाती है। | ||
एवीएल | एवीएल ट्री में ग्रंथि मिल जाने के पश्चात्, पूर्व ग्रंथि को [[अमूर्त जटिलता]] निरंतर समय में प्रवेश किया जा सकता है।<ref name="Pfaff"/>{{rp|58}} इन निकट के ग्रंथि की परीक्षण के कुछ उदाहरणों में ट्रैवर्सिंग की आवश्यकता होती है, {{math|''h'' ∝ log(''n'')}} लिंक (विशेष रूप से जब जड़ के बाएं उपट्री के सबसे दाहिने पत्ते से जड़ तक या जड़ से जड़ के दाएं उपट्री के सबसे बाएं पत्ते तक नेविगेट करते हैं; चित्र 1 के एवीएल ट्री में, ग्रंथि P से अगले-से-दाएँ तक नेविगेट करना ग्रंथि Q 3 चरण लेता है)। क्योंकि वहां {{math|''n''−1}} हैं, किसी भी ट्री में लिंक, परिशोधित लागत {{math|2×(''n''−1)/''n''}} है, या लगभग 2 है I | ||
===सन्निविष्ट करना=== | ===सन्निविष्ट करना=== | ||
एवीएल | एवीएल ट्री में ग्रंथि के प्रवेश होते समय, आप प्रारम्भ में [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण ट्री]] में प्रवेश जैसी ही प्रक्रिया का पालन करते हैं। यदि ट्री रिक्त है, तो ग्रंथि को ट्री की जड़ के रूप में डाला जाता है। यदि ट्री रिक्त नहीं है, तो हम जड़ के नीचे जाते हैं, और नए ग्रंथि को सम्मिलित करने के लिए स्थान का परीक्षण करते हुए पुनरावर्ती रूप से ट्री के नीचे जाते हैं। यह ट्रैवर्सल तुलना फलन द्वारा निर्देशित होता है। इस विषय में, ग्रंथि सदैव ट्री में किसी बाहरी ग्रंथि के अशक्त संदर्भ (बाएं या दाएं) को प्रतिस्थापित करता है, जिससे, ग्रंथि को या तो बाहरी ग्रंथि का बायां-चाइल्ड या दायां-चाइल्ड बनाया जाता है। | ||
इस प्रविष्टि के पश्चात्, यदि कोई | इस प्रविष्टि के पश्चात्, यदि कोई ट्री असंतुलित हो जाता है, तो केवल नए डाले गए ग्रंथि के पूर्वज असंतुलित होते हैं। ऐसा इसलिए है क्योंकि केवल उन ग्रंथि के उप-ट्री परिवर्तित किये गए हैं।<ref>{{Cite book|last=Weiss, Mark Allen.|title=C++ में डेटा संरचनाएं और एल्गोरिदम विश्लेषण|date=2006|publisher=Pearson Addison-Wesley|year=2006|isbn=0-321-37531-9|edition=3rd|location=Boston|pages=145|oclc=61278554}}</ref> इसलिए एवीएल ट्रीों के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक ग्रंथि के पूर्वजों की जांच करना आवश्यक है: इसे अनुसंधान कहा जाता है। यह प्रत्येक ग्रंथि के संतुलन कारक पर विचार करके प्राप्त किया जाता है।<ref name="Knuth"/>{{rp|458–481}} <ref name="Pfaff">{{cite book|last1=Pfaff|first1=Ben|title=बाइनरी सर्च ट्री और बैलेंस्ड ट्री का परिचय|date=2004|publisher=Free Software Foundation, Inc.}}</ref>{{rp|108}} | ||
चूंकि एकल सम्मिलन के साथ एवीएल | चूंकि एकल सम्मिलन के साथ एवीएल अर्धट्री की ऊंचाई से अधिक नहीं बढ़ सकती है, सम्मिलन के पश्चात् ग्रंथि का अस्थायी संतुलन कारक सीमा {{nowrap|[–2,+2].}} में होगा I परीक्षण किये गए प्रत्येक ग्रंथि के लिए, यदि अस्थायी संतुलन कारक -1 से +1 तक की सीमा में रहता है, तो केवल संतुलन कारक का अद्यतन और कोई नियमित आवर्तन आवश्यक नहीं है। चूंकि, यदि अस्थायी संतुलन कारक ±2 है, तो इस ग्रंथि पर निहित उपट्री एवीएल असंतुलित है, और नियमित आवर्तन की आवश्यकता है।<ref name="brass-advanced-data-structures" />{{rp|52}} जैसा कि नीचे दिए गए कोड से ज्ञात होता है, सम्मिलन के साथ, पर्याप्त नियमित आवर्तन ट्री को पुनः संतुलित करता है। | ||
चित्र 1 में, ग्रंथि X के चाइल्ड के रूप में नया ग्रंथि Z डालने से उस | चित्र 1 में, ग्रंथि X के चाइल्ड के रूप में नया ग्रंथि Z डालने से उस उपट्री Z की ऊंचाई 0 से 1 तक बढ़ जाती है। | ||
;सम्मिलन के लिए अनुसंधान लूप का [[लूप अपरिवर्तनीय]] | ;सम्मिलन के लिए अनुसंधान लूप का [[लूप अपरिवर्तनीय]] | ||
Z द्वारा मार्ग किए गए | Z द्वारा मार्ग किए गए उपट्री की ऊंचाई 1 बढ़ गई है। यह पूर्व से ही एवीएल आकार में है। | ||
{{Collapse top|सम्मिलित संचालन के लिए उदाहरण कोड}} | {{Collapse top|सम्मिलित संचालन के लिए उदाहरण कोड}} | ||
for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root) | for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root) | ||
Line 119: | Line 119: | ||
} | } | ||
// Unless loop is left via break, the height of the total tree increases by 1.{{Collapse bottom}} | // Unless loop is left via break, the height of the total tree increases by 1.{{Collapse bottom}} | ||
सभी ग्रंथि के संतुलन कारकों को अद्यतन करने के लिए, देखें कि सुधार की आवश्यकता वाले सभी ग्रंथि सम्मिलित पत्ते के पथ के साथ बच्चे से माता-पिता तक स्थित हैं। यदि उपरोक्त प्रक्रिया को पत्ती से प्रारम्भ करके इस पथ के ग्रंथि पर प्रस्तावित किया जाता है, तो | सभी ग्रंथि के संतुलन कारकों को अद्यतन करने के लिए, देखें कि सुधार की आवश्यकता वाले सभी ग्रंथि सम्मिलित पत्ते के पथ के साथ बच्चे से माता-पिता तक स्थित हैं। यदि उपरोक्त प्रक्रिया को पत्ती से प्रारम्भ करके इस पथ के ग्रंथि पर प्रस्तावित किया जाता है, तो ट्री के प्रत्येक ग्रंथि में -1, 0, या 1 का संतुलन कारक होगा। | ||
यदि संतुलन कारक 0 हो जाता है, तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस | यदि संतुलन कारक 0 हो जाता है, तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस उपट्री की ऊंचाई अपरिवर्तित रहती है। | ||
यदि संतुलन कारक ±1 हो जाता है, तो | यदि संतुलन कारक ±1 हो जाता है, तो उपट्री की ऊंचाई बढ़ जाती है और अनुसंधान प्रारम्भ रखने की आवश्यकता होती है। | ||
यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा ठीक किया जाना चाहिए, जिसके पश्चात् | यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा ठीक किया जाना चाहिए, जिसके पश्चात् उपट्री की ऊंचाई पूर्व प्रकार ही हो जाती है (और इसकी जड़ में संतुलन कारक 0 होता है)। | ||
समय की आवश्यकता है, {{math|O(log ''n'')}} लुकअप के लिए, साथ ही अधिकतम {{math|O(log ''n'')}} पुनः अनुरेखण स्तर ({{math|O(1)}} औसतन) मार्ग पर पुनः जा रहा है, जिससे संचालन {{math|O(log ''n'')}} समय में पूर्ण किया जा सके।<ref name="brass-advanced-data-structures" />{{rp|53}} | समय की आवश्यकता है, {{math|O(log ''n'')}} लुकअप के लिए, साथ ही अधिकतम {{math|O(log ''n'')}} पुनः अनुरेखण स्तर ({{math|O(1)}} औसतन) मार्ग पर पुनः जा रहा है, जिससे संचालन {{math|O(log ''n'')}} समय में पूर्ण किया जा सके।<ref name="brass-advanced-data-structures" />{{rp|53}} | ||
===विलोपन=== | ===विलोपन=== | ||
किसी ग्रंथि के विलोपन को प्रारंभिक चरण द्विआधारी परीक्षण | किसी ग्रंथि के विलोपन को प्रारंभिक चरण द्विआधारी परीक्षण ट्री विलोपन अनुभाग में वर्णित किया गया हैं। वहां, विषय ग्रंथि या प्रतिस्थापन ग्रंथि का प्रभावी विलोपन संबंधित चाइल्ड ट्री की ऊंचाई को 1 से 0 या 2 से 1 तक कम कर देता है, यदि उस ग्रंथि में बच्चा था। | ||
इस | इस उपट्री से प्रारम्भ करते हुए, एवीएल ट्रीों के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक पूर्वज की जांच करना आवश्यक है। इसे पुनः अनुरेखण कहा जाता है। | ||
चूँकि विलोपन से एवीएल | चूँकि विलोपन से एवीएल उपट्री की ऊँचाई से अधिक नहीं घट सकती, ग्रंथि का अस्थायी संतुलन कारक −2 से +2 तक की सीमा में होगा। यदि संतुलन कारक -1 से +1 की सीमा में रहता है, तो इसे एवीएल नियमों के अनुसार समायोजित किया जा सकता है। यदि यह ±2 हो जाता है, तो उपट्री असंतुलित है, और इसे घुमाने की आवश्यकता है। (सम्मिलन के विपरीत जहां घुमाव सदैव ट्री को संतुलित करता है, विलोपन के पश्चात्, BF(Z) ≠ 0 हो सकता है, (आंकड़े 2 और 3 देखें), जिससे उचित एकल या दोगुने घुमाव के पश्चात् पुनर्संतुलित उपट्री की ऊंचाई अर्थ से कम हो जाए कि ट्री को उच्च स्तर पर पुनः से संतुलित करना होगा।) घूर्णन के विभिन्न विषयों को खंड पुनर्संतुलन में वर्णित किया गया है। | ||
;विलोपन के लिए रिट्रेसिंग लूप का अपरिवर्तनीय | ;विलोपन के लिए रिट्रेसिंग लूप का अपरिवर्तनीय | ||
N द्वारा मार्ग किए गए | N द्वारा मार्ग किए गए उपट्री की ऊंचाई 1 से कम हो गई है। यह पूर्व से ही एवीएल आकार में है। | ||
{{Collapse top|विलोपन संचालन के लिए उदाहरण कोड}} | {{Collapse top|विलोपन संचालन के लिए उदाहरण कोड}} | ||
for (X = parent(N); X != null; X = G) { // Loop (possibly up to the root) | for (X = parent(N); X != null; X = G) { // Loop (possibly up to the root) | ||
Line 201: | Line 201: | ||
// If (b != 0) the height of the total tree decreases by 1. | // If (b != 0) the height of the total tree decreases by 1. | ||
{{Collapse bottom}} | {{Collapse bottom}} | ||
यदि संतुलन कारक ±1 हो जाता है (यह 0 रहा होगा) तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस | यदि संतुलन कारक ±1 हो जाता है (यह 0 रहा होगा) तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस उपट्री की ऊंचाई अपरिवर्तित रहती है। | ||
यदि संतुलन कारक 0 हो जाता है (यह ±1 होना चाहिए) तो | यदि संतुलन कारक 0 हो जाता है (यह ±1 होना चाहिए) तो उपट्री की ऊंचाई कम हो जाती है और अनुसंधान प्रारम्भ रखने की आवश्यकता होती है। | ||
यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा सही करना होगा। यह सहोदर Z (चित्र 2 में उच्च संतान | यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा सही करना होगा। यह सहोदर Z (चित्र 2 में उच्च संतान ट्री) के संतुलन कारक पर निर्भर करता है कि क्या उपट्री की ऊंचाई से कम हो जाती है- और अनुसंधान प्रारम्भ रखने की आवश्यकता है - या नहीं परिवर्तित होता है (यदि Z का संतुलन कारक 0 है) और पूर्ण ट्री एवीएल-आकार में है। | ||
समय की आवश्यकता है 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}} ऊंचाई में वृद्धि से इसके पूर्वजों की ऊंचाई बढ़ सकती है, संभवतः उन ग्रंथि के एवीएल अपरिवर्तनीय को अमान्य कर दिया जा सकता है। इसे या तो दोगुने घुमाव के साथ ठीक किया जा सकता है, यदि मूल पर अमान्य है या यदि ट्री में उच्चतर अमान्य है तो एकल बाएं घुमाव के साथ, दोनों ही विषयों में किसी भी पूर्वज ग्रंथि के लिए ऊंचाई को बहाल किया जा सकता है। इसलिए जॉइन के लिए अधिकतम दो घुमावों की आवश्यकता होगी। इस फलन की लागत दो इनपुट ट्रीों के मध्य की ऊंचाई का अंतर है। | ||
{{Collapse top|बांधना कलन विधि के लिए छदमकोड कार्यान्वयन}} | {{Collapse top|बांधना कलन विधि के लिए छदमकोड कार्यान्वयन}} | ||
function JoinRightAVL(TL, k, TR) | function JoinRightAVL(TL, k, TR) | ||
Line 243: | Line 243: | ||
{{Collapse bottom}} | {{Collapse bottom}} | ||
एवीएल | एवीएल ट्री को दो छोटे ट्रीों में विभाजित करना, जो कुंजी {{mvar|k}} से छोटे हों, और वे कुंजी {{mvar|k}} से बड़े हैं, पूर्व मार्ग से {{mvar|k}} एवीएल में हैं। इस प्रविष्टि के पश्चात्, सभी मान इससे कम होंगे {{mvar|k}} पथ के बायीं ओर मिलेगा, और सभी मान इससे बड़े होंगे {{mvar|k}} दाहिनी ओर मिलेगा I जॉइन प्रस्तावित करने से, बायीं ओर के सभी उपट्रीों को नीचे से ऊपर की ओर मध्यवर्ती ग्रंथि के रूप में पथ पर कुंजियों का उपयोग करके बाएँ ट्री बनाने के लिए विलय किया जाता है, और दायाँ भाग असममित होता है। विभाजित {{math|O(log ''n'')}}, ट्री की ऊंचाई का क्रम की लागत है I | ||
{{Collapse top|विभाजित कलन विधि के लिए स्यूडोकोड कार्यान्वयन}} | {{Collapse top|विभाजित कलन विधि के लिए स्यूडोकोड कार्यान्वयन}} | ||
function Split(T, k) | function Split(T, k) | ||
Line 256: | Line 256: | ||
return (Join(L, m, L'), b, R')){{Collapse bottom}} | return (Join(L, m, L'), b, R')){{Collapse bottom}} | ||
दो एवीएल | दो एवीएल ट्रीों का मिलन {{math|''t''<sub>1</sub>}} और {{math|''t''<sub>2</sub>}} समूह का प्रतिनिधित्व करना {{mvar|A}} और {{mvar|B}}, एवीएल है, {{mvar|''t''}} जो {{math|''A'' ∪ ''B''}} प्रतिनिधित्व करता है I | ||
{{Collapse top|यूनियन कलन विधि के लिए स्यूडोकोड कार्यान्वयन}} | {{Collapse top|यूनियन कलन विधि के लिए स्यूडोकोड कार्यान्वयन}} | ||
Line 270: | Line 270: | ||
{{Collapse bottom}} | {{Collapse bottom}} | ||
प्रतिच्छेदन या अंतर के लिए कलन विधि समान है, किन्तु इसके लिए जॉइन 2 हेल्पर मार्गीन की आवश्यकता होती है, जो कि जॉइन के समान है किन्तु मध्य कुंजी के बिना है। यूनियन, प्रतिच्छेदन या अंतर के नए कार्यों के आधार पर, एवीएल | प्रतिच्छेदन या अंतर के लिए कलन विधि समान है, किन्तु इसके लिए जॉइन 2 हेल्पर मार्गीन की आवश्यकता होती है, जो कि जॉइन के समान है किन्तु मध्य कुंजी के बिना है। यूनियन, प्रतिच्छेदन या अंतर के नए कार्यों के आधार पर, एवीएल ट्री में या तो एक कुंजी या अधिक कुंजियाँ डाली जा सकती हैं, या हटाई जा सकती हैं। चूंकि विभाजित कॉल जॉइन करता है किन्तु एवीएल ट्रीों के संतुलन मानदंडों से सीधे निपटता नहीं है, ऐसे कार्यान्वयन को सामान्यतः जॉइन-आधारित ट्री कलन विधि कहा जाता है I सम्मिलित-आधारित कार्यान्वयन मिलन, प्रतिच्छेद और भेद प्रत्येक की जटिलता <math>\text{O}\left(m \log \left({n\over m}+1\right)\right)</math> है, <math>m</math> और <math>n \; (\ge m)</math> आकार के एवीएल ट्रीों के लिए अधिक महत्वपूर्ण बात यह है कि चूंकि संघ, प्रतिच्छेदन या अंतर के लिए पुनरावर्ती कॉल -दूसरे से स्वतंत्र हैं, इसलिए उन्हें समानांतर कलन विधि के विश्लेषण के साथ [[समानांतर प्रोग्रामिंग]] निष्पादित की जा सकती है। <math>\text{O}(\log m\log n)</math>.<ref name="join-based" /> जब <math>m=1</math>, जुड़ाव-आधारित कार्यान्वयन में एकल-तत्व सम्मिलन और विलोपन के समान कम्प्यूटेशनल डीएजी है। | ||
==पुनर्संतुलन== | ==पुनर्संतुलन== | ||
यदि संशोधित संचालन के अंतर्गत दो चाइल्ड | यदि संशोधित संचालन के अंतर्गत दो चाइल्ड उपट्रीों के मध्य ऊंचाई का अंतर परिवर्तित होता है, तो यह, जब तक कि यह <2 है, मूल पर संतुलन सूचना के अनुकूलन द्वारा परिलक्षित हो सकता है। सम्मिलित करने और विलोपन के संचालन के अंतर्गत 2 का (अस्थायी) ऊंचाई अंतर उत्पन्न हो सकता है, जिसका अर्थ है कि मूल उपट्री को पुनर्संतुलित करना होगा। दिए गए उपकरण तथाकथित ट्री घुमाव हैं, क्योंकि वे कुंजियों को केवल लंबवत रूप से घुमाते हैं, जिससे कुंजियों का (क्षैतिज) क्रम क्रम पूर्ण प्रकार से संरक्षित रहे (जो द्विआधारी-सर्च ट्री के लिए आवश्यक है)।<ref name="Knuth"/>{{rp|458–481}} <ref name="Pfaff"/>{{rp|33}} | ||
मान लीजिए कि X वह ग्रंथि है जिसका (अस्थायी) संतुलन कारक -2 या +2 है। इसके बाएँ या दाएँ | मान लीजिए कि X वह ग्रंथि है जिसका (अस्थायी) संतुलन कारक -2 या +2 है। इसके बाएँ या दाएँ उपट्री को संशोधित किया गया था। मान लीजिए कि Z बड़ा बच्चा है (आंकड़े 2 और 3 देखें)। ध्यान दें कि दोनों बच्चे [[गणितीय प्रेरण]] द्वारा एवीएल आकार में हैं। | ||
सम्मिलन के विषय में यह सम्मिलन Z के बच्चों में से के साथ इस प्रकार से हुआ है कि Z की ऊंचाई बढ़ गई है। विलोपन के विषय में यह विलोपन सहोदर t<sub>1</sub> को हुआ है, Z प्रकार से जिससे t<sub>1</sub> की ऊंचाई पूर्व से ही कम होने के कारण कम हो गई है। (यह मात्र मामला है जहां Z का संतुलन कारक 0 भी हो सकता है।) | सम्मिलन के विषय में यह सम्मिलन Z के बच्चों में से के साथ इस प्रकार से हुआ है कि Z की ऊंचाई बढ़ गई है। विलोपन के विषय में यह विलोपन सहोदर t<sub>1</sub> को हुआ है, Z प्रकार से जिससे t<sub>1</sub> की ऊंचाई पूर्व से ही कम होने के कारण कम हो गई है। (यह मात्र मामला है जहां Z का संतुलन कारक 0 भी हो सकता है।) | ||
Line 307: | Line 307: | ||
===सरल घुमाव=== | ===सरल घुमाव=== | ||
चित्र 2 दाएं-दाएं स्थिति प्रदर्शित करता है। इसके ऊपरी अर्ध भाग में, ग्रंथि X में <span style= color:#FF0000; के संतुलन कारक के साथ दो चाइल्ड ट्री हैं; >+2</span>. इसके अतिरिक्त, आंतरिक बच्चा t<sub>23</sub> Z का (अर्थात, बायां बच्चा जब Z दायां बच्चा है, या दायां बच्चा जब Z बायां बच्चा है) अपने सहोदर t<sub>4</sub> से अधिक नहीं है I यह | चित्र 2 दाएं-दाएं स्थिति प्रदर्शित करता है। इसके ऊपरी अर्ध भाग में, ग्रंथि X में <span style= color:#FF0000; के संतुलन कारक के साथ दो चाइल्ड ट्री हैं; >+2</span>. इसके अतिरिक्त, आंतरिक बच्चा t<sub>23</sub> Z का (अर्थात, बायां बच्चा जब Z दायां बच्चा है, या दायां बच्चा जब Z बायां बच्चा है) अपने सहोदर t<sub>4</sub> से अधिक नहीं है I यह उपट्री t<sub>4</sub> की ऊंचाई बढ़ने से हो सकता है, या उपट्री t<sub>1</sub> की ऊंचाई में कमी से पश्चात् वाले विषय में भी, पीली स्थिति जहां t<sub>233</sub> इसकी ऊँचाई t<sub>4</sub> के समान है I | ||
बाएँ घुमाव का परिणाम चित्र के निचले अर्ध भाग में प्रदर्शित किया गया है। तीन लिंक (चित्र 2 में मोटे किनारे) और दो संतुलन कारकों को अद्यतन किया जाना है। | बाएँ घुमाव का परिणाम चित्र के निचले अर्ध भाग में प्रदर्शित किया गया है। तीन लिंक (चित्र 2 में मोटे किनारे) और दो संतुलन कारकों को अद्यतन किया जाना है। | ||
जैसा कि चित्र से ज्ञात होता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और घूमने के पश्चात् पुनः स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 स्तर पर थी, जहां यह पुनः है, जब t<sub>23</sub> और t<sub>4</sub> ही कद के थे. अन्यथा पत्ती की परत h+1 स्तर तक पहुंच जाती है, जिससे घूमने वाले | जैसा कि चित्र से ज्ञात होता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और घूमने के पश्चात् पुनः स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 स्तर पर थी, जहां यह पुनः है, जब t<sub>23</sub> और t<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)]]सरल बाएँ घुमाव का कोड स्निपेट | ||
{| | {| | ||
|- | |- | ||
| style="width:4em;" | इनपुट: || X = | | style="width:4em;" | इनपुट: || X = उपट्री की जड़ को बायीं ओर घुमाना है | ||
|- | |- | ||
| || Z = X, Z का दायाँ बच्चा दायाँ-भारी है | | || Z = X, Z का दायाँ बच्चा दायाँ-भारी है | ||
Line 322: | Line 322: | ||
| || with height == {{math|Height(LeftSubtree(}}X{{math|))+2}} | | || with height == {{math|Height(LeftSubtree(}}X{{math|))+2}} | ||
|- | |- | ||
|परिणाम: || पुनर्संतुलित | |परिणाम: || पुनर्संतुलित उपट्री की नई जड़ | ||
|} | |} | ||
Line 348: | Line 348: | ||
===दोहरा घुमाव === | ===दोहरा घुमाव === | ||
चित्र 3 दाएँ बाएँ स्थिति को प्रदर्शित करता है। इसके ऊपरी तीसरे भाग में, ग्रंथि X में <span style= color:#FF0000; के संतुलन कारक के साथ दो चाइल्ड ट्री हैं; >+2</span>. किन्तु चित्र 2 के विपरीत, Z का आंतरिक बच्चा Y उसके भाई t<sub>4</sub> से ऊंचा है I यह स्वयं Y के सम्मिलन या इसके किसी | चित्र 3 दाएँ बाएँ स्थिति को प्रदर्शित करता है। इसके ऊपरी तीसरे भाग में, ग्रंथि X में <span style= color:#FF0000; के संतुलन कारक के साथ दो चाइल्ड ट्री हैं; >+2</span>. किन्तु चित्र 2 के विपरीत, Z का आंतरिक बच्चा Y उसके भाई t<sub>4</sub> से ऊंचा है I यह स्वयं Y के सम्मिलन या इसके किसी उपट्री t<sub>2</sub> की ऊँचाई में वृद्धि से हो सकता है, या t<sub>3</sub> (इस परिणाम के साथ कि वे भिन्न-भिन्न ऊंचाई के हैं) या उपट्री t<sub>1</sub> की ऊंचाई में कमी से पश्चात् वाले विषय में, यह भी हो सकता है कि t<sub>2</sub> और t<sub>3</sub> समान ऊंचाई के हैं. | ||
पूर्व, दाएँ, घुमाव का परिणाम चित्र के मध्य तीसरे में दिखाया गया है। (संतुलन कारकों के संबंध में, यह घुमाव अन्य एवीएल एकल घुमावों के समान नहीं है, क्योंकि Y और t<sub>4</sub> के मध्य ऊंचाई का अंतर है केवल 1 है।) अंतिम बाएँ घुमाव का परिणाम चित्र के निचले तीसरे भाग में दिखाया गया है। पांच लिंक (चित्रा 3 में मोटे किनारे) और तीन संतुलन कारकों को अद्यतन किया जाना है। | पूर्व, दाएँ, घुमाव का परिणाम चित्र के मध्य तीसरे में दिखाया गया है। (संतुलन कारकों के संबंध में, यह घुमाव अन्य एवीएल एकल घुमावों के समान नहीं है, क्योंकि Y और t<sub>4</sub> के मध्य ऊंचाई का अंतर है केवल 1 है।) अंतिम बाएँ घुमाव का परिणाम चित्र के निचले तीसरे भाग में दिखाया गया है। पांच लिंक (चित्रा 3 में मोटे किनारे) और तीन संतुलन कारकों को अद्यतन किया जाना है। | ||
जैसा कि चित्र से ज्ञात होता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और दोहरे घुमाव के पश्चात् पुनः स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 के स्तर पर थी और दोहरे घुमाव के पश्चात् यह h+1 के स्तर पर थी, जिससे कि घुमाए गए | जैसा कि चित्र से ज्ञात होता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और दोहरे घुमाव के पश्चात् पुनः स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 के स्तर पर थी और दोहरे घुमाव के पश्चात् यह h+1 के स्तर पर थी, जिससे कि घुमाए गए ट्री की ऊंचाई कम हो गई। | ||
[[File:AVL-double-rl_K.svg|thumb|right|264px|चित्र 3: डबल घुमाव दाएँ बाएँ (''X'',''Z'')<br/>= घुमाव _दाएँ ''Z'' के चारों ओर और उसके पश्चात् ''X''<br/>के चारों ओर बाएँ घुमाएँ]];दाएँ-बाएँ दोहरे घुमाव का कोड स्निपेट | [[File:AVL-double-rl_K.svg|thumb|right|264px|चित्र 3: डबल घुमाव दाएँ बाएँ (''X'',''Z'')<br/>= घुमाव _दाएँ ''Z'' के चारों ओर और उसके पश्चात् ''X''<br/>के चारों ओर बाएँ घुमाएँ]];दाएँ-बाएँ दोहरे घुमाव का कोड स्निपेट | ||
{| | {| | ||
|- | |- | ||
| style="width:4em;" | इनपुट: || X = | | style="width:4em;" | इनपुट: || X = उपट्री की जड़ को घुमाना है | ||
|- | |- | ||
| || Z = इसका दाहिना बच्चा, बायाँ-भारी | | || Z = इसका दाहिना बच्चा, बायाँ-भारी | ||
Line 363: | Line 363: | ||
| || with height == {{math|Height(LeftSubtree(}}X{{math|))+2}} | | || with height == {{math|Height(LeftSubtree(}}X{{math|))+2}} | ||
|- | |- | ||
|परिणाम: || पुनर्संतुलित | |परिणाम: || पुनर्संतुलित उपट्री की नई जड़ | ||
|} | |} | ||
Line 403: | Line 403: | ||
==अन्य संरचनाओं से तुलना== | ==अन्य संरचनाओं से तुलना== | ||
एवीएल | एवीएल ट्री और लाल-काले (आरबी) ट्री दोनों स्व-संतुलन वाले द्विआधारी परीक्षण ट्री हैं, और वे गणितीय रूप से संबंधित हैं। प्रत्येक एवीएल ट्री को लाल-काला रंग दिया जा सकता है,<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> किन्तु ऐसे आरबी ट्री हैं जो एवीएल संतुलित नहीं हैं। एवीएल (या आरबी) ट्री के अपरिवर्तनीयों को बनाए रखने के लिए, घुमाव महत्वपूर्ण भूमिका निभाते हैं। सबसे अमान्य स्थिति में, घुमाव के बिना भी, एवीएल या आरबी सम्मिलन या विलोपन की आवश्यकता होती है I {{math|O(log ''n'')}} एवीएल संतुलन कारकों (या आरबी रंग) का निरीक्षण और/या अद्यतन आरबी सम्मिलन और विलोपन और एवीएल सम्मिलन के लिए शून्य से तीन [[ पूँछ बुलाओ |टेल-रिकर्सिव]] घुमाव की आवश्यकता होती है और {{math|O(1)}} समय अमूर्त विश्लेषण में चलाया जाता है I<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> इस प्रकार औसतन समान रूप से स्थिर एवीएल विलोपन की आवश्यकता है I {{math|O(log ''n'')}} सबसे अमान्य स्थिति में भी घुमाव होते हैं, {{math|O(1)}} औसत पर आरबी ट्री को प्रत्येक ग्रंथि में बिट जानकारी (रंग) संग्रहीत करने की आवश्यकता होती है, जबकि एवीएल ट्री अधिकतर संतुलन कारक के लिए दो बिट्स का उपयोग करते हैं, चूँकि, जब बच्चों पर संग्रहीत किया जाता है, तो "सहोदर से कम" अर्थ वाला बिट पर्याप्त होता है। दो डेटा संरचनाओं के मध्य बड़ा अंतर उनकी ऊंचाई सीमा है। | ||
{{math|''n'' ≥ 1}} आकार के | {{math|''n'' ≥ 1}} आकार के ट्री के लिए :- | ||
*एवीएल | *एवीएल ट्री की ऊंचाई अधिकतम होती है | ||
*:<math> | *:<math> | ||
\begin{array}{ll} | \begin{array}{ll} | ||
Line 414: | Line 414: | ||
</math> | </math> | ||
:जहाँ <math>\varphi := \tfrac{1+\sqrt 5}2 \approx 1.618</math> सुनहरा अनुपात, <math>c := \tfrac 1{\log_2 \varphi} \approx 1.440,</math> <math>b := \tfrac{c}2 \log_2 5 - 2 \approx \; -0.328,</math> और <math>d:=1+\tfrac{1}{\varphi^4\sqrt{5}} \approx 1.065</math>. | :जहाँ <math>\varphi := \tfrac{1+\sqrt 5}2 \approx 1.618</math> सुनहरा अनुपात, <math>c := \tfrac 1{\log_2 \varphi} \approx 1.440,</math> <math>b := \tfrac{c}2 \log_2 5 - 2 \approx \; -0.328,</math> और <math>d:=1+\tfrac{1}{\varphi^4\sqrt{5}} \approx 1.065</math>. | ||
*आरबी | *आरबी ट्री की ऊंचाई अधिकतम होती है:- | ||
*:<math> | *:<math> | ||
\begin{array}{ll} | \begin{array}{ll} | ||
Line 420: | Line 420: | ||
\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 के मध्य एवीएल/आरबी का संबंध प्रदर्शित करता है।<ref name="Pfaff1"/> | ||
==यह भी देखें== | ==यह भी देखें== | ||
*[[WAVL पेड़|डव्लूएवीएल | *[[WAVL पेड़|डव्लूएवीएल ट्री]] | ||
*छींटे का | *छींटे का ट्री | ||
*[[बलि का बकरा पेड़|स्केपगोट | *[[बलि का बकरा पेड़|स्केपगोट ट्री]] | ||
*[[बी-वृक्ष]] | *[[बी-वृक्ष|बी-ट्री]] | ||
*टी- | *टी-ट्री | ||
*[[डेटा संरचनाओं की सूची]] | *[[डेटा संरचनाओं की सूची]] | ||
Revision as of 10:32, 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
|