एवीएल ट्री

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; " | सम्मिलित संचालन के लिए उदाहरण कोड

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) समय में पूर्ण किया जा सके। विलोपन किसी ग्रंथि के विलोपन को प्रारंभिक चरण द्विआधारी परीक्षण पेड़ विलोपन अनुभाग में वर्णित किया गया हैं। वहां, विषय ग्रंथि या प्रतिस्थापन ग्रंथि का प्रभावी विलोपन संबंधित चाइल्ड पेड़ की ऊंचाई को 1 से 0 या 2 से 1 तक कम कर देता है, यदि उस ग्रंथि में बच्चा था। इस उपवृक्ष से प्रारम्भ करते हुए, एवीएल पेड़ों के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक पूर्वज की जांच करना आवश्यक है। इसे पुनः अनुरेखण कहा जाता है। चूँकि विलोपन से एवीएल उपवृक्ष की ऊँचाई से अधिक नहीं घट सकती, ग्रंथि का अस्थायी संतुलन कारक −2 से +2 तक की सीमा में होगा। यदि संतुलन कारक -1 से +1 की सीमा में रहता है, तो इसे एवीएल नियमों के अनुसार समायोजित किया जा सकता है। यदि यह ±2 हो जाता है, तो उपवृक्ष असंतुलित है, और इसे घुमाने की आवश्यकता है। (सम्मिलन के विपरीत जहां घुमाव सदैव पेड़ को संतुलित करता है, विलोपन के पश्चात्, BF(Z) ≠ 0 हो सकता है, (आंकड़े 2 और 3 देखें), जिससे उचित एकल या दोगुने घुमाव के पश्चात् पुनर्संतुलित उपपेड़ की ऊंचाई अर्थ से कम हो जाए कि पेड़ को उच्च स्तर पर पुनः से संतुलित करना होगा।) घूर्णन के विभिन्न विषयों को खंड पुनर्संतुलन में वर्णित किया गया है। विलोपन के लिए रिट्रेसिंग लूप का अपरिवर्तनीय N द्वारा मार्ग किए गए उपवृक्ष की ऊंचाई 1 से कम हो गई है। यह पूर्व से ही एवीएल आकार में है। style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | विलोपन संचालन के लिए उदाहरण कोड for (X = parent(N); X != null; X = G) { // Loop (possibly up to the root) G = parent(X); // Save parent of X around rotations // BF(X) has not yet been updated! if (N == left_child(X)) { // the left subtree decreases if (BF(X) > 0) { // X is right-heavy // ==> the temporary BF(X) == +2 // ==> rebalancing is required. Z = right_child(X); // Sibling of N (higher by 2) b = BF(Z); if (b < 0) // Right Left Case (see figure 3) N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X) else // Right Right Case (see figure 2) N = rotate_Left(X, Z); // Single rotation Left(X) // After rotation adapt parent link } else { if (BF(X) == 0) { BF(X) = +1; // N’s height decrease is absorbed at X. break; // Leave the loop } N = X; BF(N) = 0; // Height(N) decreases by 1 continue; } } else { // (N == right_child(X)): The right subtree decreases if (BF(X) < 0) { // X is left-heavy // ==> the temporary BF(X) == -2 // ==> rebalancing is required. Z = left_child(X); // Sibling of N (higher by 2) b = BF(Z); if (b > 0) // Left Right Case N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X) else // Left Left Case N = rotate_Right(X, Z); // Single rotation Right(X) // After rotation adapt parent link } else { if (BF(X) == 0) { BF(X) = -1; // N’s height decrease is absorbed at X. break; // Leave the loop } N = X; BF(N) = 0; // Height(N) decreases by 1 continue; } } // After a rotation adapt parent link: // N is the new root of the rotated subtree parent(N) = G; if (G != null) { if (X == left_child(G)) left_child(G) = N; else right_child(G) = N; } else tree->root = N; // N is the new root of the total tree if (b == 0) break; // Height does not change: Leave the loop // Height(N) decreases by 1 (== old Height(X)-1) } // If (b != 0) the height of the total tree decreases by 1. यदि संतुलन कारक ±1 हो जाता है (यह 0 रहा होगा) तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस उपवृक्ष की ऊंचाई अपरिवर्तित रहती है। यदि संतुलन कारक 0 हो जाता है (यह ±1 होना चाहिए) तो उपवृक्ष की ऊंचाई कम हो जाती है और अनुसंधान प्रारम्भ रखने की आवश्यकता होती है। यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा सही करना होगा। यह सहोदर Z (चित्र 2 में उच्च संतान वृक्ष) के संतुलन कारक पर निर्भर करता है कि क्या उपवृक्ष की ऊंचाई से कम हो जाती है- और अनुसंधान प्रारम्भ रखने की आवश्यकता है - या नहीं परिवर्तित होता है (यदि Z का संतुलन कारक 0 है) और पूर्ण पेड़ एवीएल-आकार में है। समय की आवश्यकता है I O(log n) लुकअप के लिए, साथ ही अधिकतम O(log n) पुनः अनुरेखण स्तर (O(1) औसतन) मार्ग पर पुनःजा रहा है, जिससे संचालन O(log n) समय में पूर्ण किया जा सके। संचालन और थोक संचालन समूह करें सिंगल-एलिमेंट इंसर्ट, डिलीट और लुकअप ऑपरेशंस के अलावा, एवीएल पेड़ पर कई समूह ऑपरेशंस को परिभाषित किया गया है: संघ (समूह सिद्धांत) , प्रतिच्छेदन (समूह सिद्धांत) और अंतर समूह करें । फिर इन समूह फ़ंक्शंस के आधार पर सम्मिलन या विलोपन पर तीव्र बल्क संचालन प्रस्तावित किया जा सकता है। ये समूह संचालन दो सहायक संचालन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, एवीएल पेड़ों का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है। फलन दो एवीएल पेड़ों पर जुड़ें t1 और t2 और कुंजी k सभी तत्वों वाला पेड़ लौटाएगा t1, t2 साथ ही k. उसकी आवश्यकता हैं k सभी कुंजियों से बड़ा होना t1 और सभी कुंजियों से छोटा t2. यदि दो पेड़ों की ऊंचाई अधिकतम से भिन्न है, तो Join बस बाएं उपवृक्ष के साथ नया ग्रंथि बनाएं t1, जड़ k और दायां उपवृक्ष t2. अन्यथा, मान लीजिये t1 ये उससे ऊंचा है t2 से अधिक के लिए (दूसरा मामला सममित है)। जॉइन की दाहिनी रीढ़ का अनुसरण करता है t1 ग्रंथि तक c जिसके साथ संतुलित है t2. इस बिंदु पर बाएँ बच्चे के साथ नया ग्रंथि c, जड़ k और सही बच्चा t2 c को प्रतिस्थापित करने के लिए बनाया गया है। नया ग्रंथि एवीएल अपरिवर्तनीय को संतुष्ट करता है, और इसकी ऊंचाई इससे अधिक है c. ऊंचाई में वृद्धि से इसके पूर्वजों की ऊंचाई बढ़ सकती है, संभवतः उन ग्रंथि के एवीएल अपरिवर्तनीय को अमान्य कर दिया जा सकता है। इसे या तो डबल रोटेशन के साथ ठीक किया जा सकता है यदि मूल पर अमान्य है या यदि पेड़ में उच्चतर अमान्य है तो ल बाएं रोटेशन के साथ, दोनों ही विषयों में किसी भी पूर्वज ग्रंथि के लिए ऊंचाई को बहाल किया जा सकता है। इसलिए जॉइन के लिए अधिकतम दो घुमावों की आवश्यकता होगी। इस फलन की लागत दो इनपुट पेड़ों के बीच की ऊंचाई का अंतर है। style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | बांधना कलन विधि के लिए छदमकोड कार्यान्वयन function JoinRightAVL(TL, k, TR) (l, k', c) = expose(TL) if (Height(c) <= Height(TR)+1) T' = Node(c, k, TR) if (Height(T') <= Height(l)+1) then return Node(l, k', T') else return rotateLeft(Node(l, k', rotateRight(T'))) else T' = JoinRightAVL(c, k, TR) T = Node(l, k', T') if (Height(T') <= Height(l)+1) return T else return rotateLeft(T) function JoinLeftAVL(TL, k, TR) /* symmetric to JoinRightAVL */ function Join(TL, k, TR) if (Height(TL)>Height(TR)+1) return JoinRightAVL(TL, k, TR) if (Height(TR)>Height(TL)+1) return JoinLeftAVL(TL, k, TR) return Node(TL, k, TR)vHere Height(v) is the height of a subtree (node) v. (l,k,r) = expose(v) extracts v's left child l, the key k of v's root, and the right child r. Node(l,k,r) means to create a node of left child l, key k, and right child r.. एवीएल वृक्ष को दो छोटे वृक्षों में विभाजित करना, जो कुंजी से छोटे हों k, और वे कुंजी से बड़े हैं k, पहले मार्ग से रास्ता डालकर डालें kएवीएल में। इस प्रविष्टि के पश्चात्, सभी मान इससे कम होंगे k पथ के बायीं ओर मिलेगा, और सभी मान इससे बड़े होंगे k दाहिनी ओर मिलेगा. जॉइन प्रस्तावित करने से, बायीं ओर के सभी उपवृक्षों को नीचे से ऊपर की ओर मध्यवर्ती ग्रंथि के रूप में पथ पर कुंजियों का उपयोग करके बाएँ वृक्ष बनाने के लिए मर्ज किया जाता है, और दायाँ भाग असममित होता है। स्प्लिट की लागत है 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) (एल',बी,आर') = स्प्लिट(आर, के) वापसी (जुड़ें (एल, एम, एल'), बी, आर')) दो एवीएल पेड़ों का मिलन t1 और t2 समूह का प्रतिनिधित्व करना 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 की ऊंचाई बढ़ गई है। विलोपन के विषय में यह विलोपन सहोदर टी को हुआ है1 Z का प्रकार से जिससे t1की ऊंचाई पहले से ही कम होने के कारण कम हो गई है। (यह मात्र मामला है जहां 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. इसके अलावा, आंतरिक बच्चा टी23 Z का (अर्थात, बायां बच्चा जब Z दायां बच्चा है, या दायां बच्चा जब Z बायां बच्चा है) अपने सहोदर से अधिक नहीं है4. यह सबपेड़ टी की ऊंचाई बढ़ने से हो सकता है4 या उपवृक्ष टी की ऊंचाई में कमी से1. पश्चात् वाले विषय में भी, पीली स्थिति जहां टी23 इसकी ऊँचाई t के समान है4 तब हो सकती है। बाएँ घुमाव का परिणाम चित्र के निचले आधे भाग में दिखाया गया है। तीन लिंक (चित्र 2 में मोटे किनारे) और दो संतुलन कारकों को अद्यतन किया जाना है। जैसा कि चित्र से पता चलता है, सम्मिलन से पहले, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और घूमने के पश्चात् फिर से स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 स्तर पर थी, जहां यह फिर से है, जब t23 और टी4 ही कद के थे. अन्यथा पत्ती की परत 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 से ऊंचा है4. यह स्वयं Y के सम्मिलन या इसके किसी उपवृक्ष t की ऊँचाई में वृद्धि से हो सकता है2 या टी3 (इस परिणाम के साथ कि वे अलग-अलग ऊंचाई के हैं) या उपवृक्ष टी की ऊंचाई में कमी से1. पश्चात् वाले विषय में, यह भी हो सकता है कि टी2 और टी3 समान ऊंचाई के हैं. पहले, दाएँ, घुमाव का परिणाम चित्र के मध्य तीसरे में दिखाया गया है। (संतुलन कारकों के संबंध में, यह घुमाव अन्य एवीएल ल घुमावों के समान नहीं है, क्योंकि Y और t के बीच ऊंचाई का अंतर है4 केवल 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.