एवीएल ट्री: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(8 intermediate revisions by 5 users not shown)
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> संचालन से पूर्व पेड़ में ग्रंथि की संख्या है। सम्मिलन और विलोपन के लिए पेड़ को या अधिक वृक्ष घुमावों द्वारा पुनर्संतुलित करने की आवश्यकता हो सकती है 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> एवीएल पेड़ों की तुलना प्रायः लाल-काले पेड़ों से की जाती है, क्योंकि दोनों संचालन और टेक के समान समूह का समर्थन करते हैं 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


:<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>
holds and <math>\mu</math> is minimal with this property. <math>|N|</math> is the number of nodes below the tree with <math>N</math> as root (including the root) and <math>N_l</math> is the left child node of <math>N</math>.</ref> अर्थात्, सहोदर ग्रंथि में वंशजों की संख्या बहुत भिन्न हो सकती है।
holds and <math>\mu</math> is minimal with this property. <math>|N|</math> is the number of nodes below the tree with <math>N</math> as root (including the root) and <math>N_l</math> is the left child node of <math>N</math>.</ref> अर्थात्, सहोदर नोड्स में वंशजों की संख्या बहुत भिन्न हो सकती है।


==परिभाषा==
==परिभाषा==


===संतुलन कारक===
===संतुलन कारक===
[[ द्विआधारी वृक्ष | द्विआधारी वृक्ष]] में ग्रंथि के संतुलन कारक को ऊंचाई अंतर के रूप में परिभाषित किया गया है:-
[[ द्विआधारी वृक्ष | द्विआधारी ट्री]] में नोड्स के संतुलन कारक को ऊंचाई अंतर के रूप में परिभाषित किया गया है:-


:<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 के लिए धारण करता है।
ट्री में प्रत्येक नोड्स 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> (स्तरों की अधिकतम संख्या के रूप में गिना जाता है) एवीएल वृक्ष के साथ <math>n</math> ग्रंथि अंतराल में निहित हैं:<ref name="Knuth"/>{{rp|460}}
पूर्व संतुलन कारकों और ऊंचाई में परिवर्तन को समझकर संतुलन कारकों को अद्यतन रखा जा सकता है- पूर्ण ऊंचाई जानना आवश्यक नहीं है। एवीएल संतुलन जानकारी रखने के लिए, प्रति नोड्स दो बिट पर्याप्त हैं।<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>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  
==संचालन==
==संचालन==
एवीएल पेड़ के रीड-ओनली संचालन में वही क्रियाएं सम्मिलित होती हैं, जो असंतुलित [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण पेड़]] पर की जाती हैं, किन्तु संशोधनों में उप-पेड़ों की ऊंचाई संतुलन का निरीक्षण करना और पुनर्स्थापित करना होता है।
एवीएल ट्री के रीड-ओनली संचालन में वही क्रियाएं सम्मिलित होती हैं, जो असंतुलित [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण ट्री]] पर की जाती हैं, किन्तु संशोधनों में अर्ध-ट्री की ऊंचाई संतुलन का निरीक्षण करना और पुनर्स्थापित करना होता है।


===अन्वेषण===
===अन्वेषण===
एवीएल पेड़ में विशिष्ट कुंजी के परीक्षण उसी प्रकार से किये जा सकते है जैसे किसी संतुलित या असंतुलित द्विआधारी परीक्षण पेड़ अन्वेषण की होती है।<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}}
एवीएल ट्री में विशिष्ट कुंजी के परीक्षण उसी प्रकार से किये जा सकते है जैसे किसी संतुलित या असंतुलित द्विआधारी परीक्षण ट्री अन्वेषण की होती है।<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''}} पेड़ के ग्रंथि प्रत्येक लिंक पर ठीक दो बार जाते हैं: नीचे की ओर जाने वाली यात्रा उस ग्रंथि द्वारा निहित उप-वृक्ष में प्रवेश करने के लिए, दूसरी ऊपर की ओर जाने वाली यात्रा उस ग्रंथि के उप-वृक्ष का पता लगाने के पश्चात् उसे त्यागने के लिए जाती है।
रीड-ओनली विकल्प के रूप में एवीएल ट्री का ट्रैवर्सल किसी अन्य द्विआधारी ट्री के जैसे ही कार्य करता है। सभी का अन्वेषण {{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 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}}
इस प्रविष्टि के पश्चात्, यदि कोई ट्री असंतुलित हो जाता है, तो केवल नए डाले गए नोड्स के पूर्वज असंतुलित होते हैं। ऐसा इसलिए है क्योंकि केवल उन नोड्स के अर्ध-ट्री परिवर्तित किये गए हैं।<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}} जैसा कि नीचे दिए गए कोड से ज्ञात होता है, सम्मिलन के साथ, पर्याप्त नियमित आवर्तन ट्री को पुनः संतुलित करता है।


चित्र 1 में, ग्रंथि X के चाइल्ड के रूप में नया ग्रंथि Z डालने से उस उपपेड़ Z की ऊंचाई 0 से 1 तक बढ़ जाती है।
चित्र 1 में, नोड्स X के चाइल्ड के रूप में नया नोड्स Z डालने से उस अर्धट्री Z की ऊंचाई 0 से 1 तक बढ़ जाती है।


;सम्मिलन के लिए अनुसंधान लूप का [[लूप अपरिवर्तनीय]]
;सम्मिलन के लिए अनुसंधान लूप का [[लूप अपरिवर्तनीय]]
Z द्वारा मार्ग किए गए उपपेड़ की ऊंचाई 1 बढ़ गई है। यह पूर्व से ही एवीएल आकार में है।
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 का संतुलन कारक होगा।
सभी नोड्स के संतुलन कारकों को अद्यतन करने के लिए, देखें कि सुधार की आवश्यकता वाले सभी नोड्स सम्मिलित पत्ते के पथ के साथ बच्चे से माता-पिता तक स्थित हैं। यदि अर्धरोक्त प्रक्रिया को पत्ती से प्रारम्भ करके इस पथ के नोड्स पर प्रस्तावित किया जाता है, तो ट्री के प्रत्येक नोड्स में -1, 0, या 1 का संतुलन कारक होगा।


