WAVL ट्री: Difference between revisions

[[कंप्यूटर विज्ञान]] में, WAVL ट्री या कमजोर AVL ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष]] है। WAVL पेड़ों का नाम AVL पेड़ों के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज पेड़ है, और यह AVL पेड़ों और लाल-काले पेड़ों दोनों से निकटता से संबंधित है, जो सभी रैंक संतुलित पेड़ों के एक सामान्य ढांचे में आते हैं।

अन्य संतुलित बाइनरी खोज पेड़ों की तरह, WAVL पेड़ समय पर सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं {{math|''O''(log ''n'')}} प्रति ऑपरेशन.<ref name="gt">{{citation|contribution=4.4 Weak AVL Trees|pages=130–138|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015}}.</ref><ref name="hst15"/>

WAVL पेड़ों को AVL पेड़ों और लाल-काले पेड़ों दोनों के कुछ सर्वोत्तम गुणों को संयोजित करने के लिए डिज़ाइन किया गया है। लाल-काले पेड़ों की तुलना में एवीएल पेड़ों का एक फायदा यह है कि वे अधिक संतुलित होते हैं: उनकी अधिकतम ऊंचाई होती है <math>\log_{\varphi} n\approx 1.44\log_2 n</math> (एक पेड़ के लिए {{mvar|n}} डेटा आइटम, कहां <math>\varphi</math> [[सुनहरा अनुपात]] है), जबकि लाल-काले पेड़ों की अधिकतम ऊंचाई अधिक होती है, <math>2\log_2 n</math>. यदि एक WAVL ट्री केवल सम्मिलन का उपयोग करके, बिना हटाए बनाया जाता है, तो इसमें वही छोटी ऊँचाई होती है जो AVL ट्री में होती है। दूसरी ओर, लाल-काले पेड़ों को अपने पेड़ों के कम पुनर्गठन में एवीएल पेड़ों की तुलना में फायदा होता है। एवीएल पेड़ों में, प्रत्येक विलोपन के लिए पेड़ के घूर्णन संचालन की एक लघुगणकीय संख्या की आवश्यकता हो सकती है, जबकि लाल-काले पेड़ों में सरल विलोपन संचालन होते हैं जो केवल पेड़ के घूर्णन की एक स्थिर संख्या का उपयोग करते हैं। WAVL पेड़, लाल-काले पेड़ों की तरह, केवल पेड़ के घूर्णन की एक स्थिर संख्या का उपयोग करते हैं, और स्थिरांक लाल-काले पेड़ों की तुलना में भी बेहतर है।<ref name="gt"/><ref name="hst15"/>

WAVL वृक्षों की शुरुआत किसके द्वारा की गई थी? {{harvtxt|Haeupler|Sen|Tarjan|2015}}. उन्हीं लेखकों ने एवीएल पेड़ों, डब्ल्यूएवीएल पेड़ों और लाल-काले पेड़ों के बारे में एक सामान्य दृष्टिकोण भी प्रदान किया, क्योंकि ये सभी एक प्रकार के रैंक-संतुलित पेड़ हैं।<ref name="hst15">{{citation

  | year = 2015}}.</ref>

अलग-अलग बाइनरी सर्च ट्री में डालने/हटाने और संतुलन एल्गोरिदम के लिए अलग-अलग एल्गोरिदम होते हैं, जिससे व्यवस्थित अध्ययन करना मुश्किल हो जाता है। के लेखक {{harvtxt|Haeupler|Sen|Tarjan|2015}} रैंक बाइनरी ट्री को परिभाषित करके बाइनरी सर्च ट्री के अध्ययन को एकीकृत करने के लिए रैंक संतुलित ट्री फ्रेमवर्क का परिचय दें, और प्रत्येक बाइनरी सर्च ट्री रैंक फ़ंक्शन पर लागू विशिष्ट बाधाओं का पालन करता है। ध्यान दें कि फ़्रेमवर्क उन एल्गोरिदम को निर्दिष्ट नहीं करता है जिनमें ये पेड़ लागू किए जाते हैं।

 

 

