एवीएल ट्री: Difference between revisions
No edit summary |
No edit summary |
||
(14 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: संतुलन कारकों के साथ एवीएल | [[Image:AVL-tree-wBalance_K.svg|thumb|right|262px|चित्र 1: संतुलन कारकों के साथ एवीएल ट्री (हरा)]][[कंप्यूटर विज्ञान]] में, '''एवीएल ट्री''' (आविष्कारकों एडेलसन-वेल्स्की और लैंडिस के नाम पर) [[स्व-संतुलन द्विआधारी खोज वृक्ष|स्व-संतुलन द्विआधारी परीक्षण ट्री]] है। एवीएल ट्री में, किसी भी नोड्स के दो [[ बाल नोड्स |बाल नोड्स]] अर्धट्री की ऊंचाई अधिकतम से भिन्न होती है; यदि किसी भी समय उनमें से अधिक का अंतर होता है, तो इस संपत्ति को पुनर्स्थापित करने के लिए पुनर्संतुलन किया जाता है। लुकअप, सम्मिलन और विलोपन सभी लेते हैं I {{math|[[big O notation|O]](log ''n'')}} औसत और सबसे अमान्य दोनों विषयों में समय, जहां <math>n</math> संचालन से पूर्व ट्री में नोड्स की संख्या होती है। सम्मिलन और विलोपन के लिए ट्री को एक या अधिक ट्री घुमावों द्वारा पुनर्संतुलित करने की आवश्यकता हो सकती है I | ||
एवीएल | एवीएल ट्री का नाम इसके दो [[सोवियत संघ]] के आविष्कारकों, [[जॉर्जी एडेल्सन-वेल्स्की]] और [[एवगेनी लैंडिस]] के नाम पर रखा गया है, जिन्होंने इसे अपने 1962 के पेपर एन एल्गोरिदम फॉर द ऑर्गनाइजेशन ऑफ इंफॉर्मेशन में प्रकाशित किया था।<ref>{{cite journal|last1=Adelson-Velsky|first1=Georgy|last2=Landis|first2=Evgenii|year=1962|title=सूचना के संगठन के लिए एक एल्गोरिदम|journal=[[Proceedings of the USSR Academy of Sciences]]|volume=146|pages=263–266|language=ru}} [https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf English translation] by Myron J. Ricci in ''Soviet Mathematics - Doklady'', 3:1259–1263, 1962.</ref> यह आविष्कार किया जाने वाला सबसे प्राचीन स्व-संतुलन द्विआधारी अनुसंधान ट्री [[डेटा संरचना]] है।<ref>{{cite book |last=Sedgewick |first=Robert |title=एल्गोरिदम|publisher=Addison-Wesley |year=1983 |isbn=0-201-06672-6 |page=[https://archive.org/details/algorithms00sedg/page/199 199] |chapter=Balanced Trees |author-link1=Robert Sedgewick (computer scientist) |chapter-url=https://archive.org/details/algorithms00sedg/page/199 |chapter-url-access=registration}}</ref> एवीएल ट्री की तुलना प्रायः लाल-काले ट्री से की जाती है, क्योंकि दोनों संचालन और टेक के समान समूह का समर्थन करते हैं I <math>\text{O}(\log n)</math> प्रारंभिक कार्यों के लिए समय लुकअप-गहन अनुप्रयोगों के लिए, एवीएल ट्री लाल-काले ट्री की तुलना में तीव्र होते हैं, क्योंकि वे अधिक कठोरता से संतुलित होते हैं।<ref name="Pfaff1">{{cite web|last = Pfaff|first = Ben|title = सिस्टम सॉफ्टवेयर में बीएसटी का प्रदर्शन विश्लेषण| publisher = [[Stanford University]]|date=June 2004|url = http://www.stanford.edu/~blp/papers/libavl.pdf}}</ref> लाल-काले ट्री के समान, एवीएल ट्री ऊंचाई-संतुलित होते हैं। सामान्यतः, दोनों न तो [[वजन-संतुलित पेड़|वजन-संतुलित ट्री]] हैं, न ही वजन-संतुलित <math>\mu</math>-किसी के लिए संतुलित <math>\mu\leq\tfrac{1}{2}</math>;<ref>[https://cs.stackexchange.com/q/421 AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?)] <br />Thereby: A Binary Tree is called <math>\mu</math>-balanced, with <math>0 \le\mu\leq\tfrac12</math>, if for every node <math>N</math>, the inequality | ||
:<math>\tfrac12-\mu\le\tfrac{|N_l|}{|N|+1}\le \tfrac12+\mu</math> | :<math>\tfrac12-\mu\le\tfrac{|N_l|}{|N|+1}\le \tfrac12+\mu</math> | ||
Line 25: | Line 25: | ||
===संतुलन कारक=== | ===संतुलन कारक=== | ||
[[ द्विआधारी वृक्ष | द्विआधारी | [[ द्विआधारी वृक्ष | द्विआधारी ट्री]] में नोड्स के संतुलन कारक को ऊंचाई अंतर के रूप में परिभाषित किया गया है:- | ||
:<math> \text{BF}(X) := \text{Height}(\text{RightSubtree}(X)) - \text{Height}(\text{LeftSubtree}(X)) </math><ref name="Knuth">{{cite book|last=Knuth|first=Donald E.|author-link=Donald Knuth|title=छाँटना और खोजना|year=2000|publisher=Addison-Wesley|location=Boston [u.a.]|isbn=0-201-89685-0|edition=2. ed., 6. printing, newly updated and rev.}}</ref>{{rp|459}} | :<math> \text{BF}(X) := \text{Height}(\text{RightSubtree}(X)) - \text{Height}(\text{LeftSubtree}(X)) </math><ref name="Knuth">{{cite book|last=Knuth|first=Donald E.|author-link=Donald Knuth|title=छाँटना और खोजना|year=2000|publisher=Addison-Wesley|location=Boston [u.a.]|isbn=0-201-89685-0|edition=2. ed., 6. printing, newly updated and rev.}}</ref>{{rp|459}} | ||
इसके दो बाल | इसके दो बाल अर्ध-ट्री का द्विआधारी ट्री को एवीएल ट्री के रूप में परिभाषित किया गया है, यदि इनवेरिएंट (कंप्यूटर विज्ञान) | ||
:<math>\text{BF}(X) \in {\{-1,0,1\}}</math><ref>{{Cite web|url=http://www.btechsmartclass.com/data_structures/avl-trees.html|title=AVL Tree : Data Structures|last=Rajinikanth|website=btechsmartclass.com|access-date=2018-03-09}}</ref> | :<math>\text{BF}(X) \in {\{-1,0,1\}}</math><ref>{{Cite web|url=http://www.btechsmartclass.com/data_structures/avl-trees.html|title=AVL Tree : Data Structures|last=Rajinikanth|website=btechsmartclass.com|access-date=2018-03-09}}</ref> | ||
ट्री में प्रत्येक नोड्स X के लिए धारण करता है। | |||
नोड्स के साथ <math>\text{BF}(X)<0</math> वाम-भारी कहा जाता है, <math>\text{BF}(X)>0</math> के साथ दाएँ-भारी कहा जाता है, और <math>\text{BF}(X)=0</math> के साथ कभी-कभी इसे केवल संतुलित कहा जाता है। | नोड्स के साथ <math>\text{BF}(X)<0</math> वाम-भारी कहा जाता है, <math>\text{BF}(X)>0</math> के साथ दाएँ-भारी कहा जाता है, और <math>\text{BF}(X)=0</math> के साथ कभी-कभी इसे केवल संतुलित कहा जाता है। | ||
===गुण=== | ===गुण=== | ||
पूर्व संतुलन कारकों और ऊंचाई में परिवर्तन को समझकर संतुलन कारकों को अद्यतन रखा जा सकता है- पूर्ण ऊंचाई जानना आवश्यक नहीं है। एवीएल संतुलन जानकारी रखने के लिए, प्रति | पूर्व संतुलन कारकों और ऊंचाई में परिवर्तन को समझकर संतुलन कारकों को अद्यतन रखा जा सकता है- पूर्ण ऊंचाई जानना आवश्यक नहीं है। एवीएल संतुलन जानकारी रखने के लिए, प्रति नोड्स दो बिट पर्याप्त हैं।<ref>However, the balance information can be kept in the child nodes as one bit indicating whether the parent is higher by 1 or by 2; thereby higher by 2 cannot occur for both children. This way the AVL tree is a [[WAVL tree|"rank balanced" tree]], as coined by [[#Haeupler|Haeupler, Sen and Tarjan]].</ref> ऊंचाई <math>h</math> (स्तरों की अधिकतम संख्या के रूप में गिना जाता है) एवीएल ट्री के साथ <math>n</math> नोड्स अंतराल में निहित हैं:<ref name="Knuth"/>{{rp|460}} | ||
:<math>\log_2(n+1) \le h < \log_\varphi(n+2) + b</math> जहाँ <math>\varphi := \tfrac{1+\sqrt 5}2 \approx 1.618</math>[[सुनहरा अनुपात]] है और <math>b := \frac{\log_2 5}{2 \log_2 \varphi} - 2 \approx \; -0.3277 .</math> | :<math>\log_2(n+1) \le h < \log_\varphi(n+2) + b</math> जहाँ <math>\varphi := \tfrac{1+\sqrt 5}2 \approx 1.618</math>[[सुनहरा अनुपात]] है और <math>b := \frac{\log_2 5}{2 \log_2 \varphi} - 2 \approx \; -0.3277 .</math> | ||
इसका कारण ऊंचाई <math>h</math> का एवीएल | इसका कारण ऊंचाई <math>h</math> का एवीएल ट्री है, <math>F_{h}-1</math> कम से कम सम्मिलित है I नोड्स जहाँ <math>\{F_n\}_{n\in\N}</math> बीज मूल्यों के साथ [[फाइबोनैचि संख्या]] <math>F_1=F_2=1 .</math> है I | ||
==संचालन== | ==संचालन== | ||
एवीएल | एवीएल ट्री के रीड-ओनली संचालन में वही क्रियाएं सम्मिलित होती हैं, जो असंतुलित [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण ट्री]] पर की जाती हैं, किन्तु संशोधनों में अर्ध-ट्री की ऊंचाई संतुलन का निरीक्षण करना और पुनर्स्थापित करना होता है। | ||
===अन्वेषण=== | ===अन्वेषण=== | ||
एवीएल | एवीएल ट्री में विशिष्ट कुंजी के परीक्षण उसी प्रकार से किये जा सकते है जैसे किसी संतुलित या असंतुलित द्विआधारी परीक्षण ट्री अन्वेषण की होती है।<ref name="dixit-mastering-data-structures">{{Cite book|title='सी' भाषा के माध्यम से डेटा संरचनाओं में महारत हासिल करना|last=Dixit|first=J. B.|publisher=University Science Press, an imprint of Laxmi Publications Pvt. Ltd.|year=2010|isbn=9789380386720|location=New Delhi, India|oclc=939446542}}</ref>{{rp|ch. 8}} परीक्षण को प्रभावी प्रकार से काम करने के लिए इसे तुलना फलन को नियोजित करना होगा, जो कुंजियों के समूह पर [[कुल ऑर्डर]] (या कम से कम निर्बल ऑर्डर, कुल प्रीऑर्डर) स्थापित करता है।<ref name="brass-advanced-data-structures">{{Cite book|title=उन्नत डेटा संरचनाएँ|last=Brass|first=Peter|date=2008|publisher=Cambridge University Press|isbn=9780511438202|location=Cambridge|oclc=312435417}}</ref>{{rp|23}} सफल परीक्षण के लिए आवश्यक तुलनाओं की संख्या ऊंचाई {{math|''h''}} तक सीमित है, और असफल परीक्षण के लिए {{math|''h''}} बहुत निकट है, तो दोनों {{math|O(log ''n'')}} अंदर हैं I<ref name="hubbard-outline-theory-problems">{{Cite book|url=https://archive.org/details/schaumsoutlineof0000hubb|title=शाउम के सिद्धांत की रूपरेखा और जावा के साथ डेटा संरचनाओं की समस्याएं|last=Hubbard|first=John Rast|date=2000|publisher=McGraw-Hill|isbn=0071378707|location=New York|oclc=48139308|url-access=registration}}</ref>{{rp|216}} | ||
===ट्रैवर्सल=== | ===ट्रैवर्सल=== | ||
रीड-ओनली विकल्प के रूप में एवीएल | रीड-ओनली विकल्प के रूप में एवीएल ट्री का ट्रैवर्सल किसी अन्य द्विआधारी ट्री के जैसे ही कार्य करता है। सभी का अन्वेषण {{math|''n''}} ट्री के नोड्स प्रत्येक लिंक पर ठीक दो बार जाते हैं: नीचे की ओर जाने वाली यात्रा उस नोड्स द्वारा निहित अर्ध-ट्री में प्रवेश करने के लिए, दूसरी ऊपर की ओर जाने वाली यात्रा उस नोड्स के अर्ध-ट्री का पता लगाने के पश्चात् उसे त्यागने के लिए जाती है। | ||
एवीएल | एवीएल ट्री में नोड्स मिल जाने के पश्चात्, पूर्व नोड्स को [[अमूर्त जटिलता]] निरंतर समय में प्रवेश किया जा सकता है।<ref name="Pfaff"/>{{rp|58}} इन निकट के नोड्स की परीक्षण के कुछ उदाहरणों में ट्रैवर्सिंग की आवश्यकता होती है, {{math|''h'' ∝ log(''n'')}} लिंक (विशेष रूप से जब जड़ के बाएं अर्धट्री के सबसे दाहिने पत्ते से जड़ तक या जड़ से जड़ के दाएं अर्धट्री के सबसे बाएं पत्ते तक नेविगेट करते हैं; चित्र 1 के एवीएल ट्री में, नोड्स P से अगले-से-दाएँ तक नेविगेट करना नोड्स Q 3 चरण लेता है)। क्योंकि वहां {{math|''n''−1}} हैं, किसी भी ट्री में लिंक, परिशोधित लागत {{math|2×(''n''−1)/''n''}} है, या लगभग 2 है I | ||
===सन्निविष्ट करना=== | ===सन्निविष्ट करना=== | ||
एवीएल | एवीएल ट्री में नोड्स के प्रवेश होते समय, आप प्रारम्भ में [[बाइनरी सर्च ट्री|द्विआधारी परीक्षण ट्री]] में प्रवेश जैसी ही प्रक्रिया का पालन करते हैं। यदि ट्री रिक्त है, तो नोड्स को ट्री की जड़ के रूप में डाला जाता है। यदि ट्री रिक्त नहीं है, तो हम जड़ के नीचे जाते हैं, और नए नोड्स को सम्मिलित करने के लिए स्थान का परीक्षण करते हुए पुनरावर्ती रूप से ट्री के नीचे जाते हैं। यह ट्रैवर्सल तुलना फलन द्वारा निर्देशित होता है। इस विषय में, नोड्स सदैव ट्री में किसी बाहरी नोड्स के अशक्त संदर्भ (बाएं या दाएं) को प्रतिस्थापित करता है, जिससे, नोड्स को या तो बाहरी नोड्स का बायां-चाइल्ड या दायां-चाइल्ड बनाया जाता है। | ||
इस प्रविष्टि के पश्चात्, यदि कोई | इस प्रविष्टि के पश्चात्, यदि कोई ट्री असंतुलित हो जाता है, तो केवल नए डाले गए नोड्स के पूर्वज असंतुलित होते हैं। ऐसा इसलिए है क्योंकि केवल उन नोड्स के अर्ध-ट्री परिवर्तित किये गए हैं।<ref>{{Cite book|last=Weiss, Mark Allen.|title=C++ में डेटा संरचनाएं और एल्गोरिदम विश्लेषण|date=2006|publisher=Pearson Addison-Wesley|year=2006|isbn=0-321-37531-9|edition=3rd|location=Boston|pages=145|oclc=61278554}}</ref> इसलिए एवीएल ट्री के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक नोड्स के पूर्वजों की जांच करना आवश्यक है: इसे अनुसंधान कहा जाता है। यह प्रत्येक नोड्स के संतुलन कारक पर विचार करके प्राप्त किया जाता है।<ref name="Knuth"/>{{rp|458–481}} <ref name="Pfaff">{{cite book|last1=Pfaff|first1=Ben|title=बाइनरी सर्च ट्री और बैलेंस्ड ट्री का परिचय|date=2004|publisher=Free Software Foundation, Inc.}}</ref>{{rp|108}} | ||
चूंकि एकल सम्मिलन के साथ एवीएल | चूंकि एकल सम्मिलन के साथ एवीएल अर्धट्री की ऊंचाई से अधिक नहीं बढ़ सकती है, सम्मिलन के पश्चात् नोड्स का अस्थायी संतुलन कारक सीमा {{nowrap|[–2,+2].}} में होगा I परीक्षण किये गए प्रत्येक नोड्स के लिए, यदि अस्थायी संतुलन कारक -1 से +1 तक की सीमा में रहता है, तो केवल संतुलन कारक का अद्यतन और कोई नियमित आवर्तन आवश्यक नहीं है। चूंकि, यदि अस्थायी संतुलन कारक ±2 है, तो इस नोड्स पर निहित अर्धट्री एवीएल असंतुलित है, और नियमित आवर्तन की आवश्यकता है।<ref name="brass-advanced-data-structures" />{{rp|52}} जैसा कि नीचे दिए गए कोड से ज्ञात होता है, सम्मिलन के साथ, पर्याप्त नियमित आवर्तन ट्री को पुनः संतुलित करता है। | ||
चित्र 1 में, | चित्र 1 में, नोड्स X के चाइल्ड के रूप में नया नोड्स Z डालने से उस अर्धट्री Z की ऊंचाई 0 से 1 तक बढ़ जाती है। | ||
;सम्मिलन के लिए अनुसंधान लूप का [[लूप अपरिवर्तनीय]] | ;सम्मिलन के लिए अनुसंधान लूप का [[लूप अपरिवर्तनीय]] | ||
Z द्वारा | Z द्वारा मार्ग किए गए अर्धट्री की ऊंचाई 1 बढ़ गई है। यह पूर्व से ही एवीएल आकार में है। | ||
{{Collapse top| | {{Collapse top|सम्मिलित संचालन के लिए उदाहरण कोड}} | ||
for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root) | |||
// 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.{{Collapse bottom}} | ||
सभी नोड्स के संतुलन कारकों को अद्यतन करने के लिए, देखें कि सुधार की आवश्यकता वाले सभी नोड्स सम्मिलित पत्ते के पथ के साथ बच्चे से माता-पिता तक स्थित हैं। यदि अर्धरोक्त प्रक्रिया को पत्ती से प्रारम्भ करके इस पथ के नोड्स पर प्रस्तावित किया जाता है, तो ट्री के प्रत्येक नोड्स में -1, 0, या 1 का संतुलन कारक होगा। | |||
{{Collapse bottom}} | |||
सभी नोड्स के संतुलन कारकों को अद्यतन करने के लिए, | |||
यदि संतुलन कारक 0 हो जाता है तो | यदि संतुलन कारक 0 हो जाता है, तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस अर्धट्री की ऊंचाई अपरिवर्तित रहती है। | ||
यदि संतुलन कारक ±1 हो जाता है तो | यदि संतुलन कारक ±1 हो जाता है, तो अर्धट्री की ऊंचाई बढ़ जाती है और अनुसंधान प्रारम्भ रखने की आवश्यकता होती है। | ||
यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा ठीक किया जाना चाहिए जिसके पश्चात् | यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा ठीक किया जाना चाहिए, जिसके पश्चात् अर्धट्री की ऊंचाई पूर्व प्रकार ही हो जाती है (और इसकी जड़ में संतुलन कारक 0 होता है)। | ||
समय की आवश्यकता है {{math|O(log ''n'')}} लुकअप के लिए, साथ ही अधिकतम {{math|O(log ''n'')}} पुनः अनुरेखण स्तर ({{math|O(1)}} औसतन) | समय की आवश्यकता है, {{math|O(log ''n'')}} लुकअप के लिए, साथ ही अधिकतम {{math|O(log ''n'')}} पुनः अनुरेखण स्तर ({{math|O(1)}} औसतन) मार्ग पर पुनः जा रहा है, जिससे संचालन {{math|O(log ''n'')}} समय में पूर्ण किया जा सके।<ref name="brass-advanced-data-structures" />{{rp|53}} | ||
=== | ===विलोपन=== | ||
किसी | किसी नोड्स के विलोपन को प्रारंभिक चरण द्विआधारी परीक्षण ट्री विलोपन अनुभाग में वर्णित किया गया हैं। वहां, विषय नोड्स या प्रतिस्थापन नोड्स का प्रभावी विलोपन संबंधित चाइल्ड ट्री की ऊंचाई को 1 से 0 या 2 से 1 तक कम कर देता है, यदि उस नोड्स में बच्चा था। | ||
वहां, विषय | |||
इस | इस अर्धट्री से प्रारम्भ करते हुए, एवीएल ट्री के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक पूर्वज की जांच करना आवश्यक है। इसे पुनः अनुरेखण कहा जाता है। | ||
चूँकि | चूँकि विलोपन से एवीएल अर्धट्री की ऊँचाई से अधिक नहीं घट सकती, नोड्स का अस्थायी संतुलन कारक −2 से +2 तक की सीमा में होगा। यदि संतुलन कारक -1 से +1 की सीमा में रहता है, तो इसे एवीएल नियमों के अनुसार समायोजित किया जा सकता है। यदि यह ±2 हो जाता है, तो अर्धट्री असंतुलित है, और इसे घुमाने की आवश्यकता है। (सम्मिलन के विपरीत जहां घुमाव सदैव ट्री को संतुलित करता है, विलोपन के पश्चात्, BF(Z) ≠ 0 हो सकता है, (आंकड़े 2 और 3 देखें), जिससे उचित एकल या दोगुने घुमाव के पश्चात् पुनर्संतुलित अर्धट्री की ऊंचाई अर्थ से कम हो जाए कि ट्री को उच्च स्तर पर पुनः से संतुलित करना होगा।) घूर्णन के विभिन्न विषयों को खंड पुनर्संतुलन में वर्णित किया गया है। | ||
यदि संतुलन कारक -1 से +1 की सीमा में रहता है तो इसे एवीएल नियमों के अनुसार समायोजित किया जा सकता है। यदि यह ±2 हो जाता है तो | |||
;विलोपन के लिए रिट्रेसिंग लूप का अपरिवर्तनीय | ;विलोपन के लिए रिट्रेसिंग लूप का अपरिवर्तनीय | ||
N द्वारा | N द्वारा मार्ग किए गए अर्धट्री की ऊंचाई 1 से कम हो गई है। यह पूर्व से ही एवीएल आकार में है। | ||
{{Collapse top| | {{Collapse top|विलोपन संचालन के लिए उदाहरण कोड}} | ||
for (X = parent(N); X != null; X = G) { // Loop (possibly up to the root) | |||
for (X =parent(N); | 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 = | 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. | ||
{{Collapse bottom}} | {{Collapse bottom}} | ||
यदि संतुलन कारक ±1 हो जाता है (यह 0 रहा होगा) तो | यदि संतुलन कारक ±1 हो जाता है (यह 0 रहा होगा) तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस अर्धट्री की ऊंचाई अपरिवर्तित रहती है। | ||
यदि संतुलन कारक 0 हो जाता है (यह ±1 होना चाहिए) तो | यदि संतुलन कारक 0 हो जाता है (यह ±1 होना चाहिए) तो अर्धट्री की ऊंचाई कम हो जाती है और अनुसंधान प्रारम्भ रखने की आवश्यकता होती है। | ||
यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित | यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा सही करना होगा। यह सहोदर Z (चित्र 2 में उच्च संतान ट्री) के संतुलन कारक पर निर्भर करता है कि क्या अर्धट्री की ऊंचाई से कम हो जाती है- और अनुसंधान प्रारम्भ रखने की आवश्यकता है - या नहीं परिवर्तित होता है (यदि Z का संतुलन कारक 0 है) और पूर्ण ट्री एवीएल-आकार में है। | ||
समय की आवश्यकता है {{math|O(log ''n'')}} लुकअप के लिए, साथ ही अधिकतम {{math|O(log ''n'')}} पुनः अनुरेखण स्तर ({{math|O(1)}} औसतन) | समय की आवश्यकता है I {{math|O(log ''n'')}} लुकअप के लिए, साथ ही अधिकतम {{math|O(log ''n'')}} पुनः अनुरेखण स्तर ({{math|O(1)}} औसतन) मार्ग पर पुनःजा रहा है, जिससे संचालन {{math|O(log ''n'')}} समय में पूर्ण किया जा सके। | ||
===संचालन और थोक संचालन | ===संचालन और थोक संचालन संग्रह करें=== | ||
एकल तत्व इंसर्ट, डिलीट और लुकअप विकल्प के अतिरिक्त, एवीएल ट्री पर अनेक समूह विकल्प को परिभाषित किया गया है: [[ संघ (सेट सिद्धांत) |संघ (समूह सिद्धांत)]], [[ प्रतिच्छेदन (सेट सिद्धांत) |प्रतिच्छेदन (समूह सिद्धांत)]] और [[ अंतर सेट करें |अंतर समूह]] आदि I इन समूह फलन के आधार पर सम्मिलन या विलोपन पर तीव्र बल्क संचालन प्रस्तावित किया जा सकता है। ये समूह संचालन दो सहायक संचालन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, एवीएल ट्री का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है।<ref name="join-based">{{citation | |||
| last1 = Blelloch | first1 = Guy E. | | last1 = Blelloch | first1 = Guy E. | ||
| last2 = Ferizovic | first2 = Daniel | | last2 = Ferizovic | first2 = Daniel | ||
Line 229: | 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) | ||
(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){{mvar|v}}Here 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.{{mvar|}}{{mvar|}}{{mvar|}}{{mvar|}}{{mvar|}}{{mvar|}}{{mvar|}}{{mvar|}}. | |||
{{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) | |||
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')){{Collapse bottom}} | |||
{{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|यूनियन कलन विधि के लिए स्यूडोकोड कार्यान्वयन}} | ||
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>)) | |||
यहां, | यहां, विभाजित को दो पेड़ों को वापस करने के लिए माना जाता है: कुंजी को अपनी इनपुट कुंजी से कम रखता है, बड़ी कुंजी को रखता है। (एल्गोरिदम [[लगातार डेटा संरचना]] है | गैर-विनाशकारी, किन्तु इन-प्लेस विनाशकारी संस्करण भी उपस्थित है।) | ||
{{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 है, मूल पर संतुलन सूचना के अनुकूलन द्वारा परिलक्षित हो सकता है। सम्मिलित करने और विलोपन के संचालन के अंतर्गत 2 का (अस्थायी) ऊंचाई अंतर उत्पन्न हो सकता है, जिसका अर्थ है कि मूल अर्धट्री को पुनर्संतुलित करना होगा। दिए गए अर्धकरण तथाकथित ट्री घुमाव हैं, क्योंकि वे कुंजियों को केवल लंबवत रूप से घुमाते हैं, जिससे कुंजियों का (क्षैतिज) क्रम क्रम पूर्ण प्रकार से संरक्षित रहे (जो द्विआधारी-सर्च ट्री के लिए आवश्यक है)।<ref name="Knuth"/>{{rp|458–481}} <ref name="Pfaff"/>{{rp|33}} | ||
मान लीजिए कि X वह | मान लीजिए कि X वह नोड्स है जिसका (अस्थायी) संतुलन कारक -2 या +2 है। इसके बाएँ या दाएँ अर्धट्री को संशोधित किया गया था। मान लीजिए कि Z बड़ा बच्चा है (आंकड़े 2 और 3 देखें)। ध्यान दें कि दोनों बच्चे [[गणितीय प्रेरण]] द्वारा एवीएल आकार में हैं। | ||
सम्मिलन के विषय में यह सम्मिलन Z के बच्चों में से के साथ इस प्रकार से हुआ है कि Z की ऊंचाई बढ़ गई है। | सम्मिलन के विषय में यह सम्मिलन Z के बच्चों में से के साथ इस प्रकार से हुआ है कि Z की ऊंचाई बढ़ गई है। विलोपन के विषय में यह विलोपन सहोदर t<sub>1</sub> को हुआ है, Z प्रकार से जिससे t<sub>1</sub> की ऊंचाई पूर्व से ही कम होने के कारण कम हो गई है। (यह मात्र मामला है जहां Z का संतुलन कारक 0 भी हो सकता है।) | ||
विलोपन के विषय में यह विलोपन सहोदर | |||
उल्लंघन के चार संभावित प्रकार हैं: | उल्लंघन के चार संभावित प्रकार हैं: | ||
Line 298: | Line 283: | ||
{| | {| | ||
|- | |- | ||
| style="width:1em" | || | | style="width:1em" | || दाएँ दाएँ || ⟹ Z दायां है || इसके माता-पिता X और BF(Z) का बच्चा ≥ 0 | ||
|- | |- | ||
| || | | || बाएँ बाएँ || ⟹ Z बायां है || इसके माता-पिता X और BF(Z) का बच्चा ≤ 0 | ||
|- | |- | ||
| || | | || दाएँ बाएँ || ⟹ Z दायां है || इसके माता-पिता X और BF(Z) का बच्चा < 0 | ||
|- | |- | ||
| || | | || बाएँ दाएँ || ⟹ Z बायां है || इसके माता-पिता X और BF(Z) का बच्चा > 0 | ||
|} | |} | ||
और पुनर्संतुलन | और पुनर्संतुलन भिन्न प्रकार से किया जाता है: | ||
{| | {| | ||
|- | |- | ||
| style="width:1em" | || | | style="width:1em" | || दाएँ दाएँ || ⟹ X को a के साथ पुनः संतुलित किया गया है || सरल || घुमाव <code>rotate_Left</code> || (रेखा - चित्र देखें 2) | ||
|- | |- | ||
| || | | || बाएँ बाएँ || ⟹ X को a के साथ पुनः संतुलित किया गया है || सरल || घुमाव <code>rotate_Right</code> || (आकृति की दर्पण-छवि 2) | ||
|- | |- | ||
| || | | || दाएँ बाएँ || ⟹ X को a के साथ पुनः संतुलित किया गया है || दोगुना || घुमाव <code>rotate_RightLeft</code> || (रेखा - चित्र देखें 3) | ||
|- | |- | ||
| || | | || बाएँ दाएँ || ⟹ X को a के साथ पुनः संतुलित किया गया है || दोगुना || घुमाव <code>rotate_LeftRight</code> || (आकृति की दर्पण-छवि 3) | ||
|} | |} | ||
{{nowrap|''C B'',}} जिससे स्थितियों को निरूपित किया जाता है, जहां C (= बच्चे की दिशा) और B (= संतुलन) समूह से आते हैं {{nowrap|{ ''Left'', ''Right'' }}} साथ {{nowrap|1=''Right'' := −''Left''.}} विषय का शेष उल्लंघन {{nowrap|1=''C'' == ''B''}} के साधारण घुमाव द्वारा की जाती है I {{nowrap|<code>rotate_</code>(−''C''),}} जबकि विषय {{nowrap|1=''C'' != ''B''}} की दोहरे घुमाव {{nowrap|<code>rotate_</code>''CB''.}} द्वारा की जाती है I | |||
घुमाव की लागत, चाहे वह साधारण हो या दोगुनी, स्थिर होती है। | |||
===सरल घुमाव=== | ===सरल घुमाव=== | ||
चित्र 2 | चित्र 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 में मोटे किनारे) और दो संतुलन कारकों को अद्यतन किया जाना है। | ||
जैसा कि चित्र से | जैसा कि चित्र से ज्ञात होता है, सम्मिलन से पूर्व, पत्ती की परत स्तर 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;" | | | style="width:4em;" | इनपुट: || X = अर्धट्री की जड़ को बायीं ओर घुमाना है | ||
|- | |- | ||
| || Z = | | || Z = X, Z का दायाँ बच्चा दायाँ-भारी है | ||
|- | |- | ||
| || with height == {{math|Height(LeftSubtree(}}X{{math|))+2}} | | || with height == {{math|Height(LeftSubtree(}}X{{math|))+2}} | ||
|- | |- | ||
| | |परिणाम: || पुनर्संतुलित अर्धट्री की नई जड़ | ||
|} | |} | ||
=== | node *rotate_Left(node *X, node *Z) { | ||
चित्र 3 दाएँ बाएँ स्थिति को | |||
// 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 में <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 में मोटे किनारे) और तीन संतुलन कारकों को अद्यतन किया जाना है। | |||
जैसा कि चित्र से | जैसा कि चित्र से ज्ञात होता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और दोहरे घुमाव के पश्चात् पुनः स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 के स्तर पर थी और दोहरे घुमाव के पश्चात् यह h+1 के स्तर पर थी, जिससे कि घुमाए गए ट्री की ऊंचाई कम हो गई। | ||
[[File:AVL-double-rl_K.svg|thumb|right|264px|चित्र 3: डबल | [[File:AVL-double-rl_K.svg|thumb|right|264px|चित्र 3: डबल घुमाव दाएँ बाएँ (''X'',''Z'')<br/>= घुमाव _दाएँ ''Z'' के चारों ओर और उसके पश्चात् ''X''<br/>के चारों ओर बाएँ घुमाएँ]];दाएँ-बाएँ दोहरे घुमाव का कोड स्निपेट | ||
{| | {| | ||
|- | |- | ||
| style="width:4em;" | | | style="width:4em;" | इनपुट: || X = अर्धट्री की जड़ को घुमाना है | ||
|- | |- | ||
| || Z = | | || Z = इसका दाहिना बच्चा, बायाँ-भारी | ||
|- | |- | ||
| || with height == {{math|Height(LeftSubtree(}}X{{math|))+2}} | | || with height == {{math|Height(LeftSubtree(}}X{{math|))+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 | ||
} | |||
==अन्य संरचनाओं से तुलना== | ==अन्य संरचनाओं से तुलना== | ||
एवीएल | एवीएल ट्री और लाल-काले (आरबी) ट्री दोनों स्व-संतुलन वाले द्विआधारी परीक्षण ट्री हैं, और वे गणितीय रूप से संबंधित हैं। प्रत्येक एवीएल ट्री को लाल-काला रंग दिया जा सकता है,<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> | *:<math> | ||
\begin{array}{ll} | \begin{array}{ll} | ||
Line 428: | Line 413: | ||
\end{array} | \end{array} | ||
</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 435: | Line 420: | ||
\end{array} | \end{array} | ||
</math> .<ref>[[Red–black tree#Proof of bounds]]</ref> | </math> .<ref>[[Red–black tree#Proof of bounds]]</ref> | ||
एवीएल | एवीएल ट्री आरबी ट्री की तुलना में अधिक कठोरता से संतुलित होते हैं, जिसमें एसिम्प्टोटिक विश्लेषण संबंध एवीएल/आरबी ≈0.720 अधिकतम ऊंचाई का होता है। सम्मिलन और विलोपन के लिए, बेन पफ़्फ़ 79 मापों में माध्य ≈0.947 और ज्यामितीय माध्य ≈0.910 के साथ 0.677 और 1.077 के मध्य एवीएल/आरबी का संबंध प्रदर्शित करता है।<ref name="Pfaff1"/> | ||
==यह भी देखें== | ==यह भी देखें== | ||
*[[WAVL पेड़| | *[[WAVL पेड़|डव्लूएवीएल ट्री]] | ||
* | *छींटे का ट्री | ||
*[[बलि का बकरा पेड़]] | *[[बलि का बकरा पेड़|स्केपगोट ट्री]] | ||
*[[बी-वृक्ष]] | *[[बी-वृक्ष|बी-ट्री]] | ||
*टी- | *टी-ट्री | ||
*[[डेटा संरचनाओं की सूची]] | *[[डेटा संरचनाओं की सूची]] | ||
Line 474: | Line 459: | ||
{{Data structures}} | {{Data structures}} | ||
{{DEFAULTSORT:AVL Tree}} | {{DEFAULTSORT:AVL Tree}} | ||
[[Category: | [[Category:1962 कंप्यूटिंग में|AVL Tree]] | ||
[[Category:Created On 07/07/2023]] | [[Category:CS1 maint]] | ||
[[Category:CS1 русский-language sources (ru)]] | |||
[[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 | |||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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
|