एवीएल ट्री

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.