एवीएल ट्री

AVL tree
Type	Tree
Invented	1962
Invented by	Georgy Adelson-Velsky and Evgenii Landis
Complexities in big O notation
Space complexity Space ${\text{Θ}}(n)$ Time complexity Function Amortized Worst Case Search ${\text{Θ}}(\log n)$ ${\text{O}}(\log n)$ Insert ${\text{Θ}}(\log n)$ ${\text{O}}(\log n)$ Delete ${\text{Θ}}(\log n)$ ${\text{O}}(\log n)$

एवीएल पेड़ में कई तत्वों को सम्मिलित करने वाला एनीमेशन। इसमें बाएँ, दाएँ, बाएँ-दाएँ और दाएँ-बाएँ घुमाव सम्मिलित हैं।

चित्र 1: संतुलन कारकों के साथ एवीएल वृक्ष (हरा)

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

एवीएल पेड़ का नाम इसके दो सोवियत संघ के आविष्कारकों, जॉर्जी एडेल्सन-वेल्स्की और एवगेनी लैंडिस के नाम पर रखा गया है, जिन्होंने इसे अपने 1962 के पेपर एन एल्गोरिदम फॉर द ऑर्गनाइजेशन ऑफ इंफॉर्मेशन में प्रकाशित किया था। यह आविष्कार किया जाने वाला सबसे प्राचीन स्व-संतुलन बाइनरी सर्च पेड़ डेटा संरचना है। एवीएल पेड़ों की तुलना प्रायः लाल-काले पेड़ों से की जाती है, क्योंकि दोनों ऑपरेशन और टेक के समान समूह का समर्थन करते हैं I ${\text{O}}(\log n)$ प्रारंभिक कार्यों के लिए समय लुकअप-गहन अनुप्रयोगों के लिए, एवीएल पेड़ लाल-काले पेड़ों की तुलना में तीव्र होते हैं, क्योंकि वे अधिक कठोरता से संतुलित होते हैं। लाल-काले पेड़ों के समान, एवीएल पेड़ ऊंचाई-संतुलित होते हैं। सामान्यतः, दोनों न तो वजन-संतुलित पेड़ हैं, न ही वजन-संतुलित $\mu$-किसी के लिए संतुलित $\mu \leq {\tfrac {1}{2}}$; अर्थात्, सहोदर नोड्स में वंशजों की संख्या बहुत भिन्न हो सकती है।

परिभाषा

संतुलन कारक

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

${\text{BF}}(X):={\text{Height}}({\text{RightSubtree}}(X))-{\text{Height}}({\text{LeftSubtree}}(X))$

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

${\text{BF}}(X)\in {\{-1,0,1\}}$

पेड़ में प्रत्येक नोड X के लिए धारण करता है।

नोड्स के साथ ${\text{BF}}(X)<0$ वाम-भारी कहा जाता है, ${\text{BF}}(X)>0$ के साथ दाएँ-भारी कहा जाता है, और ${\text{BF}}(X)=0$ के साथ कभी-कभी इसे केवल संतुलित कहा जाता है।

गुण

पूर्व संतुलन कारकों और ऊंचाई में परिवर्तन को समझकर संतुलन कारकों को अद्यतन रखा जा सकता है- पूर्ण ऊंचाई जानना आवश्यक नहीं है। एवीएल संतुलन जानकारी रखने के लिए, प्रति नोड दो बिट पर्याप्त हैं। ऊंचाई $h$ (स्तरों की अधिकतम संख्या के रूप में गिना जाता है) एवीएल वृक्ष के साथ $n$ नोड्स अंतराल में निहित हैं:

$\log _{2}(n+1)\leq h<\log _{\varphi }(n+2)+b$ जहाँ $\varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618$सुनहरा अनुपात है और $b:={\frac {\log _{2}5}{2\log _{2}\varphi }}-2\approx \;-0.3277.$

इसका कारण ऊंचाई $h$ का एवीएल वृक्ष है, $F_{h}-1$ कम से कम सम्मिलित है I नोड्स जहाँ $\{F_{n}\}_{n\in \mathbb {N} }$ बीज मूल्यों के साथ फाइबोनैचि संख्या $F_{1}=F_{2}=1.$ है I

संचालन

