एवीएल ट्री

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)$

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

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

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

एवीएल पेड़ का नाम इसके दो सोवियत संघ के आविष्कारकों, जॉर्जी एडेल्सन-वेल्स्की और एवगेनी लैंडिस के नाम पर रखा गया है, जिन्होंने इसे अपने 1962 के पेपर एन एल्गोरिदम फॉर द ऑर्गनाइजेशन ऑफ इंफॉर्मेशन में प्रकाशित किया था। यह आविष्कार किया जाने वाला सबसे पुराना स्व-संतुलन बाइनरी सर्च ट्री डेटा संरचना है। एवीएल पेड़ों की तुलना अक्सर लाल-काले पेड़ों से की जाती है क्योंकि दोनों ऑपरेशन और टेक के समान सेट का समर्थन करते हैं ${\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$ (स्तरों की अधिकतम संख्या के रूप में गिना जाता है) AVL वृक्ष के साथ $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.$

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

संचालन

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

खोज रहा हूँ

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

ट्रैवर्सल

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

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

सम्मिलित करें

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

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

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

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

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

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

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 तक कम कर देता है, यदि उस नोड में एक बच्चा था।

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

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

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

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

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 है) और पूरा पेड़ AVL-आकार में है।

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

संचालन और थोक संचालन सेट करें

सिंगल-एलिमेंट इंसर्ट, डिलीट और लुकअप ऑपरेशंस के अलावा, एवीएल ट्री पर कई सेट ऑपरेशंस को परिभाषित किया गया है: संघ (सेट सिद्धांत) , प्रतिच्छेदन (सेट सिद्धांत) और अंतर सेट करें । फिर इन सेट फ़ंक्शंस के आधार पर सम्मिलन या विलोपन पर तेज़ बल्क ऑपरेशन लागू किया जा सकता है। ये सेट ऑपरेशन दो सहायक ऑपरेशन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, एवीएल पेड़ों का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है। फ़ंक्शन दो AVL पेड़ों पर जुड़ें 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.

एक AVL वृक्ष को दो छोटे वृक्षों में विभाजित करना, जो कुंजी से छोटे हों 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 देखें)। ध्यान दें कि दोनों बच्चे गणितीय प्रेरण द्वारा AVL आकार में हैं।

सम्मिलन के मामले में यह सम्मिलन 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;
   यदि (t23 != शून्य)
       पैरेंट(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;
   वापसी वाई; // घुमाए गए सबट्री की नई जड़ लौटाएं

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

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

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

यह भी देखें

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

अग्रिम पठन

• 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.