* AVL नियम, जो AVL ट्री से मेल खाता है: प्रत्येक नोड प्रकार 1,1 या 1,2 का है।

* लाल काला नियम, जो लाल-काले पेड़ से मेल खाता है: सभी रैंक अंतर 0 या 1 हैं, और 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है। ध्यान दें कि लाल-काला नियम 0,0 प्रकार के नोड की अनुमति देकर 2-3 नियम को सामान्य बनाता है।

* दाएँ-झुकाव वाला दो-तीन नियम, जो दाएँ झुकाव वाले द्विअर्थी 2-3 पेड़ से मेल खाता है: प्रत्येक नोड 1,1 या 0,1 है, 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और कोई 0-बच्चा नहीं है शेष है।

* वाम-झुकाव वाला दो-तीन नियम, जो बायीं ओर झुके हुए द्विअर्थी 2-3 पेड़ से मेल खाता है: प्रत्येक नोड 1,1 या 0,1 है, 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और कोई 0-बच्चा नहीं है सही है।

* दाएं-झुकाव वाला लाल-काला नियम, जो रेफ्ट-झुकाव वाले लाल-काले पेड़ से मेल खाता है: 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और 0,1-नोड का कोई 0-बच्चा नहीं बचा है।

* वाम-झुकाव वाले लाल-काले नियम, जो वाम-झुकाव वाले लाल-काले पेड़ से मेल खाता है: सभी रैंक अंतर 0 या 1 हैं, 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और 0 का कोई 0-बच्चा नहीं है, 1-नोड सही है.

कमज़ोर AVL वृक्ष को कमज़ोर AVL नियम द्वारा परिभाषित किया गया है:

* कमजोर एवीएल नियम: सभी रैंक अंतर 1 या 2 हैं, और सभी लीफ नोड्स की रैंक 0 है।

ध्यान दें कि कमजोर AVL ट्री 2,2 प्रकार के नोड की अनुमति देकर AVL ट्री को सामान्यीकृत करता है। एक साधारण प्रमाण से पता चलता है कि एक कमजोर एवीएल पेड़ को इस तरह से रंगा जा सकता है जो लाल-काले पेड़ का प्रतिनिधित्व करता है। तो एक अर्थ में, कमजोर AVL वृक्ष AVL वृक्ष और लाल-काले वृक्ष के गुणों को जोड़ता है।

आमतौर पर बाइनरी सर्च ट्री की तरह, WAVL ट्री में दो प्रकार के [[नोड (कंप्यूटर विज्ञान)]] का संग्रह होता है: आंतरिक नोड्स और बाहरी नोड्स। एक आंतरिक नोड एक डेटा आइटम संग्रहीत करता है, और अपने माता-पिता से जुड़ा होता है (निर्दिष्ट रूट नोड को छोड़कर जिसका कोई माता-पिता नहीं है) और पेड़ में ठीक दो बच्चों, बाएं बच्चे और दाएं बच्चे से जुड़ा होता है। एक बाहरी नोड में कोई डेटा नहीं होता है, और उसका लिंक केवल पेड़ में उसके मूल नोड से होता है। इन नोड्स को एक बाइनरी ट्री बनाने के लिए व्यवस्थित किया जाता है, ताकि किसी भी आंतरिक नोड के लिए {{mvar|x}} बाएँ और दाएँ बच्चों के माता-पिता {{mvar|x}} हैं {{mvar|x}} अपने आप। बाहरी गांठें पेड़ की पत्तियाँ बनाती हैं।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, Section 2.3 Trees, pp. 68–83.</ref> डेटा आइटम को ट्री में इस तरह व्यवस्थित किया जाता है कि ट्री का एक [[इनऑर्डर ट्रैवर्सल]] डेटा आइटम को क्रमबद्ध क्रम में सूचीबद्ध करता है।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, Chapter 3 Binary Search Trees, pp. 89–114.</ref>