एवीएल पेड़ के रीड-ओनली संचालन में वही क्रियाएं सम्मिलित होती हैं, जो असंतुलित बाइनरी परीक्षण पेड़ पर की जाती हैं, किन्तु संशोधनों में उप-पेड़ों की ऊंचाई संतुलन का निरीक्षण करना और पुनर्स्थापित करना होता है।

अन्वेषण

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

ट्रैवर्सल

रीड-ओनली विकल्प के रूप में एवीएल पेड़ का ट्रैवर्सल किसी अन्य बाइनरी पेड़ के जैसे ही कार्य करता है। सभी का अन्वेषण n पेड़ के नोड्स प्रत्येक लिंक पर ठीक दो बार जाते हैं: नीचे की ओर जाने वाली यात्रा उस नोड द्वारा निहित उप-वृक्ष में प्रवेश करने के लिए, दूसरी ऊपर की ओर जाने वाली यात्रा उस नोड के उप-वृक्ष का पता लगाने के पश्चात् उसे त्यागने के लिए जाती है।

एवीएल पेड़ में नोड मिल जाने के पश्चात्, पूर्व नोड को अमूर्त जटिलता निरंतर समय में प्रवेश किया जा सकता है। इन निकट के नोड्स की परीक्षण के कुछ उदाहरणों में ट्रैवर्सिंग की आवश्यकता होती है, h ∝ log(n) लिंक (विशेष रूप से जब जड़ के बाएं उपवृक्ष के सबसे दाहिने पत्ते से जड़ तक या जड़ से जड़ के दाएं उपवृक्ष के सबसे बाएं पत्ते तक नेविगेट करते हैं; चित्र 1 के एवीएल पेड़ में, नोड P से अगले-से-दाएँ तक नेविगेट करना नोड Q 3 चरण लेता है)। क्योंकि वहां n−1 हैं, किसी भी पेड़ में लिंक, परिशोधित लागत 2×(n−1)/n है, या लगभग 2 है I

सन्निविष्ट करना

एवीएल पेड़ में नोड के प्रवेश होते समय, आप प्रारम्भ में बाइनरी परीक्षण पेड़ में प्रवेश जैसी ही प्रक्रिया का पालन करते हैं। यदि पेड़ रिक्त है, तो नोड को पेड़ की जड़ के रूप में डाला जाता है। यदि पेड़ रिक्त नहीं है, तो हम जड़ के नीचे जाते हैं, और नए नोड को सम्मिलित करने के लिए स्थान का परीक्षण करते हुए पुनरावर्ती रूप से पेड़ के नीचे जाते हैं। यह ट्रैवर्सल तुलना फलन द्वारा निर्देशित होता है। इस विषय में, नोड सदैव पेड़ में किसी बाहरी नोड के अशक्त संदर्भ (बाएं या दाएं) को प्रतिस्थापित करता है, जिससे, नोड को या तो बाहरी नोड का बायां-चाइल्ड या दायां-चाइल्ड बनाया जाता है।

इस प्रविष्टि के पश्चात्, यदि कोई पेड़ असंतुलित हो जाता है, तो केवल नए डाले गए नोड के पूर्वज असंतुलित होते हैं। ऐसा इसलिए है क्योंकि केवल उन नोड्स के उप-वृक्ष परिवर्तित किये गए हैं। इसलिए एवीएल पेड़ों के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक नोड के पूर्वजों की जांच करना आवश्यक है: इसे अनुसंधान कहा जाता है। यह प्रत्येक नोड के संतुलन कारक पर विचार करके प्राप्त किया जाता है।

चूंकि एकल सम्मिलन के साथ एवीएल अर्धपेड़ की ऊंचाई से अधिक नहीं बढ़ सकती है, सम्मिलन के पश्चात् नोड का अस्थायी संतुलन कारक सीमा [–2,+2]. में होगा I परीक्षण किये गए प्रत्येक नोड के लिए, यदि अस्थायी संतुलन कारक -1 से +1 तक की सीमा में रहता है, तो केवल संतुलन कारक का अद्यतन और कोई नियमित आवर्तन आवश्यक नहीं है। चूंकि, यदि अस्थायी संतुलन कारक ±2 है, तो इस नोड पर निहित उपवृक्ष एवीएल असंतुलित है, और नियमित आवर्तन की आवश्यकता है। जैसा कि नीचे दिए गए कोड से ज्ञात होता है, सम्मिलन के साथ, पर्याप्त नियमित आवर्तन पेड़ को पुनः संतुलित करता है।

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

