WAVL ट्री: Difference between revisions

[[कंप्यूटर विज्ञान]] में, '''डब्ल्यूएवीएल (WAVL) ट्री''' या कमजोर एवीएल ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष|स्व-संतुलन द्विआधारी विवृत्त ट्री]] है। डब्ल्यूएवीएल ट्री का नाम एवीएल ट्री  के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज ट्री है, और यह एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित है, जो सभी पद संतुलित ट्री के एक सामान्य ढांचे में आते हैं। अन्य संतुलित बाइनरी खोज ट्री की तरह, डब्ल्यूएवीएल ट्री प्रति संचालन {{math|''O''(log ''n'')}} समय में सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं। <ref name="hst15"/>

== पद संतुलित ट्रीज की रूपरेखा ==

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

पद बाइनरी ट्री एक बाइनरी ट्री है जहां प्रत्येक बिन्दु  x एक पद  r(x) से जुड़ा होता है। परंपरा के अनुसार, खाली बिन्दु  की पद  -1 होती है। एक बिन्दु  x के लिए जो रूट नहीं है, पद अंतर है <math>r(p(x))-r(x)</math>, और यदि पद अंतर i है तो ऐसे बिन्दु को आई-चाइल्ड कहा जाता है। एक बिन्दु <math>i,j</math> प्रकार का होता है। यदि इसके बाएं चाइल्ड और दाएं चाइल्ड की पद का अंतर i और j है।

इसके साथ, हम अतिरिक्त नियम परिभाषित कर सकते हैं, जो विभिन्न ट्री से मेल खाते हैं:

* एवीएल नियम, जो एवीएल ट्री से मेल खाता है: प्रत्येक बिन्दु प्रकार 1,1 या 1,2 का है।

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

* लाल काला नियम, जो लाल-काले ट्री से मेल खाता है: सभी पद अंतर 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-बिन्दु सही है.

कमज़ोर एवीएल ट्री कमज़ोर एवीएल नियम द्वारा परिभाषित किया गया है:

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

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