WAVL ट्री को अन्य प्रकार के बाइनरी सर्च ट्री से जो अलग करता है, वह है इसका रैंक का उपयोग। ये प्रत्येक नोड से जुड़े नंबर हैं, जो नोड से उसके सबसे दूर के पत्ते के वंशज तक की दूरी का अनुमान प्रदान करते हैं।

एवीएल पेड़ों के विपरीत, जहां रैंक को नोड्स की ऊंचाई के समान परिभाषित किया जाता है, डब्ल्यूएवीएल पेड़ों में रैंक हमेशा ऊंचाई के बराबर नहीं होती है। नोड x के रैंक अंतर को x के मूल रैंक और x के रैंक के बीच अंतर के रूप में परिभाषित किया गया है। रैंकों को निम्नलिखित गुणों का पालन करना आवश्यक है:<ref name="gt"/><ref name="hst15"/>*बाहरी-नोड संपत्ति: प्रत्येक बाहरी नोड की रैंक होती है {{math|0}}<ref>In this we follow {{harvtxt|Goodrich|Tamassia|2015}}. In the version described by {{harvtxt|Haeupler|Sen|Tarjan|2015}}, the external nodes have rank &minus;1. This variation makes very little difference in the operations of WAVL trees, but it causes some minor changes to the formula for converting WAVL trees to red–black trees.</ref>

*रैंक-अंतर संपत्ति: यदि एक गैर-रूट नोड में रैंक है {{mvar|r}}, तो उसके माता-पिता का पद या तो होना चाहिए {{math|''r'' + 1}} या {{math|''r'' + 2}}. दूसरे शब्दों में, किसी भी गैर-रूट नोड के लिए रैंक अंतर 1 या 2 है।<ref name="gt" />*आंतरिक-नोड संपत्ति: दो बाहरी बच्चों वाले एक आंतरिक नोड की रैंक बिल्कुल 1 होनी चाहिए।

कुंजी की तलाश की जा रही है {{mvar|k}} WAVL ट्री में किसी भी संतुलित बाइनरी सर्च ट्री डेटा संरचना के समान ही है। कोई पेड़ की जड़ से शुरुआत करता है और फिर बार-बार तुलना करता है {{mvar|k}} रूट से पथ पर प्रत्येक नोड पर संग्रहीत डेटा आइटम के साथ, नोड के बाएं बच्चे के पथ का अनुसरण करते हुए {{mvar|k}} नोड पर मान से छोटा है या इसके बजाय सही बच्चे के पथ का अनुसरण कर रहा है {{mvar|k}} नोड पर मान से बड़ा है। जब एक नोड जिसका मान बराबर हो {{mvar|k}} पहुँच जाता है, या कोई बाहरी नोड पहुँच जाता है, खोज रुक जाती है।<ref name="gt-search">{{harvtxt|Goodrich|Tamassia|2015}}, Section 3.1.2 Searching in a Binary Search Tree, pp. 95–96.</ref>

कुंजी के साथ एक आंतरिक नोड सम्मिलित करना {{mvar|k}} WAVL ट्री में खोज की आवश्यकता होती है {{mvar|k}} पेड़ में, एक बाहरी नोड पर समाप्त होता है, फिर दो बाहरी बच्चों के साथ नए आंतरिक नोड के साथ उस बाहरी नोड का प्रतिस्थापन होता है, और अंत में पेड़ का पुनर्संतुलन होता है। पुनर्संतुलन चरण या तो ऊपर से नीचे या नीचे से ऊपर किया जा सकता है,<ref name="hst15"/>लेकिन पुनर्संतुलन का निचला-ऊपर संस्करण वह है जो एवीएल पेड़ों से सबसे अधिक मेल खाता है।<ref name="gt"/><ref name="hst15"/>

रैंक-अंतर पर विचार करके नीचे-ऊपर पुनर्संतुलन शुरू होता है

प्रविष्टि शुरू हुई, पैरेंट और नोड के बीच रैंक-अंतर 1 या था