सम्मिलन के लिए अनुसंधान लूप का लूप अपरिवर्तनीय

Z द्वारा रूट किए गए उपपेड़ की ऊंचाई 1 बढ़ गई है। यह पूर्व से ही एवीएल आकार में है।

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | Example code for an insert operation

<सिंटैक्सहाइलाइट लैंग = सी स्टाइल = ओवरफ़्लो: हिडन लाइन = 1 > के लिए (X = पैरेंट(Z); //बीएफ(एक्स) को अपडेट करना होगा: यदि (Z ==right_child(X)) {//सही उपवृक्ष बढ़ता है यदि (BF(X) > 0) {//X दाएं-भारी है // ==> अस्थायी बीएफ(एक्स) == +2 // ==> पुनर्संतुलन आवश्यक है। जी = अभिभावक(एक्स); // रोटेशन के आसपास एक्स के पैरेंट को सेव करें यदि (बीएफ(जेड) < 0) // दायां बायां मामला (चित्र 3 देखें) एन = रोटेट_राइटलेफ्ट(एक्स, जेड); // दोहरा घुमाव: दाएँ(Z) फिर बाएँ(X) अन्यथा // सही सही मामला (चित्र 2 देखें) एन = रोटेट_लेफ्ट(एक्स, जेड); // सिंगल रोटेशन लेफ्ट(X) // रोटेशन के बाद पैरेंट लिंक को अनुकूलित करें } अन्य { यदि (बीएफ(एक्स) < 0) { बीएफ(एक्स) = 0; // Z की ऊंचाई में वृद्धि X पर अवशोषित होती है। तोड़ना; // लूप छोड़ें } बीएफ(एक्स) = +1; जेड = एक्स; // ऊँचाई (Z) 1 से बढ़ जाती है जारी रखना; } } अन्यथा {// Z == बायां_चाइल्ड(एक्स): बायां उपवृक्ष बढ़ता है यदि (BF(X) < 0) {// X बाएँ-भारी है // ==> अस्थायी BF(X) == -2 // ==> पुनर्संतुलन आवश्यक है। जी = अभिभावक(एक्स); // रोटेशन के आसपास एक्स के पैरेंट को सेव करें अगर (बीएफ(जेड) > 0) // लेफ्ट राइट केस एन = रोटेट_लेफ्टराइट(एक्स, जेड); // दोहरा घुमाव: बाएँ(Z) फिर दाएँ(X) अन्यथा // बायाँ बायाँ मामला एन = रोटेट_राइट(एक्स, जेड); // सिंगल रोटेशन राइट (एक्स) // रोटेशन के बाद पैरेंट लिंक को अनुकूलित करें } अन्य { अगर (बीएफ(एक्स) > 0) { बीएफ(एक्स) = 0; // Z की ऊंचाई में वृद्धि X पर अवशोषित होती है। तोड़ना; // लूप छोड़ें } बीएफ(एक्स) = -1; जेड = एक्स; // ऊँचाई (Z) 1 से बढ़ जाती है जारी रखना; } } // एक रोटेशन के बाद पैरेंट लिंक को अनुकूलित करें: // एन घुमाए गए उपट्री की नई जड़ है // ऊंचाई नहीं बदलती: ऊंचाई (एन) == पुरानी ऊंचाई (एक्स) माता-पिता(एन) = जी; यदि (जी != शून्य) { अगर (एक्स == लेफ्ट_चाइल्ड(जी)) बायाँ_बच्चा(जी) = एन; अन्य दाएँ_बच्चे(जी) = एन; } अन्य पेड़->जड़ = एन; // N कुल वृक्ष की नई जड़ है तोड़ना; // कोई गिरावट नहीं है, केवल टूटना है; या जारी रखें; } // जब तक लूप को ब्रेक के माध्यम से नहीं छोड़ा जाता, कुल पेड़ की ऊंचाई 1 बढ़ जाती है। </सिंटैक्सहाइलाइट>

सभी नोड्स के संतुलन कारकों को अद्यतन करने के लिए, पहले देखें कि सुधार की आवश्यकता वाले सभी नोड्स सम्मिलित पत्ते के पथ के साथ बच्चे से माता-पिता तक स्थित हैं। यदि उपरोक्त प्रक्रिया को पत्ती से शुरू करके इस पथ के नोड्स पर लागू किया जाता है, तो पेड़ के प्रत्येक नोड में फिर से -1, 0, या 1 का संतुलन कारक होगा।

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

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

यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा ठीक किया जाना चाहिए जिसके पश्चात् उपवृक्ष की ऊंचाई पहले की प्रकार ही हो जाती है (और इसकी जड़ में संतुलन कारक 0 होता है)।

समय की आवश्यकता है O(log n) लुकअप के लिए, साथ ही अधिकतम O(log n) पुनः अनुरेखण स्तर (O(1) औसतन) रूट पर वापस जा रहा है, ताकि ऑपरेशन पूरा किया जा सके O(log n) समय।

हटाएं

किसी नोड को हटाने के प्रारंभिक चरण बाइनरी सर्च पेड़#डिलीशन अनुभाग में वर्णित हैं। वहां, विषय नोड या प्रतिस्थापन नोड का प्रभावी विलोपन संबंधित चाइल्ड पेड़ की ऊंचाई को 1 से 0 या 2 से 1 तक कम कर देता है, यदि उस नोड में बच्चा था।

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

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

विलोपन के लिए रिट्रेसिंग लूप का अपरिवर्तनीय

N द्वारा रूट किए गए उपवृक्ष की ऊंचाई 1 से कम हो गई है। यह पहले से ही एवीएल आकार में है।

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | Example code for a delete operation

<सिंटैक्सहाइलाइट लैंग = सी स्टाइल = ओवरफ़्लो: हिडन लाइन = 1 > for (X =parent(N); जी = अभिभावक(एक्स); // रोटेशन के आसपास एक्स के पैरेंट को सेव करें //बीएफ(एक्स) अभी तक अपडेट नहीं किया गया है! यदि (एन == लेफ्ट_चाइल्ड(एक्स)) {// लेफ्ट सबट्री घट जाती है यदि (BF(X) > 0) {//X दाएं-भारी है // ==> अस्थायी बीएफ(एक्स) == +2 // ==> पुनर्संतुलन आवश्यक है। जेड = राइट_चाइल्ड(एक्स); // N का सहोदर (2 से अधिक) बी = बीएफ(जेड); यदि (बी < 0) // दायां बायां मामला (चित्र 3 देखें) एन = रोटेट_राइटलेफ्ट(एक्स, जेड); // दोहरा घुमाव: दाएँ(Z) फिर बाएँ(X) अन्यथा // सही सही मामला (चित्र 2 देखें) एन = रोटेट_लेफ्ट(एक्स, जेड); // सिंगल रोटेशन लेफ्ट(X) // रोटेशन के बाद पैरेंट लिंक को अनुकूलित करें } अन्य { अगर (बीएफ(एक्स) == 0) { बीएफ(एक्स) = +1; // N की ऊंचाई में कमी X पर अवशोषित हो जाती है। तोड़ना; // लूप छोड़ें } एन = एक्स; बीएफ(एन) = 0; // ऊंचाई (एन) 1 से घट जाती है जारी रखना; } } अन्यथा {// (एन == दायां_चाइल्ड(एक्स)): दायां उपवृक्ष घटता है यदि (BF(X) < 0) {// X बाएँ-भारी है // ==> अस्थायी BF(X) == -2 // ==> पुनर्संतुलन आवश्यक है। Z = बायाँ_बच्चा(X); // N का सहोदर (2 से अधिक) बी = बीएफ(जेड); यदि (बी > 0) // बायां दायां मामला एन = रोटेट_लेफ्टराइट(एक्स, जेड); // दोहरा घुमाव: बाएँ(Z) फिर दाएँ(X) अन्यथा // बायाँ बायाँ मामला एन = रोटेट_राइट(एक्स, जेड); // सिंगल रोटेशन राइट (एक्स) // रोटेशन के बाद पैरेंट लिंक को अनुकूलित करें } अन्य { अगर (बीएफ(एक्स) == 0) { बीएफ(एक्स) = -1; // N की ऊंचाई में कमी X पर अवशोषित हो जाती है। तोड़ना; // लूप छोड़ें } एन = एक्स; बीएफ(एन) = 0; // ऊंचाई (एन) 1 से घट जाती है जारी रखना; } } // एक रोटेशन के बाद पैरेंट लिंक को अनुकूलित करें: // एन घुमाए गए उपट्री की नई जड़ है माता-पिता(एन) = जी; यदि (जी != शून्य) { अगर (एक्स == लेफ्ट_चाइल्ड(जी)) बायाँ_बच्चा(जी) = एन; अन्य दाएँ_बच्चे(जी) = एन; } अन्य पेड़->जड़ = एन; // N कुल वृक्ष की नई जड़ है यदि (बी == 0) तोड़ना; // ऊंचाई नहीं बदलती: लूप छोड़ें // ऊंचाई(एन) 1 से घट जाती है (== पुरानी ऊंचाई(एक्स)-1) } // यदि (बी != 0) तो कुल पेड़ की ऊंचाई 1 घट जाती है। </सिंटैक्सहाइलाइट>

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

यदि संतुलन कारक 0 हो जाता है (यह ±1 होना चाहिए) तो उपवृक्ष की ऊंचाई कम हो जाती है और रिट्रेसिंग जारी रखने की आवश्यकता होती है।

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

समय की आवश्यकता है O(log n) लुकअप के लिए, साथ ही अधिकतम O(log n) पुनः अनुरेखण स्तर (O(1) औसतन) रूट पर वापस जा रहा है, ताकि ऑपरेशन पूरा किया जा सके O(log n) समय।

संचालन और थोक संचालन समूह करें

सिंगल-एलिमेंट इंसर्ट, डिलीट और लुकअप ऑपरेशंस के अलावा, एवीएल पेड़ पर कई समूह ऑपरेशंस को परिभाषित किया गया है: संघ (समूह सिद्धांत) , प्रतिच्छेदन (समूह सिद्धांत) और अंतर समूह करें । फिर इन समूह फ़ंक्शंस के आधार पर सम्मिलन या विलोपन पर तीव्र बल्क ऑपरेशन लागू किया जा सकता है। ये समूह ऑपरेशन दो सहायक ऑपरेशन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, एवीएल पेड़ों का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है। फलन दो एवीएल पेड़ों पर जुड़ें t₁ और t₂ और कुंजी k सभी तत्वों वाला पेड़ लौटाएगा t₁, t₂ साथ ही k. उसकी आवश्यकता हैं k सभी कुंजियों से बड़ा होना t₁ और सभी कुंजियों से छोटा t₂. यदि दो पेड़ों की ऊंचाई अधिकतम से भिन्न है, तो Join बस बाएं उपवृक्ष के साथ नया नोड बनाएं t₁, जड़ k और दायां उपवृक्ष t₂. अन्यथा, मान लीजिये t₁ ये उससे ऊंचा है t₂ से अधिक के लिए (दूसरा मामला सममित है)। जॉइन की दाहिनी रीढ़ का अनुसरण करता है t₁ नोड तक c जिसके साथ संतुलित है t₂. इस बिंदु पर बाएँ बच्चे के साथ नया नोड c, जड़ k और सही बच्चा t₂ c को प्रतिस्थापित करने के लिए बनाया गया है। नया नोड एवीएल अपरिवर्तनीय को संतुष्ट करता है, और इसकी ऊंचाई इससे अधिक है c. ऊंचाई में वृद्धि से इसके पूर्वजों की ऊंचाई बढ़ सकती है, संभवतः उन नोड्स के एवीएल अपरिवर्तनीय को अमान्य कर दिया जा सकता है। इसे या तो डबल रोटेशन के साथ ठीक किया जा सकता है यदि मूल पर अमान्य है या यदि पेड़ में उच्चतर अमान्य है तो ल बाएं रोटेशन के साथ, दोनों ही विषयों में किसी भी पूर्वज नोड के लिए ऊंचाई को बहाल किया जा सकता है। इसलिए जॉइन के लिए अधिकतम दो घुमावों की आवश्यकता होगी। इस फलन की लागत दो इनपुट पेड़ों के बीच की ऊंचाई का अंतर है।

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | Pseudocode implementation for the Join algorithm

फ़ंक्शन JoinRightAVL(TL, के, टीR) (एल, के', सी) = एक्सपोज़(टीL) यदि (ऊंचाई(सी) <= ऊंचाई(टीR)+1) टी' = नोड(सी, के, टीR) यदि (ऊंचाई(टी') <= ऊंचाई(एल)+1) तो नोड(एल, के', टी') लौटाएं अन्यथा रोटेटलेफ्ट लौटाएं(नोड(एल, के', रोटेटराइट(टी'))) अन्य टी' = जॉइनराइटएवीएल(सी, के, टीR) टी<नोविकी></नोविकी> = नोड(एल, के', टी') ' अगर ' ( ​​ऊंचाई ( टी ' ) <= ऊंचाई ( एल ) + 1 ) ' वापसी ' टी < अभी > </ अभी > ' अन्यथा ' वापसी ' रोटेट लेफ्ट ( T < nowwiki > </ nowwiki > ) 'फ़ंक्शन' JoinLeftAVL (टीL, के, टीR) /* JoinRightAVL के सममित */ फ़ंक्शन जॉइन(टीL, के, टीR) यदि (ऊंचाई(टी)L)>ऊंचाई(टीR)+1) रिटर्न JoinRightAVL(TL, के, टीR) यदि (ऊंचाई(टी)R)>ऊंचाई(टीL)+1) रिटर्न JoinLeftAVL(TL, के, टीR) वापसी नोड(टीL, के, टीR) यहाँ ऊँचाई(v) एक उपवृक्ष (नोड) की ऊँचाई है v. (एल, के, आर) = एक्सपोज़ (वी) अर्क v का बायां बच्चा l, कुंजी k का vकी जड़, और दाहिना बच्चा r. नोड(एल,के,आर) का अर्थ है बाएं बच्चे का नोड बनाना l, चाबी k, और सही बच्चा r.

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

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | Pseudocode implementation for the Split algorithm
फ़ंक्शन स्प्लिट (टी, के) यदि (T = शून्य) वापसी (शून्य, गलत, शून्य) (एल,एम,आर) = एक्सपोज़(टी) यदि (k = m) वापसी (L, सत्य, R) यदि (k<m) (एल',बी,आर') = स्प्लिट(एल,के) वापसी (एल', बी, जुड़ें (आर', एम, आर)) यदि (k>m) (एल',बी,आर') = स्प्लिट(आर, के) वापसी (जुड़ें (एल, एम, एल'), बी, आर'))

दो एवीएल पेड़ों का मिलन t₁ और t₂ समूह का प्रतिनिधित्व करना A और B, एवीएल है t जो प्रतिनिधित्व करता है A ∪ B.

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | Pseudocode implementation for the Union algorithm

फंक्शन यूनियन(टी1, टी2): यदि टी1 = शून्य: वापसी टी2 यदि टी2 = शून्य: वापसी टी1 (टी<, बी, टी>) = स्प्लिट(t2, टी1।जड़) वापसी शामिल हों (संघ (बाएं (टी)।1), टी<), टी1.रूट, यूनियन(दाएं(t1), टी>)) यहां, स्प्लिट को दो पेड़ों को वापस करने के लिए माना जाता है: एक कुंजी को अपनी इनपुट कुंजी से कम रखता है, एक बड़ी कुंजी को रखता है। (एल्गोरिदम लगातार डेटा संरचना है | गैर-विनाशकारी, लेकिन एक इन-प्लेस विनाशकारी संस्करण भी मौजूद है।)

प्रतिच्छेदन या अंतर के लिए एल्गोरिथ्म समान है, किन्तु इसके लिए Join2 हेल्पर रूटीन की आवश्यकता होती है जो कि Join के समान है किन्तु मध्य कुंजी के बिना। यूनियन, इंटरसेक्शन या अंतर के नए कार्यों के आधार पर, एवीएल पेड़ में या तो कुंजी या ाधिक कुंजियाँ डाली जा सकती हैं या हटाई जा सकती हैं। चूंकि स्प्लिट कॉल जॉइन करता है किन्तु एवीएल पेड़ों के संतुलन मानदंडों से सीधे निपटता नहीं है, ऐसे कार्यान्वयन को आमतौर पर जॉइन-आधारित पेड़ एल्गोरिदम कहा जाता है | सम्मिलित-आधारित कार्यान्वयन।

मिलन, प्रतिच्छेद और भेद प्रत्येक की जटिलता है ${\text{O}}\left(m\log \left({n \over m}+1\right)\right)$ आकार के एवीएल पेड़ों के लिए $m$ और $n\;(\geq m)$. अधिक महत्वपूर्ण बात यह है कि चूंकि संघ, प्रतिच्छेदन या अंतर के लिए पुनरावर्ती कॉल -दूसरे से स्वतंत्र हैं, इसलिए उन्हें समानांतर एल्गोरिदम के विश्लेषण के साथ समानांतर प्रोग्रामिंग निष्पादित की जा सकती है। ${\text{O}}(\log m\log n)$.कब $m=1$, जुड़ाव-आधारित कार्यान्वयन में ल-तत्व सम्मिलन और विलोपन के समान कम्प्यूटेशनल डीएजी है।

पुनर्संतुलन

यदि संशोधित ऑपरेशन के दौरान दो चाइल्ड उपवृक्षों के बीच ऊंचाई का अंतर बदलता है, तो यह, जब तक कि यह <2 है, मूल पर संतुलन जानकारी के अनुकूलन द्वारा परिलक्षित हो सकता है। सम्मिलित करने और हटाने के संचालन के दौरान 2 का (अस्थायी) ऊंचाई अंतर उत्पन्न हो सकता है, जिसका अर्थ है कि मूल उपवृक्ष को पुनर्संतुलित करना होगा। दिए गए मरम्मत उपकरण तथाकथित पेड़ रोटेशन हैं, क्योंकि वे कुंजियों को केवल लंबवत रूप से घुमाते हैं, ताकि कुंजियों का (क्षैतिज) क्रम क्रम पूरी प्रकार से संरक्षित रहे (जो बाइनरी-सर्च पेड़ के लिए आवश्यक है)।

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

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

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

	Right Right	⟹ Z is a right	child of its parent X and BF(Z) ≥ 0
	Left Left	⟹ Z is a left	child of its parent X and BF(Z) ≤ 0
	Right Left	⟹ Z is a right	child of its parent X and BF(Z) < 0
	Left Right	⟹ Z is a left	child of its parent X and BF(Z) > 0

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

	Right Right	⟹ X is rebalanced with a	simple	rotation rotate_Left	(see figure 2)
	Left Left	⟹ X is rebalanced with a	simple	rotation rotate_Right	(mirror-image of figure 2)
	Right Left	⟹ X is rebalanced with a	double	rotation rotate_RightLeft	(see figure 3)
	Left Right	⟹ X is rebalanced with a	double	rotation rotate_LeftRight	(mirror-image of figure 3)

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

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

सरल घुमाव

चित्र 2 सही सही स्थिति दिखाता है। इसके ऊपरी आधे भाग में, नोड X में +2. इसके अलावा, आंतरिक बच्चा टी₂₃ Z का (अर्थात, बायां बच्चा जब Z दायां बच्चा है, या दायां बच्चा जब Z बायां बच्चा है) अपने सहोदर से अधिक नहीं है₄. यह सबपेड़ टी की ऊंचाई बढ़ने से हो सकता है₄ या उपवृक्ष टी की ऊंचाई में कमी से₁. पश्चात् वाले विषय में भी, पीली स्थिति जहां टी₂₃ इसकी ऊँचाई t के समान है₄ तब हो सकती है।

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

जैसा कि चित्र से पता चलता है, सम्मिलन से पहले, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और घूमने के पश्चात् फिर से स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 स्तर पर थी, जहां यह फिर से है, जब t₂₃ और टी₄ ही कद के थे. अन्यथा पत्ती की परत h+1 स्तर तक पहुंच जाती है, जिससे घूमने वाले पेड़ की ऊंचाई कम हो जाती है।

चित्र 2: सरल घुमाव
rotate_Left(X,Z)

;सरल बाएँ घुमाव का कोड स्निपेट

Input:	X = root of subtree to be rotated left
	Z = right child of X, Z is right-heavy
	with height == Height(LeftSubtree(X))+2
Result:	new root of rebalanced subtree

<सिंटैक्सहाइलाइट लैंग = सी स्टाइल = ओवरफ़्लो: हिडन लाइन = 1 > नोड *rotate_Left(नोड *X, नोड *Z) {

  // Z अपने सहोदर से 2 अधिक है
  t23 = बायाँ_बच्चा(Z); // Z का आंतरिक बच्चा
  दाएँ_बच्चे(्स) = t23;
  यदि (t23t!= शून्य)
    पैरेंट(t23) = ्स;
  लेफ्ट_चाइल्ड(जेड) = ्स;
  माता-पिता(्स) = जेड;
  // पहला मामला, बीएफ(जेड) == 0,
  // केवल हटाने से होता है, डालने से नहीं:
  यदि (BF(Z) == 0) {// t23 की ऊंचाई t4 के समान है
    बीएफ(्स) = +1; // t23 अब उच्चतर
    बीएफ(जेड) = -1; // t4 अब X से कम है
  } अन्य
  {//दूसरा मामला सम्मिलन या विलोपन के साथ होता है:
    बीएफ(्स) = 0;
    बीएफ(जेड) = 0;
  }
  वापसी Z; // घुमाए गए सबपेड़ की नई जड़ लौटाएं

} </सिंटैक्सहाइलाइट>

डबल रोटेशन

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

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

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

चित्र 3: डबल रोटेशन रोटेट_राइटलेफ्ट(्स,जेड)
= रोटेट_राइट ज़ेड के चारों ओर और उसके पश्चात्
रोटेट_लेफ्ट चारों ओर ्स

;दाएँ-बाएँ दोहरे घुमाव का कोड स्निपेट

Input:	X = root of subtree to be rotated
	Z = its right child, left-heavy
	with height == Height(LeftSubtree(X))+2
Result:	new root of rebalanced subtree

<सिंटैक्सहाइलाइट लैंग = सी स्टाइल = ओवरफ़्लो: हिडन लाइन = 1 > नोड *rotate_RightLeft(नोड *X, नोड *Z) {

  // Z अपने सहोदर से 2 अधिक है
  वाई = बायाँ_बच्चा(जेड); // Z का आंतरिक बच्चा
  //Y, सहोदर से 1 अधिक है
  t3 = राइट_चाइल्ड(Y);
  बायाँ_बच्चा(Z) = t3;
  यदि (t3�!= शून्य)
    पेरेंट(t3) = Z;
  दाएँ_बच्चे(Y) = Z;
  माता-पिता(जेड) = वाई;
  t2 = बायाँ_बच्चा(Y);
  दाएँ_बच्चे(्स) = t2;
  यदि (t2�!= शून्य)
    पेरेंट(t2) = ्स;
  लेफ्ट_चाइल्ड(वाई) = ्स;
  माता-पिता(्स) = वाई;
  // पहला मामला, बीएफ(वाई) == 0,
  // केवल हटाने से होता है, डालने से नहीं:
  अगर (बीएफ(वाई) == 0) {
    बीएफ(्स) = 0;
    बीएफ(जेड) = 0;
  } अन्य
  // अन्य विषय सम्मिलन या विलोपन के साथ होते हैं:
    यदि (BF(Y) > 0) {// t3 अधिक था
      बीएफ(्स) = -1; //t1 अब उच्चतर
      बीएफ(जेड) = 0;
    } अन्य {
      // t2 अधिक था
      बीएफ(्स) = 0;
      बीएफ(जेड) = +1; // t4 अब उच्चतर
    }
  बीएफ(वाई) = 0;
  वापसी वाई; // घुमाए गए सबपेड़ की नई जड़ लौटाएं

} </सिंटैक्सहाइलाइट>

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

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

आकार के पेड़ के लिए n ≥ 1

• एवीएल पेड़ की ऊंचाई अधिकतम होती है

  ${\begin{array}{ll}h&\leqq \;c\log _{2}(n+d)+b\\&<\;c\log _{2}(n+2)+b\end{array}}$

जहाँ $\varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618$सुनहरा अनुपात, $c:={\tfrac {1}{\log _{2}\varphi }}\approx 1.440,$   $b:={\tfrac {c}{2}}\log _{2}5-2\approx \;-0.328,$ और $d:=1+{\tfrac {1}{\varphi ^{4}{\sqrt {5}}}}\approx 1.065$.

• आरबी पेड़ की ऊंचाई अधिकतम होती है

  ${\begin{array}{ll}h&\leqq \;2\log _{2}(n+1)\end{array}}$ .

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

यह भी देखें

• Wएवीएल पेड़
• स्पले पेड़
• बलि का बकरा पेड़
• बी-वृक्ष
• टी-वृक्ष
• डेटा संरचनाओं की सूची

अग्रिम पठन

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 458–475 of section 6.2.3: Balanced Trees.
• Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2015), "Rank-balanced trees" (PDF), ACM Transactions on Algorithms, 11 (4): Art. 30, 26, doi:10.1145/2689412, MR 3361215, S2CID 1407290.

बाहरी संबंध

•  This article incorporates public domain material from Black, Paul E. "AVL Tree". Dictionary of Algorithms and Data Structures.