एवीएल ट्री

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) समय में पूर्ण किया जा सके। संचालन और थोक संचालन संग्रह करें एकल तत्व इंसर्ट, डिलीट और लुकअप विकल्प के अतिरिक्त, एवीएल पेड़ पर अनेक समूह विकल्प को परिभाषित किया गया है: संघ (समूह सिद्धांत), प्रतिच्छेदन (समूह सिद्धांत) और अंतर समूह आदि I इन समूह फलन के आधार पर सम्मिलन या विलोपन पर तीव्र बल्क संचालन प्रस्तावित किया जा सकता है। ये समूह संचालन दो सहायक संचालन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, एवीएल पेड़ों का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है। फलन दो एवीएल पेड़ों पर जुड़ें t1 और t2 और कुंजी k सभी तत्वों वाला पेड़ लौटाएगा I t1, t2 साथ ही k. उसकी आवश्यकता हैं I k सभी कुंजियों से बड़ा t1 और सभी कुंजियों से छोटा t2 होना चाहिए I यदि दो पेड़ों की ऊंचाई अधिकतम से भिन्न है, तो जॉइन बस बाएं उपवृक्ष के साथ नया ग्रंथि t1 बनाएं, जड़ k और दायां उपवृक्ष t2. अन्यथा, मान लीजिये t1 ये उससे ऊंचा है, t2 से अधिक के लिए (दूसरा विषय सममित है)। जॉइन की दाहिनी रीढ़ का अनुसरण t1 करता है, ग्रंथि c तक जिसके साथ t2 संतुलित है I इस बिंदु पर बाएँ बच्चे के साथ नया ग्रंथि c, जड़ k और सही बच्चा t2 c को प्रतिस्थापित करने के लिए बनाया गया है। नया ग्रंथि एवीएल अपरिवर्तनीय को संतुष्ट करता है, और इसकी ऊंचाई इससे अधिक है, c ऊंचाई में वृद्धि से इसके पूर्वजों की ऊंचाई बढ़ सकती है, संभवतः उन ग्रंथि के एवीएल अपरिवर्तनीय को अमान्य कर दिया जा सकता है। इसे या तो दोगुने घुमाव के साथ ठीक किया जा सकता है, यदि मूल पर अमान्य है या यदि पेड़ में उच्चतर अमान्य है तो एकल बाएं घुमाव के साथ, दोनों ही विषयों में किसी भी पूर्वज ग्रंथि के लिए ऊंचाई को बहाल किया जा सकता है। इसलिए जॉइन के लिए अधिकतम दो घुमावों की आवश्यकता होगी। इस फलन की लागत दो इनपुट पेड़ों के मध्य की ऊंचाई का अंतर है। style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | बांधना कलन विधि के लिए छदमकोड कार्यान्वयन function JoinRightAVL(TL, k, TR) (l, k', c) = expose(TL) if (Height(c) <= Height(TR)+1) T' = Node(c, k, TR) if (Height(T') <= Height(l)+1) then return Node(l, k', T') else return rotateLeft(Node(l, k', rotateRight(T'))) else T' = JoinRightAVL(c, k, TR) T = Node(l, k', T') if (Height(T') <= Height(l)+1) return T else return rotateLeft(T) function JoinLeftAVL(TL, k, TR) /* symmetric to JoinRightAVL */ function Join(TL, k, TR) if (Height(TL)>Height(TR)+1) return JoinRightAVL(TL, k, TR) if (Height(TR)>Height(TL)+1) return JoinLeftAVL(TL, k, TR) return Node(TL, k, TR)vHere Height(v) is the height of a subtree (node) v. (l,k,r) = expose(v) extracts v's left child l, the key k of v's root, and the right child r. Node(l,k,r) means to create a node of left child l, key k, and right child r.. एवीएल वृक्ष को दो छोटे वृक्षों में विभाजित करना, जो कुंजी k से छोटे हों, और वे कुंजी k से बड़े हैं, पूर्व मार्ग से k एवीएल में हैं। इस प्रविष्टि के पश्चात्, सभी मान इससे कम होंगे k पथ के बायीं ओर मिलेगा, और सभी मान इससे बड़े होंगे k दाहिनी ओर मिलेगा I जॉइन प्रस्तावित करने से, बायीं ओर के सभी उपवृक्षों को नीचे से ऊपर की ओर मध्यवर्ती ग्रंथि के रूप में पथ पर कुंजियों का उपयोग करके बाएँ वृक्ष बनाने के लिए विलय किया जाता है, और दायाँ भाग असममित होता है। विभाजित O(log n), पेड़ की ऊंचाई का क्रम की लागत है I style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | विभाजित कलन विधि के लिए स्यूडोकोड कार्यान्वयन function Split(T, k) if (T = nil) return (nil, false, nil) (L,m,R) = expose(T) if (k = m) return (L, true, R) if (k<m) (L',b,R') = Split(L,k) return (L', b, Join(R', m, R)) if (k>m) (L',b,R') = Split(R, k) return (Join(L, m, L'), b, R'))|} दो एवीएल पेड़ों का मिलन t1 और t2 समूह का प्रतिनिधित्व करना A और B, एवीएल है, t जो A ∪ B प्रतिनिधित्व करता है I style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " | यूनियन कलन विधि के लिए स्यूडोकोड कार्यान्वयन function Union(t1, t2): if t1 = nil: return t2 if t2 = nil: return t1 (t<, b, t>) = Split(t2, t1.root) return Join(Union(left(t1), t<), t1.root, Union(right(t1), t>)) यहां, विभाजित को दो पेड़ों को वापस करने के लिए माना जाता है: कुंजी को अपनी इनपुट कुंजी से कम रखता है, बड़ी कुंजी को रखता है। (एल्गोरिदम लगातार डेटा संरचना है | गैर-विनाशकारी, किन्तु इन-प्लेस विनाशकारी संस्करण भी उपस्थित है।) प्रतिच्छेदन या अंतर के लिए कलन विधि समान है, किन्तु इसके लिए जॉइन 2 हेल्पर मार्गीन की आवश्यकता होती है, जो कि जॉइन के समान है किन्तु मध्य कुंजी के बिना है। यूनियन, प्रतिच्छेदन या अंतर के नए कार्यों के आधार पर, एवीएल पेड़ में या तो एक कुंजी या अधिक कुंजियाँ डाली जा सकती हैं, या हटाई जा सकती हैं। चूंकि विभाजित कॉल जॉइन करता है किन्तु एवीएल पेड़ों के संतुलन मानदंडों से सीधे निपटता नहीं है, ऐसे कार्यान्वयन को सामान्यतः जॉइन-आधारित पेड़ कलन विधि कहा जाता है I सम्मिलित-आधारित कार्यान्वयन मिलन, प्रतिच्छेद और भेद प्रत्येक की जटिलता ${\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 की ऊंचाई बढ़ गई है। विलोपन के विषय में यह विलोपन सहोदर t1 को हुआ है, Z प्रकार से जिससे t1 की ऊंचाई पूर्व से ही कम होने के कारण कम हो गई है। (यह मात्र मामला है जहां Z का संतुलन कारक 0 भी हो सकता है।) उल्लंघन के चार संभावित प्रकार हैं: दाएँ दाएँ ⟹ Z दायां है इसके माता-पिता X और BF(Z) का बच्चा ≥ 0 बाएँ बाएँ ⟹ Z बायां है इसके माता-पिता X और BF(Z) का बच्चा ≤ 0 दाएँ बाएँ ⟹ Z दायां है इसके माता-पिता X और BF(Z) का बच्चा < 0 बाएँ दाएँ ⟹ Z बायां है इसके माता-पिता X और BF(Z) का बच्चा > 0 और पुनर्संतुलन भिन्न प्रकार से किया जाता है: दाएँ दाएँ ⟹ X को a के साथ पुनः संतुलित किया गया है सरल घुमाव rotate_Left (रेखा - चित्र देखें 2) बाएँ बाएँ ⟹ X को a के साथ पुनः संतुलित किया गया है सरल घुमाव rotate_Right (आकृति की दर्पण-छवि 2) दाएँ बाएँ ⟹ X को a के साथ पुनः संतुलित किया गया है दोगुना घुमाव rotate_RightLeft (रेखा - चित्र देखें 3) बाएँ दाएँ ⟹ X को a के साथ पुनः संतुलित किया गया है दोगुना घुमाव rotate_LeftRight (आकृति की दर्पण-छवि 3) C B, जिससे स्थितियों को निरूपित किया जाता है, जहां C (= बच्चे की दिशा) और B (= संतुलन) समूह से आते हैं { Left, Right } साथ Right := −Left. विषय का शेष उल्लंघन C == B के साधारण घुमाव द्वारा की जाती है I rotate_(−C), जबकि विषय C != B की दोहरे घुमाव rotate_CB. द्वारा की जाती है I घुमाव की लागत, चाहे वह साधारण हो या दोगुनी, स्थिर होती है। सरल घुमाव चित्र 2 दाएं-दाएं स्थिति प्रदर्शित करता है। इसके ऊपरी अर्ध भाग में, ग्रंथि X में +2. इसके अतिरिक्त, आंतरिक बच्चा t23 Z का (अर्थात, बायां बच्चा जब Z दायां बच्चा है, या दायां बच्चा जब Z बायां बच्चा है) अपने सहोदर t4 से अधिक नहीं है I यह उपपेड़ t4 की ऊंचाई बढ़ने से हो सकता है, या उपवृक्ष t1 की ऊंचाई में कमी से पश्चात् वाले विषय में भी, पीली स्थिति जहां t233 इसकी ऊँचाई t4 के समान है I बाएँ घुमाव का परिणाम चित्र के निचले अर्ध भाग में प्रदर्शित किया गया है। तीन लिंक (चित्र 2 में मोटे किनारे) और दो संतुलन कारकों को अद्यतन किया जाना है। जैसा कि चित्र से ज्ञात होता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और घूमने के पश्चात् पुनः स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 स्तर पर थी, जहां यह पुनः है, जब t23 और t4 ही कद के थे. अन्यथा पत्ती की परत h+1 स्तर तक पहुंच जाती है, जिससे घूमने वाले पेड़ की ऊंचाई कम हो जाती है। चित्र 2: सरल घुमाव rotate_Left(X,Z) सरल बाएँ घुमाव का कोड स्निपेट इनपुट: X = उपवृक्ष की जड़ को बायीं ओर घुमाना है Z = X, Z का दायाँ बच्चा दायाँ-भारी है     with height == Height(LeftSubtree(X))+2 परिणाम: पुनर्संतुलित उपवृक्ष की नई जड़ node *rotate_Left(node *X, node *Z) { // Z is by 2 higher than its sibling t23 = left_child(Z); // Inner child of Z right_child(X) = t23; if (t23 != null) parent(t23) = X; left_child(Z) = X; parent(X) = Z; // 1st case, BF(Z) == 0, // only happens with deletion, not insertion: if (BF(Z) == 0) { // t23 has been of same height as t4 BF(X) = +1; // t23 now higher BF(Z) = –1; // t4 now lower than X } else { // 2nd case happens with insertion or deletion: BF(X) = 0; BF(Z) = 0; } return Z; // return new root of rotated subtree } दोहरा घुमाव चित्र 3 दाएँ बाएँ स्थिति को प्रदर्शित करता है। इसके ऊपरी तीसरे भाग में, ग्रंथि X में +2. किन्तु चित्र 2 के विपरीत, Z का आंतरिक बच्चा Y उसके भाई t4 से ऊंचा है I यह स्वयं Y के सम्मिलन या इसके किसी उपवृक्ष t2 की ऊँचाई में वृद्धि से हो सकता है, या t3 (इस परिणाम के साथ कि वे भिन्न-भिन्न ऊंचाई के हैं) या उपवृक्ष t1 की ऊंचाई में कमी से पश्चात् वाले विषय में, यह भी हो सकता है कि t2 और t3 समान ऊंचाई के हैं. पूर्व, दाएँ, घुमाव का परिणाम चित्र के मध्य तीसरे में दिखाया गया है। (संतुलन कारकों के संबंध में, यह घुमाव अन्य एवीएल एकल घुमावों के समान नहीं है, क्योंकि Y और t4 के मध्य ऊंचाई का अंतर है केवल 1 है।) अंतिम बाएँ घुमाव का परिणाम चित्र के निचले तीसरे भाग में दिखाया गया है। पांच लिंक (चित्रा 3 में मोटे किनारे) और तीन संतुलन कारकों को अद्यतन किया जाना है। जैसा कि चित्र से ज्ञात होता है, सम्मिलन से पूर्व, पत्ती की परत स्तर h+1 पर थी, अस्थायी रूप से स्तर h+2 पर और दोहरे घुमाव के पश्चात् पुनः स्तर h+1 पर थी। विलोपन के विषय में, पत्ती की परत h+2 के स्तर पर थी और दोहरे घुमाव के पश्चात् यह h+1 के स्तर पर थी, जिससे कि घुमाए गए पेड़ की ऊंचाई कम हो गई। चित्र 3: डबल घुमाव दाएँ बाएँ (X,Z) = घुमाव _दाएँ Z के चारों ओर और उसके पश्चात् X के चारों ओर बाएँ घुमाएँ ;दाएँ-बाएँ दोहरे घुमाव का कोड स्निपेट इनपुट: X = उपवृक्ष की जड़ को घुमाना है Z = इसका दाहिना बच्चा, बायाँ-भारी     with height == Height(LeftSubtree(X))+2 परिणाम: पुनर्संतुलित उपवृक्ष की नई जड़ node *rotate_RightLeft(node *X, node *Z) { // Z is by 2 higher than its sibling Y = left_child(Z); // Inner child of Z // Y is by 1 higher than sibling t3 = right_child(Y); left_child(Z) = t3; if (t3 != null) parent(t3) = Z; right_child(Y) = Z; parent(Z) = Y; t2 = left_child(Y); right_child(X) = t2; if (t2 != null) parent(t2) = X; left_child(Y) = X; parent(X) = Y; // 1st case, BF(Y) == 0, // only happens with deletion, not insertion: if (BF(Y) == 0) { BF(X) = 0; BF(Z) = 0; } else // other cases happen with insertion or deletion: if (BF(Y) > 0) { // t3 was higher BF(X) = –1; // t1 now higher BF(Z) = 0; } else { // t2 was higher BF(X) = 0; BF(Z) = +1; // t4 now higher } BF(Y) = 0; return Y; // return new root of rotated subtree } अन्य संरचनाओं से तुलना एवीएल पेड़ और लाल-काले (आरबी) पेड़ दोनों स्व-संतुलन वाले द्विआधारी परीक्षण पेड़ हैं, और वे गणितीय रूप से संबंधित हैं। प्रत्येक एवीएल पेड़ को लाल-काला रंग दिया जा सकता है, किन्तु ऐसे आरबी पेड़ हैं जो एवीएल संतुलित नहीं हैं। एवीएल (या आरबी) पेड़ के अपरिवर्तनीयों को बनाए रखने के लिए, घुमाव महत्वपूर्ण भूमिका निभाते हैं। सबसे अमान्य स्थिति में, घुमाव के बिना भी, एवीएल या आरबी सम्मिलन या विलोपन की आवश्यकता होती है I O(log n) एवीएल संतुलन कारकों (या आरबी रंग) का निरीक्षण और/या अद्यतन आरबी सम्मिलन और विलोपन और एवीएल सम्मिलन के लिए शून्य से तीन टेल-रिकर्सिव घुमाव की आवश्यकता होती है और O(1) समय अमूर्त विश्लेषण में चलाया जाता है I इस प्रकार औसतन समान रूप से स्थिर एवीएल विलोपन की आवश्यकता है I 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 के मध्य एवीएल/आरबी का संबंध प्रदर्शित करता है। यह भी देखें डव्लूएवीएल पेड़ छींटे का पेड़ स्केपगोट पेड़ बी-वृक्ष टी-वृक्ष डेटा संरचनाओं की सूची संदर्भ अग्रिम पठन 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.