सामान्यतः बाइनरी सर्च ट्री की तरह, डब्ल्यूएवीएल ट्री में दो प्रकार के [[नोड (कंप्यूटर विज्ञान)|बिन्दु]] का संग्रह होता है: आंतरिक बिन्दु और बाहरी बिन्दु एक आंतरिक बिन्दु एक डेटा वस्तु संग्रहीत करता है, और अपने माता-पिता से जुड़ा होता है और ट्री में ठीक दो बच्चों, बाएं चाइल्ड और दाएं चाइल्ड से जुड़ा होता है। एक बाहरी बिन्दु में कोई डेटा नहीं होता है, और उसका लिंक केवल ट्री में उसके मूल बिन्दु से होता है। इन बिन्दु  को एक बाइनरी ट्री बनाने के लिए व्यवस्थित किया जाता है, ताकि किसी भी आंतरिक बिन्दु के लिए {{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>डब्ल्यूएवीएल ट्री को अन्य प्रकार के बाइनरी सर्च ट्री से जो अलग करता है, वह है इसका पद  का उपयोग। ये प्रत्येक बिन्दु से जुड़े नंबर हैं, जो बिन्दु से उसके सबसे दूर के पत्ते के वंशज तक की दूरी का अनुमान प्रदान करते हैं। एवीएल ट्री के विपरीत, जहां पद को बिन्दु की ऊंचाई के समान परिभाषित किया जाता है, डब्ल्यूएवीएल ट्री  में पद  हमेशा ऊंचाई के बराबर नहीं होती है। बिन्दु  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}} की खोज करना किसी भी संतुलित द्विआधार सर्च ट्री डेटा संरचना की तरह होता है। पहले ट्री की रूट पर प्रारंभ करें, और फिर मूल से रूट तक के पथ पर प्रत्येक बिन्दु पर संग्रहीत डेटा वस्तु के साथ {{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>जब किसी बिन्दु के मान के बराबर कीमत के साथ एक बिन्दु तक पहुंचा जाता है या एक बाह्य बिन्दु  तक पहुंचा जाता है, खोज समाप्त हो जाती है।<ref name="gt-search"/>यदि खोज किसी आंतरिक बिन्दु पर रुकती है, तो कुंजी {{mvar|k}} मिल गई है। यदि विपरीत होता है, तो खोज किसी बाह्य बिन्दु पर रुकती है, तो {{mvar|k}} को किस स्थान पर सम्मिलित किया जाएगा, वह स्थान मिल गया है।

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

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

अंत में, बिन्दु और सिबलिंग के लिए 0 और 2 के पद -अंतर के साथ, एक या पद -अंतर से संबंधित समायोजन के साथ, दो ट्री  घूर्णन,संतुलन बहाल कर सकता है. बिन्दु का बीच वाला बच्चा कुंजी वाला होता है बिन्दु और पैरेंट की कुंजियों के बीच यदि उसके लिए पद -अंतर है

चाइल्ड और बिन्दु 2 है, बिन्दु को ट्री और पेरेंट में ऊपर ले जाने के लिए घुमाएँ नीचे, फिर माता-पिता को पदावनत करें - समायोजित करके इसकी पद  कम करें इसके चारों ओर पद -अंतर - और संतुलन बहाल हो जाता है। अन्यथा,चाइल्ड को ऊपर और बिन्दु को नीचे ले जाने के लिए घुमाएँ, फिर दोबारा घुमाएँ चाइल्ड को ऊपर और माता-पिता को नीचे ले जाएँ। चाइल्ड को प्रमोट करो, डिमोट करो बिन्दु और पैरेंट, और संतुलन बहाल हो जाता है।

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

डब्ल्यूएवीएल ट्री से एक आंतरिक बिन्दु  को हटाने की प्रक्रिया साधारण बाइनरी सर्च ट्री हटाने से प्रारंभ होती है। एक आंतरिक बिन्दु  के लिए जो किसी बाह्य बच्चे के बिना होता है, इसका अर्थ है कि उसे ट्री में उसके उत्तरजीवी का पता लगाना होगा, बिन्दु  को उसके उत्तरजीवी के साथ बदलना होगा, और फिर बिन्दु को नए ट्री स्थान से हटाना होगा, जहां उसका बाएं बच्चा आवश्यकतानुसार एक बाह्य बिन्दु होगा। एक आंतरिक बिन्दु को हटाने के लिए जो एक बाह्य बच्चे के साथ होता है, उसे दूसरे बच्चे से प्रतिस्थापित करें।

पद -अंतर संतुलनाधीन चरण पाठकों में सोचना प्रारंभ करता है जो बिन्दु  के बीच पद  -अंतर होता है - प्रारंभिक रूप में, हटाए गए बिन्दु  को प्रतिस्थापित करने वाला बिन्दु  । यदि कोई माता-पिता नहीं है, तो संतुलन संशोधित होता है। हटाने की प्रारंभिक तिथि से पहले, माता-पिता और बिन्दु  के बीच पद -अंतर 1 या 2 था, लेकिन इस अंतर को 1 के साथ बढ़ा दिया गया है क्योंकि बिन्दु के द्वारा जड़ी उपट्री  को छोटा कर दिया गया है। यदि माता-पिता के पास अब दो बाह्य बच्चे हैं, तो आंतरिक-बिन्दु संपत्ति को उल्लंघन किया जाता है क्योंकि माता-पिता का पद   2 होता है। माता-पिता को अवमानित किया जाना चाहिए, और संतुलनाधीनीकरण जारी रखना चाहिए जहां माता-पिता उन्हीं का बिन्दु है जो अत्यंत छोटे उपट्री     के मूल है।

यदि बिन्दु का माता-पिता नहीं है, तो संतुलन संशोधित हो जाता है। यदि बिन्दु और माता-पिता के बीच पद -अंतर 1 से 2 तक बढ़ गया है, तो संतुलन संशोधित हो जाता है। अन्यथा, यदि सहोदर, माता-पिता का दूसरा बच्चा, माता-पिता के साथ पद -अंतर 2 है, तो माता-पिता को अवमानित करें - उसका पद कम करें, अर्थात उसके और प्रत्येक बच्चे के बीच पद -अंतर को कम करें - और पुराने माता-पिता को नए बिन्दु के रूप में संतुलनाधीनीकरण जारी रखें। अन्यथा, यदि सहोदर के दोनों बच्चों के बीच पद -अंतर 2 हैं, तो माता-पिता और सहोदर को अवमानित करें और पुराने माता-पिता को नए बिन्दु के रूप में संतुलनाधीनीकरण जारी रखें।