यदि संतुलन कारक 0 हो जाता है, तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस उपवृक्ष की ऊंचाई अपरिवर्तित रहती है।
यदि संतुलन कारक 0 हो जाता है, तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस अर्धट्री की ऊंचाई अपरिवर्तित रहती है।


यदि संतुलन कारक ±1 हो जाता है, तो उपवृक्ष की ऊंचाई बढ़ जाती है और अनुसंधान प्रारम्भ रखने की आवश्यकता होती है।
यदि संतुलन कारक ±1 हो जाता है, तो अर्धट्री की ऊंचाई बढ़ जाती है और अनुसंधान प्रारम्भ रखने की आवश्यकता होती है।


यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा ठीक किया जाना चाहिए, जिसके पश्चात् उपवृक्ष की ऊंचाई पूर्व प्रकार ही हो जाती है (और इसकी जड़ में संतुलन कारक 0 होता है)।
यदि संतुलन कारक अस्थायी रूप से ±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 तक कम कर देता है, यदि उस ग्रंथि में बच्चा था।
किसी नोड्स के विलोपन को प्रारंभिक चरण द्विआधारी परीक्षण ट्री विलोपन अनुभाग में वर्णित किया गया हैं। वहां, विषय नोड्स या प्रतिस्थापन नोड्स का प्रभावी विलोपन संबंधित चाइल्ड ट्री की ऊंचाई को 1 से 0 या 2 से 1 तक कम कर देता है, यदि उस नोड्स में बच्चा था।


इस उपवृक्ष से प्रारम्भ करते हुए, एवीएल पेड़ों के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक पूर्वज की जांच करना आवश्यक है। इसे पुनः अनुरेखण कहा जाता है।
इस अर्धट्री से प्रारम्भ करते हुए, एवीएल ट्री के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक पूर्वज की जांच करना आवश्यक है। इसे पुनः अनुरेखण कहा जाता है।


चूँकि विलोपन से एवीएल उपवृक्ष की ऊँचाई से अधिक नहीं घट सकती, ग्रंथि का अस्थायी संतुलन कारक −2 से +2 तक की सीमा में होगा। यदि संतुलन कारक -1 से +1 की सीमा में रहता है, तो इसे एवीएल नियमों के अनुसार समायोजित किया जा सकता है। यदि यह ±2 हो जाता है, तो उपवृक्ष असंतुलित है, और इसे घुमाने की आवश्यकता है। (सम्मिलन के विपरीत जहां घुमाव सदैव पेड़ को संतुलित करता है, विलोपन के पश्चात्, BF(Z) ≠ 0 हो सकता है, (आंकड़े 2 और 3 देखें), जिससे उचित एकल या दोगुने घुमाव के पश्चात् पुनर्संतुलित उपपेड़ की ऊंचाई अर्थ से कम हो जाए कि पेड़ को उच्च स्तर पर पुनः से संतुलित करना होगा।) घूर्णन के विभिन्न विषयों को खंड पुनर्संतुलन में वर्णित किया गया है।
चूँकि विलोपन से एवीएल अर्धट्री की ऊँचाई से अधिक नहीं घट सकती, नोड्स का अस्थायी संतुलन कारक −2 से +2 तक की सीमा में होगा। यदि संतुलन कारक -1 से +1 की सीमा में रहता है, तो इसे एवीएल नियमों के अनुसार समायोजित किया जा सकता है। यदि यह ±2 हो जाता है, तो अर्धट्री असंतुलित है, और इसे घुमाने की आवश्यकता है। (सम्मिलन के विपरीत जहां घुमाव सदैव ट्री को संतुलित करता है, विलोपन के पश्चात्, BF(Z) ≠ 0 हो सकता है, (आंकड़े 2 और 3 देखें), जिससे उचित एकल या दोगुने घुमाव के पश्चात् पुनर्संतुलित अर्धट्री की ऊंचाई अर्थ से कम हो जाए कि ट्री को उच्च स्तर पर पुनः से संतुलित करना होगा।) घूर्णन के विभिन्न विषयों को खंड पुनर्संतुलन में वर्णित किया गया है।


;विलोपन के लिए रिट्रेसिंग लूप का अपरिवर्तनीय
;विलोपन के लिए रिट्रेसिंग लूप का अपरिवर्तनीय
N द्वारा मार्ग किए गए उपवृक्ष की ऊंचाई 1 से कम हो गई है। यह पूर्व से ही एवीएल आकार में है।
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 में उच्च संतान वृक्ष) के संतुलन कारक पर निर्भर करता है कि क्या उपवृक्ष की ऊंचाई से कम हो जाती है- और अनुसंधान प्रारम्भ रखने की आवश्यकता है - या नहीं परिवर्तित होता है (यदि Z का संतुलन कारक 0 है) और पूर्ण पेड़ एवीएल-आकार में है।
यदि संतुलन कारक अस्थायी रूप से ±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
एकल तत्व इंसर्ट, डिलीट और लुकअप विकल्प के अतिरिक्त, एवीएल ट्री पर अनेक समूह विकल्प को परिभाषित किया गया है: [[ संघ (सेट सिद्धांत) |संघ (समूह सिद्धांत)]], [[ प्रतिच्छेदन (सेट सिद्धांत) |प्रतिच्छेदन (समूह सिद्धांत)]] और [[ अंतर सेट करें |अंतर समूह]] आदि 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> फलन दो एवीएल पेड़ों पर जुड़ें {{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}} ऊंचाई में वृद्धि से इसके पूर्वजों की ऊंचाई बढ़ सकती है, संभवतः उन ग्रंथि के एवीएल अपरिवर्तनीय को अमान्य कर दिया जा सकता है। इसे या तो दोगुने घुमाव के साथ ठीक किया जा सकता है, यदि मूल पर अमान्य है या यदि पेड़ में उच्चतर अमान्य है तो एकल बाएं घुमाव के साथ, दोनों ही विषयों में किसी भी पूर्वज ग्रंथि के लिए ऊंचाई को बहाल किया जा सकता है। इसलिए जॉइन के लिए अधिकतम दो घुमावों की आवश्यकता होगी। इस फलन की लागत दो इनपुट पेड़ों के मध्य की ऊंचाई का अंतर है।
  }}.</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
