एवीएल ट्री: Difference between revisions
m (added Category:Vigyan Ready using HotCat) |
No edit summary |
||
(One intermediate revision by one other user not shown) | |||
Line 459: | Line 459: | ||
{{Data structures}} | {{Data structures}} | ||
{{DEFAULTSORT:AVL Tree}} | {{DEFAULTSORT:AVL Tree}} | ||
[[Category:1962 कंप्यूटिंग में|AVL Tree]] | |||
[[Category:CS1 maint]] | |||
[[Category: | [[Category:CS1 русский-language sources (ru)]] | ||
[[Category:Created On 07/07/2023]] | [[Category:Collapse templates|AVL Tree]] | ||
[[Category:Vigyan Ready]] | [[Category:Commons category link is locally defined|AVL Tree]] | ||
[[Category:Created On 07/07/2023|AVL Tree]] | |||
[[Category:Lua-based templates|AVL Tree]] | |||
[[Category:Machine Translated Page|AVL Tree]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists|AVL Tree]] | |||
[[Category:Pages with script errors|AVL Tree]] | |||
[[Category:Sidebars with styles needing conversion|AVL Tree]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready|AVL Tree]] | |||
[[Category:Templates generating microformats|AVL Tree]] | |||
[[Category:Templates that add a tracking category|AVL Tree]] | |||
[[Category:Templates that are not mobile friendly|AVL Tree]] | |||
[[Category:Templates that generate short descriptions|AVL Tree]] | |||
[[Category:Templates using TemplateData|AVL Tree]] | |||
[[Category:Wikipedia metatemplates|AVL Tree]] | |||
[[Category:पेड़ खोजें|AVL Tree]] | |||
[[Category:बाइनरी पेड़|AVL Tree]] | |||
[[Category:सोवियत आविष्कार|AVL Tree]] | |||
[[Category:स्यूडोकोड उदाहरण सहित लेख|AVL Tree]] |
Latest revision as of 18:56, 21 July 2023
AVL tree | |||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | Tree | ||||||||||||||||||||||||||||
Invented | 1962 | ||||||||||||||||||||||||||||
Invented by | Georgy Adelson-Velsky and Evgenii Landis | ||||||||||||||||||||||||||||
Complexities in big O notation | |||||||||||||||||||||||||||||
|
कंप्यूटर विज्ञान में, एवीएल ट्री (आविष्कारकों एडेलसन-वेल्स्की और लैंडिस के नाम पर) स्व-संतुलन द्विआधारी परीक्षण ट्री है। एवीएल ट्री में, किसी भी नोड्स के दो बाल नोड्स अर्धट्री की ऊंचाई अधिकतम से भिन्न होती है; यदि किसी भी समय उनमें से अधिक का अंतर होता है, तो इस संपत्ति को पुनर्स्थापित करने के लिए पुनर्संतुलन किया जाता है। लुकअप, सम्मिलन और विलोपन सभी लेते हैं I O(log n) औसत और सबसे अमान्य दोनों विषयों में समय, जहां संचालन से पूर्व ट्री में नोड्स की संख्या होती है। सम्मिलन और विलोपन के लिए ट्री को एक या अधिक ट्री घुमावों द्वारा पुनर्संतुलित करने की आवश्यकता हो सकती है I
एवीएल ट्री का नाम इसके दो सोवियत संघ के आविष्कारकों, जॉर्जी एडेल्सन-वेल्स्की और एवगेनी लैंडिस के नाम पर रखा गया है, जिन्होंने इसे अपने 1962 के पेपर एन एल्गोरिदम फॉर द ऑर्गनाइजेशन ऑफ इंफॉर्मेशन में प्रकाशित किया था।[2] यह आविष्कार किया जाने वाला सबसे प्राचीन स्व-संतुलन द्विआधारी अनुसंधान ट्री डेटा संरचना है।[3] एवीएल ट्री की तुलना प्रायः लाल-काले ट्री से की जाती है, क्योंकि दोनों संचालन और टेक के समान समूह का समर्थन करते हैं I प्रारंभिक कार्यों के लिए समय लुकअप-गहन अनुप्रयोगों के लिए, एवीएल ट्री लाल-काले ट्री की तुलना में तीव्र होते हैं, क्योंकि वे अधिक कठोरता से संतुलित होते हैं।[4] लाल-काले ट्री के समान, एवीएल ट्री ऊंचाई-संतुलित होते हैं। सामान्यतः, दोनों न तो वजन-संतुलित ट्री हैं, न ही वजन-संतुलित -किसी के लिए संतुलित ;[5] अर्थात्, सहोदर नोड्स में वंशजों की संख्या बहुत भिन्न हो सकती है।
परिभाषा
संतुलन कारक
द्विआधारी ट्री में नोड्स के संतुलन कारक को ऊंचाई अंतर के रूप में परिभाषित किया गया है:-
- [6]: 459
इसके दो बाल अर्ध-ट्री का द्विआधारी ट्री को एवीएल ट्री के रूप में परिभाषित किया गया है, यदि इनवेरिएंट (कंप्यूटर विज्ञान)
ट्री में प्रत्येक नोड्स X के लिए धारण करता है।
नोड्स के साथ वाम-भारी कहा जाता है, के साथ दाएँ-भारी कहा जाता है, और के साथ कभी-कभी इसे केवल संतुलित कहा जाता है।
गुण
पूर्व संतुलन कारकों और ऊंचाई में परिवर्तन को समझकर संतुलन कारकों को अद्यतन रखा जा सकता है- पूर्ण ऊंचाई जानना आवश्यक नहीं है। एवीएल संतुलन जानकारी रखने के लिए, प्रति नोड्स दो बिट पर्याप्त हैं।[8] ऊंचाई (स्तरों की अधिकतम संख्या के रूप में गिना जाता है) एवीएल ट्री के साथ नोड्स अंतराल में निहित हैं:[6]: 460
- जहाँ सुनहरा अनुपात है और
इसका कारण ऊंचाई का एवीएल ट्री है, कम से कम सम्मिलित है I नोड्स जहाँ बीज मूल्यों के साथ फाइबोनैचि संख्या है I
संचालन
एवीएल ट्री के रीड-ओनली संचालन में वही क्रियाएं सम्मिलित होती हैं, जो असंतुलित द्विआधारी परीक्षण ट्री पर की जाती हैं, किन्तु संशोधनों में अर्ध-ट्री की ऊंचाई संतुलन का निरीक्षण करना और पुनर्स्थापित करना होता है।
अन्वेषण
एवीएल ट्री में विशिष्ट कुंजी के परीक्षण उसी प्रकार से किये जा सकते है जैसे किसी संतुलित या असंतुलित द्विआधारी परीक्षण ट्री अन्वेषण की होती है।[9]: ch. 8 परीक्षण को प्रभावी प्रकार से काम करने के लिए इसे तुलना फलन को नियोजित करना होगा, जो कुंजियों के समूह पर कुल ऑर्डर (या कम से कम निर्बल ऑर्डर, कुल प्रीऑर्डर) स्थापित करता है।[10]: 23 सफल परीक्षण के लिए आवश्यक तुलनाओं की संख्या ऊंचाई h तक सीमित है, और असफल परीक्षण के लिए h बहुत निकट है, तो दोनों O(log n) अंदर हैं I[11]: 216
ट्रैवर्सल
रीड-ओनली विकल्प के रूप में एवीएल ट्री का ट्रैवर्सल किसी अन्य द्विआधारी ट्री के जैसे ही कार्य करता है। सभी का अन्वेषण n ट्री के नोड्स प्रत्येक लिंक पर ठीक दो बार जाते हैं: नीचे की ओर जाने वाली यात्रा उस नोड्स द्वारा निहित अर्ध-ट्री में प्रवेश करने के लिए, दूसरी ऊपर की ओर जाने वाली यात्रा उस नोड्स के अर्ध-ट्री का पता लगाने के पश्चात् उसे त्यागने के लिए जाती है।
एवीएल ट्री में नोड्स मिल जाने के पश्चात्, पूर्व नोड्स को अमूर्त जटिलता निरंतर समय में प्रवेश किया जा सकता है।[12]: 58 इन निकट के नोड्स की परीक्षण के कुछ उदाहरणों में ट्रैवर्सिंग की आवश्यकता होती है, h ∝ log(n) लिंक (विशेष रूप से जब जड़ के बाएं अर्धट्री के सबसे दाहिने पत्ते से जड़ तक या जड़ से जड़ के दाएं अर्धट्री के सबसे बाएं पत्ते तक नेविगेट करते हैं; चित्र 1 के एवीएल ट्री में, नोड्स P से अगले-से-दाएँ तक नेविगेट करना नोड्स Q 3 चरण लेता है)। क्योंकि वहां n−1 हैं, किसी भी ट्री में लिंक, परिशोधित लागत 2×(n−1)/n है, या लगभग 2 है I
सन्निविष्ट करना
एवीएल ट्री में नोड्स के प्रवेश होते समय, आप प्रारम्भ में द्विआधारी परीक्षण ट्री में प्रवेश जैसी ही प्रक्रिया का पालन करते हैं। यदि ट्री रिक्त है, तो नोड्स को ट्री की जड़ के रूप में डाला जाता है। यदि ट्री रिक्त नहीं है, तो हम जड़ के नीचे जाते हैं, और नए नोड्स को सम्मिलित करने के लिए स्थान का परीक्षण करते हुए पुनरावर्ती रूप से ट्री के नीचे जाते हैं। यह ट्रैवर्सल तुलना फलन द्वारा निर्देशित होता है। इस विषय में, नोड्स सदैव ट्री में किसी बाहरी नोड्स के अशक्त संदर्भ (बाएं या दाएं) को प्रतिस्थापित करता है, जिससे, नोड्स को या तो बाहरी नोड्स का बायां-चाइल्ड या दायां-चाइल्ड बनाया जाता है।
इस प्रविष्टि के पश्चात्, यदि कोई ट्री असंतुलित हो जाता है, तो केवल नए डाले गए नोड्स के पूर्वज असंतुलित होते हैं। ऐसा इसलिए है क्योंकि केवल उन नोड्स के अर्ध-ट्री परिवर्तित किये गए हैं।[13] इसलिए एवीएल ट्री के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक नोड्स के पूर्वजों की जांच करना आवश्यक है: इसे अनुसंधान कहा जाता है। यह प्रत्येक नोड्स के संतुलन कारक पर विचार करके प्राप्त किया जाता है।[6]: 458–481 [12]: 108
चूंकि एकल सम्मिलन के साथ एवीएल अर्धट्री की ऊंचाई से अधिक नहीं बढ़ सकती है, सम्मिलन के पश्चात् नोड्स का अस्थायी संतुलन कारक सीमा [–2,+2]. में होगा I परीक्षण किये गए प्रत्येक नोड्स के लिए, यदि अस्थायी संतुलन कारक -1 से +1 तक की सीमा में रहता है, तो केवल संतुलन कारक का अद्यतन और कोई नियमित आवर्तन आवश्यक नहीं है। चूंकि, यदि अस्थायी संतुलन कारक ±2 है, तो इस नोड्स पर निहित अर्धट्री एवीएल असंतुलित है, और नियमित आवर्तन की आवश्यकता है।[10]: 52 जैसा कि नीचे दिए गए कोड से ज्ञात होता है, सम्मिलन के साथ, पर्याप्त नियमित आवर्तन ट्री को पुनः संतुलित करता है।
चित्र 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) समय में पूर्ण किया जा सके।[10]: 53 विलोपनकिसी नोड्स के विलोपन को प्रारंभिक चरण द्विआधारी परीक्षण ट्री विलोपन अनुभाग में वर्णित किया गया हैं। वहां, विषय नोड्स या प्रतिस्थापन नोड्स का प्रभावी विलोपन संबंधित चाइल्ड ट्री की ऊंचाई को 1 से 0 या 2 से 1 तक कम कर देता है, यदि उस नोड्स में बच्चा था। इस अर्धट्री से प्रारम्भ करते हुए, एवीएल ट्री के अपरिवर्तनीयों के साथ स्थिरता के लिए प्रत्येक पूर्वज की जांच करना आवश्यक है। इसे पुनः अनुरेखण कहा जाता है। चूँकि विलोपन से एवीएल अर्धट्री की ऊँचाई से अधिक नहीं घट सकती, नोड्स का अस्थायी संतुलन कारक −2 से +2 तक की सीमा में होगा। यदि संतुलन कारक -1 से +1 की सीमा में रहता है, तो इसे एवीएल नियमों के अनुसार समायोजित किया जा सकता है। यदि यह ±2 हो जाता है, तो अर्धट्री असंतुलित है, और इसे घुमाने की आवश्यकता है। (सम्मिलन के विपरीत जहां घुमाव सदैव ट्री को संतुलित करता है, विलोपन के पश्चात्, BF(Z) ≠ 0 हो सकता है, (आंकड़े 2 और 3 देखें), जिससे उचित एकल या दोगुने घुमाव के पश्चात् पुनर्संतुलित अर्धट्री की ऊंचाई अर्थ से कम हो जाए कि ट्री को उच्च स्तर पर पुनः से संतुलित करना होगा।) घूर्णन के विभिन्न विषयों को खंड पुनर्संतुलन में वर्णित किया गया है।
N द्वारा मार्ग किए गए अर्धट्री की ऊंचाई 1 से कम हो गई है। यह पूर्व से ही एवीएल आकार में है।
यदि संतुलन कारक ±1 हो जाता है (यह 0 रहा होगा) तो अनुसंधान बाधित हो सकता है, जिसका अर्थ है कि उस अर्धट्री की ऊंचाई अपरिवर्तित रहती है। यदि संतुलन कारक 0 हो जाता है (यह ±1 होना चाहिए) तो अर्धट्री की ऊंचाई कम हो जाती है और अनुसंधान प्रारम्भ रखने की आवश्यकता होती है। यदि संतुलन कारक अस्थायी रूप से ±2 हो जाता है, तो इसे उचित घुमाव द्वारा सही करना होगा। यह सहोदर Z (चित्र 2 में उच्च संतान ट्री) के संतुलन कारक पर निर्भर करता है कि क्या अर्धट्री की ऊंचाई से कम हो जाती है- और अनुसंधान प्रारम्भ रखने की आवश्यकता है - या नहीं परिवर्तित होता है (यदि Z का संतुलन कारक 0 है) और पूर्ण ट्री एवीएल-आकार में है। समय की आवश्यकता है I O(log n) लुकअप के लिए, साथ ही अधिकतम O(log n) पुनः अनुरेखण स्तर (O(1) औसतन) मार्ग पर पुनःजा रहा है, जिससे संचालन O(log n) समय में पूर्ण किया जा सके। संचालन और थोक संचालन संग्रह करेंएकल तत्व इंसर्ट, डिलीट और लुकअप विकल्प के अतिरिक्त, एवीएल ट्री पर अनेक समूह विकल्प को परिभाषित किया गया है: संघ (समूह सिद्धांत), प्रतिच्छेदन (समूह सिद्धांत) और अंतर समूह आदि I इन समूह फलन के आधार पर सम्मिलन या विलोपन पर तीव्र बल्क संचालन प्रस्तावित किया जा सकता है। ये समूह संचालन दो सहायक संचालन, स्प्लिट और जॉइन पर निर्भर करते हैं। नए संचालन के साथ, एवीएल ट्री का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है।[14] फलन दो एवीएल ट्री पर जुड़ें 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 ऊंचाई में वृद्धि से इसके पूर्वजों की ऊंचाई बढ़ सकती है, संभवतः उन नोड्स के एवीएल अपरिवर्तनीय को अमान्य कर दिया जा सकता है। इसे या तो दोगुने घुमाव के साथ ठीक किया जा सकता है, यदि मूल पर अमान्य है या यदि ट्री में उच्चतर अमान्य है तो एकल बाएं घुमाव के साथ, दोनों ही विषयों में किसी भी पूर्वज नोड्स के लिए ऊंचाई को बहाल किया जा सकता है। इसलिए जॉइन के लिए अधिकतम दो घुमावों की आवश्यकता होगी। इस फलन की लागत दो इनपुट ट्री के मध्य की ऊंचाई का अंतर है।
एवीएल ट्री को दो छोटे ट्री में विभाजित करना, जो कुंजी k से छोटे हों, और वे कुंजी k से बड़े हैं, पूर्व मार्ग से k एवीएल में हैं। इस प्रविष्टि के पश्चात्, सभी मान इससे कम होंगे k पथ के बायीं ओर मिलेगा, और सभी मान इससे बड़े होंगे k दाहिनी ओर मिलेगा I जॉइन प्रस्तावित करने से, बायीं ओर के सभी अर्धट्री को नीचे से ऊपर की ओर मध्यवर्ती नोड्स के रूप में पथ पर कुंजियों का अर्धयोग करके बाएँ ट्री बनाने के लिए विलय किया जाता है, और दायाँ भाग असममित होता है। विभाजित O(log n), ट्री की ऊंचाई का क्रम की लागत है I
|