2, लेकिन उपवृक्ष के कारण वह अंतर 1 से कम हो गया है

नोड पर जड़ें लंबी हो गई हैं। यदि नये रैंक-अंतर के बीच

भाई-बहन, माता-पिता की दूसरी संतान, के साथ रैंक-अंतर 1 है

माता-पिता, माता-पिता को बढ़ावा दें - वृद्धि करके इसकी रैंक बढ़ाएं

इसके और इसके प्रत्येक बच्चे के बीच रैंक-अंतर - और जारी है

अंत में, नोड और सिबलिंग के लिए 0 और 2 के रैंक-अंतर के साथ, एक या

रैंक-अंतर से संबंधित समायोजन के साथ, दो वृक्ष घूर्णन,

नोड और पैरेंट की कुंजियों के बीच। यदि उसके लिए रैंक-अंतर है

चाइल्ड और नोड 2 है, नोड को पेड़ और पेरेंट में ऊपर ले जाने के लिए घुमाएँ

नीचे, फिर माता-पिता को पदावनत करें - समायोजित करके इसकी रैंक कम करें

इसके चारों ओर रैंक-अंतर - और संतुलन बहाल हो जाता है। अन्यथा,

इस प्रकार, कुल मिलाकर, सम्मिलन प्रक्रिया में एक खोज, नए नोड्स की एक निरंतर संख्या का निर्माण, रैंक परिवर्तनों की एक लघुगणकीय संख्या और पेड़ के घूर्णन की एक निरंतर संख्या शामिल होती है।<ref name="gt"/><ref name="hst15"/>

WAVL ट्री से आंतरिक नोड को हटाना सामान्य से शुरू होता है

बाहरी संतान, इसका मतलब है पेड़ में अपना उत्तराधिकारी ढूंढना,

अपने नए वृक्ष की स्थिति से, जहां उसका बायां बच्चा अनिवार्य रूप से एक है

रैंक-अंतर पर विचार करके नीचे-ऊपर पुनर्संतुलन शुरू होता है

विलोपन शुरू हुआ, पैरेंट और नोड के बीच रैंक-अंतर 1 या था

2, लेकिन उपवृक्ष के कारण वह अंतर 1 से बढ़ गया है

रैंक 2 है। माता-पिता को पदावनत किया जाना चाहिए, और पुनर्संतुलन जारी रखा जाना चाहिए

पैरेंट के साथ नोड के रूप में जो कि बहुत छोटे उपवृक्ष की जड़ है।

नोड और पैरेंट के बीच रैंक-अंतर 1 से बढ़कर 2 हो गया है, संतुलन

माता-पिता के साथ रैंक-अंतर 2 है, माता-पिता को पदावनत करें -

इसके बीच के रैंक-अंतर को कम करके इसकी रैंक को कम करें

भाई-बहन के साथ 2 का रैंक-अंतर, माता-पिता को पदावनत करता है और

अंत में, नोड और सिबलिंग के लिए 3 और 1 के रैंक-अंतर के साथ, और

भाई-बहन के बच्चे का रैंक-अंतर 1, एक या दो पेड़ है

रैंक-अंतर से जुड़े समायोजन के साथ रोटेशन, कर सकते हैं

आंतरिक-नोड संपत्ति। अन्यथा, बीच रैंक-अंतर के साथ

नए नोड्स की एक स्थिर संख्या, रैंक परिवर्तन की एक लघुगणकीय संख्या,

और पेड़ों के घूमने की एक स्थिर संख्या।[1][2]

एक डिलीट के परिणाम की तुलना करना सार्थक है जो एक AVL ट्री में कई स्तरों पर घुमाव का कारण बनता है और एक WAVL ट्री में किए गए रोटेशन और रैंक परिवर्तनों के साथ। दूसरी छवि में मान 12 वाले नोड को हटा दिया गया है, इसके बाद दाएं घुमाव और सभी बाहरी नोड्स को शून्य रैंक दिया गया है।