एवीएल ट्री को दो छोटे ट्री में विभाजित करना, जो कुंजी {{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
दो एवीएल ट्री का मिलन {{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 हेल्पर मार्गीन की आवश्यकता होती है, जो कि जॉइन के समान है किन्तु मध्य कुंजी के बिना है। यूनियन, प्रतिच्छेदन या अंतर के नए कार्यों के आधार पर, एवीएल पेड़ में या तो एक कुंजी या अधिक कुंजियाँ डाली जा सकती हैं, या हटाई जा सकती हैं। चूंकि विभाजित कॉल जॉइन करता है किन्तु एवीएल पेड़ों के संतुलन मानदंडों से सीधे निपटता नहीं है, ऐसे कार्यान्वयन को सामान्यतः जॉइन-आधारित पेड़ कलन विधि कहा जाता है 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 हेल्पर मार्गीन की आवश्यकता होती है, जो कि जॉइन के समान है किन्तु मध्य कुंजी के बिना है। यूनियन, प्रतिच्छेदन या अंतर के नए कार्यों के आधार पर, एवीएल ट्री में या तो एक कुंजी या अधिक कुंजियाँ डाली जा सकती हैं, या हटाई जा सकती हैं। चूंकि विभाजित कॉल जॉइन करता है किन्तु एवीएल ट्री के संतुलन मानदंडों से सीधे निपटता नहीं है, ऐसे कार्यान्वयन को सामान्यतः जॉइन-आधारित ट्री कलन विधि कहा जाता है 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}}
यदि संशोधित संचालन के अंतर्गत दो चाइल्ड अर्धट्री के मध्य ऊंचाई का अंतर परिवर्तित होता है, तो यह, जब तक कि यह <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 की ऊंचाई बढ़ गई है। विलोपन के विषय में यह विलोपन सहोदर 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 283: Line 283:
{|  
{|  
|-
|-
| style="width:1em" | || दाएँ दाएँ || ⟹ Z is a ''right'' || इसके माता-पिता X और BF(Z) का बच्चा ≥ 0
| style="width:1em" | || दाएँ दाएँ || ⟹ Z दायां है || इसके माता-पिता X और BF(Z) का बच्चा ≥ 0
|-
|-
| || बाएँ बाएँ || ⟹ Z is a ''left'' || इसके माता-पिता X और BF(Z) का बच्चा ≤ 0
| || बाएँ बाएँ || ⟹ Z बायां है || इसके माता-पिता X और BF(Z) का बच्चा ≤ 0
|-
|-
| || दाएँ बाएँ || ⟹ Z is a ''right'' || इसके माता-पिता X और BF(Z) का बच्चा < 0
| || दाएँ बाएँ || ⟹ Z दायां है || इसके माता-पिता X और BF(Z) का बच्चा < 0
|-
|-
| || बाएँ दाएँ || ⟹ Z is a ''left'' || इसके माता-पिता X और BF(Z) का बच्चा > 0
| || बाएँ दाएँ || ⟹ Z बायां है || इसके माता-पिता X और BF(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 यह उपपेड़ t<sub>4</sub> की ऊंचाई बढ़ने से हो सकता है, या उपवृक्ष t<sub>1</sub> की ऊंचाई में कमी से पश्चात् वाले विषय में भी, पीली स्थिति जहां  t<sub>233</sub> इसकी ऊँचाई 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;" | Input: || X = root of subtree to be rotated left
| style="width:4em;" | इनपुट: || X = अर्धट्री की जड़ को बायीं ओर घुमाना है
|-
|-
| || Z = right child of X, Z is right-heavy
| || Z = X, Z का दायाँ बच्चा दायाँ-भारी है
|-
|-
| || &nbsp; &nbsp; with height == {{math|Height(LeftSubtree(}}X{{math|))+2}}
| || &nbsp; &nbsp; with height == {{math|Height(LeftSubtree(}}X{{math|))+2}}
|-
|-
|Result: || new root of rebalanced subtree
|परिणाम: || पुनर्संतुलित अर्धट्री की नई जड़
|}
|}


Line 348: Line 348:


===दोहरा घुमाव ===
===दोहरा घुमाव ===
चित्र 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> समान ऊंचाई के हैं.
चित्र 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: डबल घुमाव रोटेट_राइटलेफ्ट(्स,जेड)<br/>= रोटेट_राइट ज़ेड के चारों ओर और उसके पश्चात्<br/>रोटेट_लेफ्ट चारों ओर ्स]];दाएँ-बाएँ दोहरे घुमाव का कोड स्निपेट
[[File:AVL-double-rl_K.svg|thumb|right|264px|चित्र 3: डबल घुमाव दाएँ बाएँ (''X'',''Z'')<br/>= घुमाव _दाएँ ''Z''  के चारों ओर और उसके पश्चात् ''X''<br/>के चारों ओर बाएँ घुमाएँ]];दाएँ-बाएँ दोहरे घुमाव का कोड स्निपेट
{|
{|
|-
|-
| style="width:4em;" | Input: || X = root of subtree to be rotated
| style="width:4em;" | इनपुट: || X = अर्धट्री की जड़ को घुमाना है
|-
|-
| || Z = its right child, left-heavy
| || Z = इसका दाहिना बच्चा, बायाँ-भारी
|-
|-
| || &nbsp; &nbsp; with height == {{math|Height(LeftSubtree(}}X{{math|))+2}}
| || &nbsp; &nbsp; with height == {{math|Height(LeftSubtree(}}X{{math|))+2}}
|-
|-
|Result: || new root of rebalanced subtree
|परिणाम: || पुनर्संतुलित अर्धट्री की नई जड़
|}
|}


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)}} औसत पर आरबी पेड़ों को प्रत्येक ग्रंथि में बिट जानकारी (रंग) संग्रहीत करने की आवश्यकता होती है, जबकि एवीएल पेड़ अधिकतर संतुलन कारक के लिए दो बिट्स का उपयोग करते हैं, चूँकि, जब बच्चों पर संग्रहीत किया जाता है, तो "सहोदर से कम" अर्थ वाला बिट पर्याप्त होता है। दो डेटा संरचनाओं के मध्य बड़ा अंतर उनकी ऊंचाई सीमा है।
एवीएल ट्री और लाल-काले (आरबी) ट्री दोनों स्व-संतुलन वाले द्विआधारी परीक्षण ट्री हैं, और वे गणितीय रूप से संबंधित हैं। प्रत्येक एवीएल ट्री को लाल-काला रंग दिया जा सकता है,<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"/>
एवीएल ट्री आरबी ट्री की तुलना में अधिक कठोरता से संतुलित होते हैं, जिसमें एसिम्प्टोटिक विश्लेषण संबंध एवीएल/आरबी ≈0.720 अधिकतम ऊंचाई का होता है। सम्मिलन और विलोपन के लिए, बेन पफ़्फ़ 79 मापों में माध्य ≈0.947 और ज्यामितीय माध्य ≈0.910 के साथ 0.677 और 1.077 के मध्य एवीएल/आरबी का संबंध प्रदर्शित करता है।<ref name="Pfaff1"/>
==यह भी देखें==
==यह भी देखें==
*[[WAVL पेड़|डव्लूएवीएल पेड़]]
*[[WAVL पेड़|डव्लूएवीएल ट्री]]
*छींटे का पेड़
*छींटे का ट्री
*[[बलि का बकरा पेड़|स्केपगोट पेड़]]
*[[बलि का बकरा पेड़|स्केपगोट ट्री]]
*[[बी-वृक्ष]]
*[[बी-वृक्ष|बी-ट्री]]
*टी-वृक्ष
*टी-ट्री
*[[डेटा संरचनाओं की सूची]]
*[[डेटा संरचनाओं की सूची]]


