WAVL ट्री: Difference between revisions

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

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

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

कुल मिलाकर, विलोपन में एक सम्मिलित होता है किसी बाहरी चाइल्ड के साथ एक बिन्दु खोजने के लिए नीचे की ओर खोजें, को हटा दें नए बिन्दु की एक स्थिर संख्या, पद परिवर्तन की एक लघुगणकीय संख्या,और ट्री के घूमने की एक स्थिर संख्या रहने दे।

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

   [[File:FibonacciTreeWRanks.png|thumb|पदो के साथ फाइबोनैचि ट्री ]] [[File:Fibonacci Tree after Delete.png|thumb|हटाने के बाद पद  के साथ फाइबोनैचि ट्री ]]

डब्ल्यूएवीएल ट्री में प्रत्येक खोज, सम्मिलन या विलोपन में ट्री में एक ही पथ का अनुसरण करना और पथ में प्रत्येक बिन्दु  के लिए निरंतर चरणों का पालन करना सम्मिलित  है। एक डब्ल्यूएवीएल ट्री  में {{mvar|n}} वस्तु  जिनमें केवल सम्मिलन हुआ है, अधिकतम पथ लंबाई है <math>\log_{\varphi} n\approx 1.44\log_2 n</math>. यदि सम्मिलन और विलोपन दोनों हो सकते हैं, तो अधिकतम पथ लंबाई है <math>2\log_2 n</math>. इसलिए, किसी भी मामले में, डब्ल्यूएवीएल ट्री में प्रत्येक खोज, सम्मिलन या विलोपन के लिए सबसे खराब स्थिति का समय {{mvar|n}} डेटा वस्तु  है {{math|''O''(log ''n'')}}.