एवीएल ट्री: Difference between revisions
No edit summary |
No edit summary |
||
Line 17: | Line 17: | ||
[[Image:AVL-tree-wBalance_K.svg|thumb|right|262px|चित्र 1: संतुलन कारकों के साथ एवीएल ट्री (हरा)]][[कंप्यूटर विज्ञान]] में, '''एवीएल ट्री''' (आविष्कारकों एडेलसन-वेल्स्की और लैंडिस के नाम पर) [[स्व-संतुलन द्विआधारी खोज वृक्ष|स्व-संतुलन द्विआधारी परीक्षण ट्री]] है। एवीएल ट्री में, किसी भी ग्रंथि के दो [[ बाल नोड्स |बाल ग्रंथि]] उपट्री की ऊंचाई अधिकतम से भिन्न होती है; यदि किसी भी समय उनमें से अधिक का अंतर होता है, तो इस संपत्ति को पुनर्स्थापित करने के लिए पुनर्संतुलन किया जाता है। लुकअप, सम्मिलन और विलोपन सभी लेते हैं I {{math|[[big O notation|O]](log ''n'')}} औसत और सबसे अमान्य दोनों विषयों में समय, जहां <math>n</math> संचालन से पूर्व ट्री में ग्रंथि की संख्या है। सम्मिलन और विलोपन के लिए ट्री को या अधिक ट्री घुमावों द्वारा पुनर्संतुलित करने की आवश्यकता हो सकती है I | [[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> एवीएल | एवीएल ट्री का नाम इसके दो [[सोवियत संघ]] के आविष्कारकों, [[जॉर्जी एडेल्सन-वेल्स्की]] और [[एवगेनी लैंडिस]] के नाम पर रखा गया है, जिन्होंने इसे अपने 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 29: | Line 29: | ||
:<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> | ||
Line 41: | Line 41: | ||
इसका कारण ऊंचाई <math>h</math> का एवीएल ट्री है, <math>F_{h}-1</math> कम से कम सम्मिलित है I ग्रंथि जहाँ <math>\{F_n\}_{n\in\N}</math> बीज मूल्यों के साथ [[फाइबोनैचि संख्या]] <math>F_1=F_2=1 .</math> है I | इसका कारण ऊंचाई <math>h</math> का एवीएल ट्री है, <math>F_{h}-1</math> कम से कम सम्मिलित है I ग्रंथि जहाँ <math>\{F_n\}_{n\in\N}</math> बीज मूल्यों के साथ [[फाइबोनैचि संख्या]] <math>F_1=F_2=1 .</math> है I | ||
==संचालन== | ==संचालन== | ||
एवीएल ट्री के रीड-ओनली संचालन में वही क्रियाएं सम्मिलित होती हैं, जो असंतुलित [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण ट्री]] पर की जाती हैं, किन्तु संशोधनों में उप- | एवीएल ट्री के रीड-ओनली संचालन में वही क्रियाएं सम्मिलित होती हैं, जो असंतुलित [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण ट्री]] पर की जाती हैं, किन्तु संशोधनों में उप-ट्री की ऊंचाई संतुलन का निरीक्षण करना और पुनर्स्थापित करना होता है। | ||
===अन्वेषण=== | ===अन्वेषण=== | ||
Line 54: | Line 54: | ||
एवीएल ट्री में ग्रंथि के प्रवेश होते समय, आप प्रारम्भ में [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण ट्री]] में प्रवेश जैसी ही प्रक्रिया का पालन करते हैं। यदि ट्री रिक्त है, तो ग्रंथि को ट्री की जड़ के रूप में डाला जाता है। यदि ट्री रिक्त नहीं है, तो हम जड़ के नीचे जाते हैं, और नए ग्रंथि को सम्मिलित करने के लिए स्थान का परीक्षण करते हुए पुनरावर्ती रूप से ट्री के नीचे जाते हैं। यह ट्रैवर्सल तुलना फलन द्वारा निर्देशित होता है। इस विषय में, ग्रंथि सदैव ट्री में किसी बाहरी ग्रंथि के अशक्त संदर्भ (बाएं या दाएं) को प्रतिस्थापित करता है, जिससे, ग्रंथि को या तो बाहरी ग्रंथि का बायां-चाइल्ड या दायां-चाइल्ड बनाया जाता है। | एवीएल ट्री में ग्रंथि के प्रवेश होते समय, आप प्रारम्भ में [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण ट्री]] में प्रवेश जैसी ही प्रक्रिया का पालन करते हैं। यदि ट्री रिक्त है, तो ग्रंथि को ट्री की जड़ के रूप में डाला जाता है। यदि ट्री रिक्त नहीं है, तो हम जड़ के नीचे जाते हैं, और नए ग्रंथि को सम्मिलित करने के लिए स्थान का परीक्षण करते हुए पुनरावर्ती रूप से ट्री के नीचे जाते हैं। यह ट्रैवर्सल तुलना फलन द्वारा निर्देशित होता है। इस विषय में, ग्रंथि सदैव ट्री में किसी बाहरी ग्रंथि के अशक्त संदर्भ (बाएं या दाएं) को प्रतिस्थापित करता है, जिससे, ग्रंथि को या तो बाहरी ग्रंथि का बायां-चाइल्ड या दायां-चाइल्ड बनाया जाता है। | ||
इस प्रविष्टि के पश्चात्, यदि कोई ट्री असंतुलित हो जाता है, तो केवल नए डाले गए ग्रंथि के पूर्वज असंतुलित होते हैं। ऐसा इसलिए है क्योंकि केवल उन ग्रंथि के उप-ट्री परिवर्तित किये गए हैं।<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>{{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}} जैसा कि नीचे दिए गए कोड से ज्ञात होता है, सम्मिलन के साथ, पर्याप्त नियमित आवर्तन ट्री को पुनः संतुलित करता है। | चूंकि एकल सम्मिलन के साथ एवीएल अर्धट्री की ऊंचाई से अधिक नहीं बढ़ सकती है, सम्मिलन के पश्चात् ग्रंथि का अस्थायी संतुलन कारक सीमा {{nowrap|[–2,+2].}} में होगा I परीक्षण किये गए प्रत्येक ग्रंथि के लिए, यदि अस्थायी संतुलन कारक -1 से +1 तक की सीमा में रहता है, तो केवल संतुलन कारक का अद्यतन और कोई नियमित आवर्तन आवश्यक नहीं है। चूंकि, यदि अस्थायी संतुलन कारक ±2 है, तो इस ग्रंथि पर निहित उपट्री एवीएल असंतुलित है, और नियमित आवर्तन की आवश्यकता है।<ref name="brass-advanced-data-structures" />{{rp|52}} जैसा कि नीचे दिए गए कोड से ज्ञात होता है, सम्मिलन के साथ, पर्याप्त नियमित आवर्तन ट्री को पुनः संतुलित करता है। | ||
Line 132: | Line 132: | ||
किसी ग्रंथि के विलोपन को प्रारंभिक चरण द्विआधारी परीक्षण ट्री विलोपन अनुभाग में वर्णित किया गया हैं। वहां, विषय ग्रंथि या प्रतिस्थापन ग्रंथि का प्रभावी विलोपन संबंधित चाइल्ड ट्री की ऊंचाई को 1 से 0 या 2 से 1 तक कम कर देता है, यदि उस ग्रंथि में बच्चा था। | किसी ग्रंथि के विलोपन को प्रारंभिक चरण द्विआधारी परीक्षण ट्री विलोपन अनुभाग में वर्णित किया गया हैं। वहां, विषय ग्रंथि या प्रतिस्थापन ग्रंथि का प्रभावी विलोपन संबंधित चाइल्ड ट्री की ऊंचाई को 1 से 0 या 2 से 1 तक कम कर देता है, यदि उस ग्रंथि में बच्चा था। | ||
इस उपट्री से प्रारम्भ करते हुए, एवीएल | इस उपट्री से प्रारम्भ करते हुए, एवीएल ट्री के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक पूर्वज की जांच करना आवश्यक है। इसे पुनः अनुरेखण कहा जाता है। | ||
चूँकि विलोपन से एवीएल उपट्री की ऊँचाई से अधिक नहीं घट सकती, ग्रंथि का अस्थायी संतुलन कारक −2 से +2 तक की सीमा में होगा। यदि संतुलन कारक -1 से +1 की सीमा में रहता है, तो इसे एवीएल नियमों के अनुसार समायोजित किया जा सकता है। यदि यह ±2 हो जाता है, तो उपट्री असंतुलित है, और इसे घुमाने की आवश्यकता है। (सम्मिलन के विपरीत जहां घुमाव सदैव ट्री को संतुलित करता है, विलोपन के पश्चात्, BF(Z) ≠ 0 हो सकता है, (आंकड़े 2 और 3 देखें), जिससे उचित एकल या दोगुने घुमाव के पश्चात् पुनर्संतुलित उपट्री की ऊंचाई अर्थ से कम हो जाए कि ट्री को उच्च स्तर पर पुनः से संतुलित करना होगा।) घूर्णन के विभिन्न विषयों को खंड पुनर्संतुलन में वर्णित किया गया है। | चूँकि विलोपन से एवीएल उपट्री की ऊँचाई से अधिक नहीं घट सकती, ग्रंथि का अस्थायी संतुलन कारक −2 से +2 तक की सीमा में होगा। यदि संतुलन कारक -1 से +1 की सीमा में रहता है, तो इसे एवीएल नियमों के अनुसार समायोजित किया जा सकता है। यदि यह ±2 हो जाता है, तो उपट्री असंतुलित है, और इसे घुमाने की आवश्यकता है। (सम्मिलन के विपरीत जहां घुमाव सदैव ट्री को संतुलित करता है, विलोपन के पश्चात्, BF(Z) ≠ 0 हो सकता है, (आंकड़े 2 और 3 देखें), जिससे उचित एकल या दोगुने घुमाव के पश्चात् पुनर्संतुलित उपट्री की ऊंचाई अर्थ से कम हो जाए कि ट्री को उच्च स्तर पर पुनः से संतुलित करना होगा।) घूर्णन के विभिन्न विषयों को खंड पुनर्संतुलन में वर्णित किया गया है। | ||
Line 210: | Line 210: | ||
===संचालन और थोक संचालन संग्रह करें=== | ===संचालन और थोक संचालन संग्रह करें=== | ||
एकल तत्व इंसर्ट, डिलीट और लुकअप विकल्प के अतिरिक्त, एवीएल ट्री पर अनेक समूह विकल्प को परिभाषित किया गया है: [[ संघ (सेट सिद्धांत) |संघ (समूह सिद्धांत)]], [[ प्रतिच्छेदन (सेट सिद्धांत) |प्रतिच्छेदन (समूह सिद्धांत)]] और [[ अंतर सेट करें |अंतर समूह]] आदि I इन समूह फलन के आधार पर सम्मिलन या विलोपन पर तीव्र बल्क संचालन प्रस्तावित किया जा सकता है। ये समूह संचालन दो सहायक संचालन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, एवीएल | एकल तत्व इंसर्ट, डिलीट और लुकअप विकल्प के अतिरिक्त, एवीएल ट्री पर अनेक समूह विकल्प को परिभाषित किया गया है: [[ संघ (सेट सिद्धांत) |संघ (समूह सिद्धांत)]], [[ प्रतिच्छेदन (सेट सिद्धांत) |प्रतिच्छेदन (समूह सिद्धांत)]] और [[ अंतर सेट करें |अंतर समूह]] आदि 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 है। इसके बाएँ या दाएँ उपट्री को संशोधित किया गया था। मान लीजिए कि Z बड़ा बच्चा है (आंकड़े 2 और 3 देखें)। ध्यान दें कि दोनों बच्चे [[गणितीय प्रेरण]] द्वारा एवीएल आकार में हैं। | मान लीजिए कि X वह ग्रंथि है जिसका (अस्थायी) संतुलन कारक -2 या +2 है। इसके बाएँ या दाएँ उपट्री को संशोधित किया गया था। मान लीजिए कि Z बड़ा बच्चा है (आंकड़े 2 और 3 देखें)। ध्यान दें कि दोनों बच्चे [[गणितीय प्रेरण]] द्वारा एवीएल आकार में हैं। |
Revision as of 10:35, 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
|