Line 459: Line 459:
{{Data structures}}
{{Data structures}}


{{DEFAULTSORT:AVL Tree}}[[Category: 1962 कंप्यूटिंग में]] [[Category: स्यूडोकोड उदाहरण सहित लेख]] [[Category: बाइनरी पेड़]] [[Category: सोवियत आविष्कार]] [[Category: पेड़ खोजें]]
{{DEFAULTSORT:AVL Tree}}


 
[[Category:1962 कंप्यूटिंग में|AVL Tree]]
 
[[Category:CS1 maint]]
[[Category: Machine Translated Page]]
[[Category:CS1 русский-language sources (ru)]]
[[Category:Created On 07/07/2023]]
[[Category:Collapse templates|AVL Tree]]
[[Category:Commons category link is locally defined|AVL Tree]]
[[Category:Created On 07/07/2023|AVL Tree]]
[[Category:Lua-based templates|AVL Tree]]
[[Category:Machine Translated Page|AVL Tree]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|AVL Tree]]
[[Category:Pages with script errors|AVL Tree]]
[[Category:Sidebars with styles needing conversion|AVL Tree]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready|AVL Tree]]
[[Category:Templates generating microformats|AVL Tree]]
[[Category:Templates that add a tracking category|AVL Tree]]
[[Category:Templates that are not mobile friendly|AVL Tree]]
[[Category:Templates that generate short descriptions|AVL Tree]]
[[Category:Templates using TemplateData|AVL Tree]]
[[Category:Wikipedia metatemplates|AVL Tree]]
[[Category:पेड़ खोजें|AVL Tree]]
[[Category:बाइनरी पेड़|AVL Tree]]
[[Category:सोवियत आविष्कार|AVL Tree]]
[[Category:स्यूडोकोड उदाहरण सहित लेख|AVL Tree]]

Latest revision as of 18:56, 21 July 2023

AVL tree
TypeTree
Invented1962
Invented byGeorgy Adelson-Velsky and Evgenii Landis
Complexities in big O notation
Space complexity
Space
Time complexity
Function Amortized Worst Case
Search [1] [1]
Insert [1] [1]
Delete [1] [1]
एवीएल ट्री में अनेक तत्वों को सम्मिलित करने वाला एनीमेशन होता है। इसमें बाएँ, दाएँ, बाएँ-दाएँ और दाएँ-बाएँ घुमाव सम्मिलित हैं।
चित्र 1: संतुलन कारकों के साथ एवीएल ट्री (हरा)

कंप्यूटर विज्ञान में, एवीएल ट्री (आविष्कारकों एडेलसन-वेल्स्की और लैंडिस के नाम पर) स्व-संतुलन द्विआधारी परीक्षण ट्री है। एवीएल ट्री में, किसी भी नोड्स के दो बाल नोड्स अर्धट्री की ऊंचाई अधिकतम से भिन्न होती है; यदि किसी भी समय उनमें से अधिक का अंतर होता है, तो इस संपत्ति को पुनर्स्थापित करने के लिए पुनर्संतुलन किया जाता है। लुकअप, सम्मिलन और विलोपन सभी लेते हैं I O(log n) औसत और सबसे अमान्य दोनों विषयों में समय, जहां संचालन से पूर्व ट्री में नोड्स की संख्या होती है। सम्मिलन और विलोपन के लिए ट्री को एक या अधिक ट्री घुमावों द्वारा पुनर्संतुलित करने की आवश्यकता हो सकती है I

एवीएल ट्री का नाम इसके दो सोवियत संघ के आविष्कारकों, जॉर्जी एडेल्सन-वेल्स्की और एवगेनी लैंडिस के नाम पर रखा गया है, जिन्होंने इसे अपने 1962 के पेपर एन एल्गोरिदम फॉर द ऑर्गनाइजेशन ऑफ इंफॉर्मेशन में प्रकाशित किया था।[2] यह आविष्कार किया जाने वाला सबसे प्राचीन स्व-संतुलन द्विआधारी अनुसंधान ट्री डेटा संरचना है।[3] एवीएल ट्री की तुलना प्रायः लाल-काले ट्री से की जाती है, क्योंकि दोनों संचालन और टेक के समान समूह का समर्थन करते हैं I प्रारंभिक कार्यों के लिए समय लुकअप-गहन अनुप्रयोगों के लिए, एवीएल ट्री लाल-काले ट्री की तुलना में तीव्र होते हैं, क्योंकि वे अधिक कठोरता से संतुलित होते हैं।[4] लाल-काले ट्री के समान, एवीएल ट्री ऊंचाई-संतुलित होते हैं। सामान्यतः, दोनों न तो वजन-संतुलित ट्री हैं, न ही वजन-संतुलित -किसी के लिए संतुलित ;[5] अर्थात्, सहोदर नोड्स में वंशजों की संख्या बहुत भिन्न हो सकती है।

परिभाषा

संतुलन कारक

द्विआधारी ट्री में नोड्स के संतुलन कारक को ऊंचाई अंतर के रूप में परिभाषित किया गया है:-

[6]: 459 

इसके दो बाल अर्ध-ट्री का द्विआधारी ट्री को एवीएल ट्री के रूप में परिभाषित किया गया है, यदि इनवेरिएंट (कंप्यूटर विज्ञान)

[7]

ट्री में प्रत्येक नोड्स 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 से कम हो गई है। यह पूर्व से ही एवीएल आकार में है।

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " |
विलोपन संचालन के लिए उदाहरण कोड

for (X = parent(N); X != null; X = G) { // Loop (possibly up to the root) 

   G = parent(X); // Save parent of X around rotations
   // BF(X) has not yet been updated!
   if (N == left_child(X)) { // the left subtree decreases
       if (BF(X) > 0) { // X is right-heavy
           // ==> the temporary BF(X) == +2
           // ==> rebalancing is required.
           Z = right_child(X); // Sibling of N (higher by 2)
           b = BF(Z);
           if (b < 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) = +1; // N’s height decrease is absorbed at X.
               break; // Leave the loop
           }
           N = X;
           BF(N) = 0; // Height(N) decreases by 1
           continue;
       }
   } else { // (N == right_child(X)): The right subtree decreases
       if (BF(X) < 0) { // X is left-heavy
           // ==> the temporary BF(X) == -2
           // ==> rebalancing is required.
           Z = left_child(X); // Sibling of N (higher by 2)
           b = BF(Z);
           if (b > 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) = -1; // N’s height decrease is absorbed at X.
               break; // Leave the loop
           }
           N = X;
           BF(N) = 0; // Height(N) decreases by 1
           continue;
       }
   }
   // After a rotation adapt parent link:
   // N is the new root of the rotated subtree
   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

   if (b == 0)
       break; // Height does not change: Leave the loop

   // Height(N) decreases by 1 (== old Height(X)-1)

} // If (b != 0) the height of the total tree decreases by 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 ऊंचाई में वृद्धि से इसके पूर्वजों की ऊंचाई बढ़ सकती है, संभवतः उन नोड्स के एवीएल अपरिवर्तनीय को अमान्य कर दिया जा सकता है। इसे या तो दोगुने घुमाव के साथ ठीक किया जा सकता है, यदि मूल पर अमान्य है या यदि ट्री में उच्चतर अमान्य है तो एकल बाएं घुमाव के साथ, दोनों ही विषयों में किसी भी पूर्वज नोड्स के लिए ऊंचाई को बहाल किया जा सकता है। इसलिए जॉइन के लिए अधिकतम दो घुमावों की आवश्यकता होगी। इस फलन की लागत दो इनपुट ट्री के मध्य की ऊंचाई का अंतर है।

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " |
बांधना कलन विधि के लिए छदमकोड कार्यान्वयन

function JoinRightAVL(TL, k, TR) 

   (l, k', c) = expose(TL)
   if (Height(c) <= Height(TR)+1)
      T' = Node(c, k, TR)
      if (Height(T') <= Height(l)+1) then return Node(l, k', T')
      else return rotateLeft(Node(l, k', rotateRight(T')))
   else 
       T' = JoinRightAVL(c, k, TR)
       T = Node(l, k', T')
       if (Height(T') <= Height(l)+1) return T
       else return rotateLeft(T)

function JoinLeftAVL(TL, k, TR) 

 /* symmetric to JoinRightAVL */

function Join(TL, k, TR) 

   if (Height(TL)>Height(TR)+1) return JoinRightAVL(TL, k, TR)
   if (Height(TR)>Height(TL)+1) return JoinLeftAVL(TL, k, TR)
   return Node(TL, k, TR)vHere Height(v) is the height of a subtree (node) v. (l,k,r) = expose(v) extracts v's left child l, the key k of v's root, and the right child r. Node(l,k,r) means to create a node of left child l, key k, and right child r..

एवीएल ट्री को दो छोटे ट्री में विभाजित करना, जो कुंजी k से छोटे हों, और वे कुंजी k से बड़े हैं, पूर्व मार्ग से k एवीएल में हैं। इस प्रविष्टि के पश्चात्, सभी मान इससे कम होंगे k पथ के बायीं ओर मिलेगा, और सभी मान इससे बड़े होंगे k दाहिनी ओर मिलेगा I जॉइन प्रस्तावित करने से, बायीं ओर के सभी अर्धट्री को नीचे से ऊपर की ओर मध्यवर्ती नोड्स के रूप में पथ पर कुंजियों का अर्धयोग करके बाएँ ट्री बनाने के लिए विलय किया जाता है, और दायाँ भाग असममित होता है। विभाजित O(log n), ट्री की ऊंचाई का क्रम की लागत है I

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " |
विभाजित कलन विधि के लिए स्यूडोकोड कार्यान्वयन
function Split(T, k)
   if (T = nil) return (nil, false, nil)
   (L,m,R) = expose(T)
   if (k = m) return (L, true, R)
   if (k<m) 
      (L',b,R') = Split(L,k)
      return (L', b, Join(R', m, R))
   if (k>m) 
      (L',b,R') = Split(R, k)
return (Join(L, m, L'), b, R'))|}

दो एवीएल ट्री का मिलन t1 और t2 समूह का प्रतिनिधित्व करना A और B, एवीएल है, t जो A ∪ B प्रतिनिधित्व करता है I

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " |
यूनियन कलन विधि के लिए स्यूडोकोड कार्यान्वयन

function Union(t1, t2): 

   if t1 = nil:
       return t2
   if t2 = nil:
       return t1
   (t<, b, t>) = Split(t2, t1.root)
   return Join(Union(left(t1), t<), t1.root, Union(right(t1), t>))

यहां, विभाजित को दो पेड़ों को वापस करने के लिए माना जाता है: कुंजी को अपनी इनपुट कुंजी से कम रखता है, बड़ी कुंजी को रखता है। (एल्गोरिदम लगातार डेटा संरचना है | गैर-विनाशकारी, किन्तु इन-प्लेस विनाशकारी संस्करण भी उपस्थित है।)

प्रतिच्छेदन या अंतर के लिए कलन विधि समान है, किन्तु इसके लिए जॉइन 2 हेल्पर मार्गीन की आवश्यकता होती है, जो कि जॉइन के समान है किन्तु मध्य कुंजी के बिना है। यूनियन, प्रतिच्छेदन या अंतर के नए कार्यों के आधार पर, एवीएल ट्री में या तो एक कुंजी या अधिक कुंजियाँ डाली जा सकती हैं, या हटाई जा सकती हैं। चूंकि विभाजित कॉल जॉइन करता है किन्तु एवीएल ट्री के संतुलन मानदंडों से सीधे निपटता नहीं है, ऐसे कार्यान्वयन को सामान्यतः जॉइन-आधारित ट्री कलन विधि कहा जाता है I सम्मिलित-आधारित कार्यान्वयन मिलन, प्रतिच्छेद और भेद प्रत्येक की जटिलता है, और आकार के एवीएल ट्री के लिए अधिक महत्वपूर्ण बात यह है कि चूंकि संघ, प्रतिच्छेदन या अंतर के लिए पुनरावर्ती कॉल -दूसरे से स्वतंत्र हैं, इसलिए उन्हें समानांतर कलन विधि के विश्लेषण के साथ समानांतर प्रोग्रामिंग निष्पादित की जा सकती है। .[14] जब , जुड़ाव-आधारित कार्यान्वयन में एकल-तत्व सम्मिलन और विलोपन के समान कम्प्यूटेशनल डीएजी है।

पुनर्संतुलन

यदि संशोधित संचालन के अंतर्गत दो चाइल्ड अर्धट्री के मध्य ऊंचाई का अंतर परिवर्तित होता है, तो यह, जब तक कि यह <2 है, मूल पर संतुलन सूचना के अनुकूलन द्वारा परिलक्षित हो सकता है। सम्मिलित करने और विलोपन के संचालन के अंतर्गत 2 का (अस्थायी) ऊंचाई अंतर उत्पन्न हो सकता है, जिसका अर्थ है कि मूल अर्धट्री को पुनर्संतुलित करना होगा। दिए गए अर्धकरण तथाकथित ट्री घुमाव हैं, क्योंकि वे कुंजियों को केवल लंबवत रूप से घुमाते हैं, जिससे कुंजियों का (क्षैतिज) क्रम क्रम पूर्ण प्रकार से संरक्षित रहे (जो द्विआधारी-सर्च ट्री के लिए आवश्यक है)।[6]: 458–481  [12]: 33 

मान लीजिए कि X वह नोड्स है जिसका (अस्थायी) संतुलन कारक -2 या +2 है। इसके बाएँ या दाएँ अर्धट्री को संशोधित किया गया था। मान लीजिए कि Z बड़ा बच्चा है (आंकड़े 2 और 3 देखें)। ध्यान दें कि दोनों बच्चे गणितीय प्रेरण द्वारा एवीएल आकार में हैं।

सम्मिलन के विषय में यह सम्मिलन Z के बच्चों में से के साथ इस प्रकार से हुआ है कि Z की ऊंचाई बढ़ गई है। विलोपन के विषय में यह विलोपन सहोदर t1 को हुआ है, Z प्रकार से जिससे t1 की ऊंचाई पूर्व से ही कम होने के कारण कम हो गई है। (यह मात्र मामला है जहां Z का संतुलन कारक 0 भी हो सकता है।)

उल्लंघन के चार संभावित प्रकार हैं:

दाएँ दाएँ ⟹ Z दायां है इसके माता-पिता X और BF(Z) का बच्चा ≥ 0
बाएँ बाएँ ⟹ Z बायां है इसके माता-पिता X और BF(Z) का बच्चा ≤ 0
दाएँ बाएँ ⟹ Z दायां है इसके माता-पिता X और BF(Z) का बच्चा < 0
बाएँ दाएँ ⟹ Z बायां है इसके माता-पिता X और BF(Z) का बच्चा > 0

और पुनर्संतुलन भिन्न प्रकार से किया जाता है:

दाएँ दाएँ ⟹ X को a के साथ पुनः संतुलित किया गया है सरल घुमाव rotate_Left (रेखा - चित्र देखें 2)
बाएँ बाएँ ⟹ X को a के साथ पुनः संतुलित किया गया है सरल घुमाव rotate_Right (आकृति की दर्पण-छवि 2)
दाएँ बाएँ ⟹ X को a के साथ पुनः संतुलित किया गया है दोगुना घुमाव rotate_RightLeft (रेखा - चित्र देखें 3)
बाएँ दाएँ ⟹ X को a के साथ पुनः संतुलित किया गया है दोगुना घुमाव rotate_LeftRight (आकृति की दर्पण-छवि 3)

C B, जिससे स्थितियों को निरूपित किया जाता है, जहां C (= बच्चे की दिशा) और B (= संतुलन) समूह से आते हैं { Left, Right } साथ Right := −Left. विषय का शेष उल्लंघन C == B के साधारण घुमाव द्वारा की जाती है I rotate_(−C), जबकि विषय C != B की दोहरे घुमाव rotate_CB. द्वारा की जाती है I

घुमाव की लागत, चाहे वह साधारण हो या दोगुनी, स्थिर होती है।

सरल घुमाव

चित्र 2 दाएं-दाएं स्थिति प्रदर्शित करता है। इसके ऊपरी अर्ध भाग में, नोड्स X में +2. इसके अतिरिक्त, आंतरिक बच्चा t23 Z का (अर्थात, बायां बच्चा जब Z दायां बच्चा है, या दायां बच्चा जब Z बायां बच्चा है) अपने सहोदर t4 से अधिक नहीं है I यह अर्धट्री t4 की ऊंचाई बढ़ने से हो सकता है, या अर्धट्री t1 की ऊंचाई में कमी से पश्चात् वाले विषय में भी, पीली स्थिति जहां t233 इसकी ऊँचाई t4 के समान है I

बाएँ घुमाव का परिणाम चित्र के निचले अर्ध भाग में प्रदर्शित किया गया है। तीन लिंक (चित्र 2 में मोटे किनारे) और दो संतुलन कारकों को अद्यतन किया जाना है।

जैसा कि चित्र से ज्ञात होता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और घूमने के पश्चात् पुनः स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 स्तर पर थी, जहां यह पुनः है, जब t23 और t4 ही कद के थे. अन्यथा पत्ती की परत h+1 स्तर तक पहुंच जाती है, जिससे घूमने वाले ट्री की ऊंचाई कम हो जाती है।

चित्र 2: सरल घुमाव
rotate_Left(X,Z)
सरल बाएँ घुमाव का कोड स्निपेट
इनपुट: X = अर्धट्री की जड़ को बायीं ओर घुमाना है
Z = X, Z का दायाँ बच्चा दायाँ-भारी है
    with height == Height(LeftSubtree(X))+2
परिणाम: पुनर्संतुलित अर्धट्री की नई जड़ 
 node *rotate_Left(node *X, node *Z) {

    // Z is by 2 higher than its sibling
    t23 = left_child(Z); // Inner child of Z
    right_child(X) = t23;
    if (t23 != null)
        parent(t23) = X;
    left_child(Z) = X;
    parent(X) = Z;
    // 1st case, BF(Z) == 0,
    //   only happens with deletion, not insertion:
    if (BF(Z) == 0) { // t23 has been of same height as t4
        BF(X) = +1;   // t23 now higher
        BF(Z) = –1;   // t4 now lower than X
    } else
    { // 2nd case happens with insertion or deletion:
        BF(X) = 0;
        BF(Z) = 0;
    }
    return Z; // return new root of rotated subtree
}

दोहरा घुमाव

चित्र 3 दाएँ बाएँ स्थिति को प्रदर्शित करता है। इसके ऊपरी तीसरे भाग में, नोड्स X में +2. किन्तु चित्र 2 के विपरीत, Z का आंतरिक बच्चा Y उसके भाई t4 से ऊंचा है I यह स्वयं Y के सम्मिलन या इसके किसी अर्धट्री t2 की ऊँचाई में वृद्धि से हो सकता है, या t3 (इस परिणाम के साथ कि वे भिन्न-भिन्न ऊंचाई के हैं) या अर्धट्री t1 की ऊंचाई में कमी से पश्चात् वाले विषय में, यह भी हो सकता है कि t2 और t3 समान ऊंचाई के हैं.

पूर्व, दाएँ, घुमाव का परिणाम चित्र के मध्य तीसरे में दिखाया गया है। (संतुलन कारकों के संबंध में, यह घुमाव अन्य एवीएल एकल घुमावों के समान नहीं है, क्योंकि Y और t4 के मध्य ऊंचाई का अंतर है केवल 1 है।) अंतिम बाएँ घुमाव का परिणाम चित्र के निचले तीसरे भाग में दिखाया गया है। पांच लिंक (चित्रा 3 में मोटे किनारे) और तीन संतुलन कारकों को अद्यतन किया जाना है।

जैसा कि चित्र से ज्ञात होता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और दोहरे घुमाव के पश्चात् पुनः स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 के स्तर पर थी और दोहरे घुमाव के पश्चात् यह h+1 के स्तर पर थी, जिससे कि घुमाए गए ट्री की ऊंचाई कम हो गई।

चित्र 3: डबल घुमाव दाएँ बाएँ (X,Z)
= घुमाव _दाएँ Z के चारों ओर और उसके पश्चात् X
के चारों ओर बाएँ घुमाएँ
;दाएँ-बाएँ दोहरे घुमाव का कोड स्निपेट
इनपुट: X = अर्धट्री की जड़ को घुमाना है
Z = इसका दाहिना बच्चा, बायाँ-भारी
    with height == Height(LeftSubtree(X))+2
परिणाम: पुनर्संतुलित अर्धट्री की नई जड़ 
 node *rotate_RightLeft(node *X, node *Z) {

    // Z is by 2 higher than its sibling
    Y = left_child(Z); // Inner child of Z
    // Y is by 1 higher than sibling
    t3 = right_child(Y);
    left_child(Z) = t3;
    if (t3 != null)
        parent(t3) = Z;
    right_child(Y) = Z;
    parent(Z) = Y;
    t2 = left_child(Y);
    right_child(X) = t2;
    if (t2 != null)
        parent(t2) = X;
    left_child(Y) = X;
    parent(X) = Y;
    // 1st case, BF(Y) == 0,
    //   only happens with deletion, not insertion:
    if (BF(Y) == 0) {
        BF(X) = 0;
        BF(Z) = 0;
    } else
    // other cases happen with insertion or deletion:
        if (BF(Y) > 0) { // t3 was higher
            BF(X) = –1;  // t1 now higher
            BF(Z) = 0;
        } else {
            // t2 was higher
            BF(X) = 0;
            BF(Z) = +1;  // t4 now higher
        }
    BF(Y) = 0;
    return Y; // return new root of rotated subtree
}

अन्य संरचनाओं से तुलना

एवीएल ट्री और लाल-काले (आरबी) ट्री दोनों स्व-संतुलन वाले द्विआधारी परीक्षण ट्री हैं, और वे गणितीय रूप से संबंधित हैं। प्रत्येक एवीएल ट्री को लाल-काला रंग दिया जा सकता है,[15] किन्तु ऐसे आरबी ट्री हैं जो एवीएल संतुलित नहीं हैं। एवीएल (या आरबी) ट्री के अपरिवर्तनीयों को बनाए रखने के लिए, घुमाव महत्वपूर्ण भूमिका निभाते हैं। सबसे अमान्य स्थिति में, घुमाव के बिना भी, एवीएल या आरबी सम्मिलन या विलोपन की आवश्यकता होती है I O(log n) एवीएल संतुलन कारकों (या आरबी रंग) का निरीक्षण और/या अद्यतन आरबी सम्मिलन और विलोपन और एवीएल सम्मिलन के लिए शून्य से तीन टेल-रिकर्सिव घुमाव की आवश्यकता होती है और O(1) समय अमूर्त विश्लेषण में चलाया जाता है I[16]: pp.165, 158  [17] इस प्रकार औसतन समान रूप से स्थिर एवीएल विलोपन की आवश्यकता है I O(log n) सबसे अमान्य स्थिति में भी घुमाव होते हैं, O(1) औसत पर आरबी ट्री को प्रत्येक नोड्स में बिट जानकारी (रंग) संग्रहीत करने की आवश्यकता होती है, जबकि एवीएल ट्री अधिकतर संतुलन कारक के लिए दो बिट्स का अर्धयोग करते हैं, चूँकि, जब बच्चों पर संग्रहीत किया जाता है, तो "सहोदर से कम" अर्थ वाला बिट पर्याप्त होता है। दो डेटा संरचनाओं के मध्य बड़ा अंतर उनकी ऊंचाई सीमा है।

n ≥ 1 आकार के ट्री के लिए :-

  • एवीएल ट्री की ऊंचाई अधिकतम होती है
जहाँ सुनहरा अनुपात,   और .
  • आरबी ट्री की ऊंचाई अधिकतम होती है:-
     .[18]

एवीएल ट्री आरबी ट्री की तुलना में अधिक कठोरता से संतुलित होते हैं, जिसमें एसिम्प्टोटिक विश्लेषण संबंध एवीएल/आरबी ≈0.720 अधिकतम ऊंचाई का होता है। सम्मिलन और विलोपन के लिए, बेन पफ़्फ़ 79 मापों में माध्य ≈0.947 और ज्यामितीय माध्य ≈0.910 के साथ 0.677 और 1.077 के मध्य एवीएल/आरबी का संबंध प्रदर्शित करता है।[4]

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Eric Alexander. "AVL Trees". Archived from the original on July 31, 2019.{{cite web}}: CS1 maint: unfit URL (link)
  2. ↑ Adelson-Velsky, Georgy; Landis, Evgenii (1962). "सूचना के संगठन के लिए एक एल्गोरिदम". Proceedings of the USSR Academy of Sciences (in русский). 146: 263–266. English translation by Myron J. Ricci in Soviet Mathematics - Doklady, 3:1259–1263, 1962.
  3. ↑ Sedgewick, Robert (1983). "Balanced Trees". एल्गोरिदम. Addison-Wesley. p. 199. ISBN 0-201-06672-6.
  4. ↑ 4.0 4.1 Pfaff, Ben (June 2004). "सिस्टम सॉफ्टवेयर में बीएसटी का प्रदर्शन विश्लेषण" (PDF). Stanford University.
  5. ↑ AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?)
    Thereby: A Binary Tree is called -balanced, with , if for every node , the inequality
    holds and is minimal with this property. is the number of nodes below the tree with as root (including the root) and is the left child node of .
  6. ↑ 6.0 6.1 6.2 6.3 Knuth, Donald E. (2000). छाँटना और खोजना (2. ed., 6. printing, newly updated and rev. ed.). Boston [u.a.]: Addison-Wesley. ISBN 0-201-89685-0.
  7. ↑ Rajinikanth. "AVL Tree : Data Structures". btechsmartclass.com. Retrieved 2018-03-09.
  8. ↑ 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 "rank balanced" tree, as coined by Haeupler, Sen and Tarjan.
  9. ↑ Dixit, J. B. (2010). 'सी' भाषा के माध्यम से डेटा संरचनाओं में महारत हासिल करना. New Delhi, India: University Science Press, an imprint of Laxmi Publications Pvt. Ltd. ISBN 9789380386720. OCLC 939446542.
  10. ↑ 10.0 10.1 10.2 Brass, Peter (2008). उन्नत डेटा संरचनाएँ. Cambridge: Cambridge University Press. ISBN 9780511438202. OCLC 312435417.
  11. ↑ Hubbard, John Rast (2000). शाउम के सिद्धांत की रूपरेखा और जावा के साथ डेटा संरचनाओं की समस्याएं. New York: McGraw-Hill. ISBN 0071378707. OCLC 48139308.
  12. ↑ 12.0 12.1 12.2 Pfaff, Ben (2004). बाइनरी सर्च ट्री और बैलेंस्ड ट्री का परिचय. Free Software Foundation, Inc.
  13. ↑ Weiss, Mark Allen. (2006). C++ में डेटा संरचनाएं और एल्गोरिदम विश्लेषण (3rd ed.). Boston: Pearson Addison-Wesley. p. 145. ISBN 0-321-37531-9. OCLC 61278554.{{cite book}}: CS1 maint: date and year (link)
  14. ↑ 14.0 14.1 Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just join for parallel ordered sets", Symposium on Parallel Algorithms and Architectures, ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793.
  15. ↑ Paul E. Black (2015-04-13). "एवीएल पेड़". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 2016-07-02.
  16. ↑ Kurt Mehlhorn, 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.
  17. ↑ Dinesh P. Mehta, Sartaj Sahni (Ed.) Handbook of Data Structures and Applications 10.4.2
  18. ↑ Red–black tree#Proof of bounds


अग्रिम पठन


बाहरी संबंध

The Wikibook Algorithm Implementation has a page on the topic of: AVL tree
Wikimedia Commons has media related to AVL-trees.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एवीएल_ट्री&oldid=222430’