WAVL ट्री: Difference between revisions

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

अलग-अलग बाइनरी सर्च ट्री में डालने/हटाने और संतुलन कला विधि  के लिए अलग-अलग कला विधि  होते हैं, जिससे व्यवस्थित अध्ययन करना मुश्किल हो जाता है। लेखक {{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}} बिन्दु  पर मान से बड़ा है। जब एक बिन्दु  जिसका मान बराबर हो {{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}} मिल गया है। यदि इसके बजाय, खोज किसी बाहरी बिन्दु  पर रुक जाती है, तो वह स्थिति कहाँ है {{mvar|k}} डाला जाएगा (यदि डाला गया हो) मिल गया है।<ref name="gt-search"/>

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

एक बिन्दु  के बीच - प्रारंभ में नया डाला गया बिन्दु  - और उसके

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

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

पैरेंट और बिन्दु  1 है, संतुलन बहाल हो गया है। अन्यथा, यदि

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

नए बिन्दु  के रूप में पुराने पैरेंट के साथ पुनर्संतुलन।

अंत में, बिन्दु  और सिबलिंग के लिए 0 और 2 के पद -अंतर के साथ, एक या

संतुलन बहाल कर सकता है. बिन्दु  का बीच वाला बच्चा कुंजी वाला होता है

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

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

चाइल्ड  को ऊपर और बिन्दु  को नीचे ले जाने के लिए घुमाएँ, फिर दोबारा घुमाएँ

चाइल्ड  को ऊपर और माता-पिता को नीचे ले जाएँ। चाइल्ड  को प्रमोट करो, डिमोट करो

बिन्दु  और पैरेंट, और संतुलन बहाल हो जाता है।

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

डब्ल्यूएवीएल ट्री से आंतरिक बिन्दु  को हटाना सामान्य से शुरू होता है

बाइनरी सर्च ट्री#विलोपन। संख्या वाले आंतरिक बिन्दु  के लिए

बिन्दु  को उसके उत्तराधिकारी के साथ बदलना, और फिर बिन्दु  को हटाना

बाहरी बिन्दु  . किसी बाहरी चाइल्ड  के साथ आंतरिक बिन्दु  को हटाने के लिए,

बिन्दु  को दूसरे चाइल्ड  के साथ बदलें।

एक बिन्दु  के बीच - प्रारंभ में, वह बिन्दु  जिसने हटाए गए बिन्दु  को प्रतिस्थापित किया -

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

बिन्दु  पर रूट छोटा हो गया है। यदि माता-पिता के पास अब दो बाहरी हैं

बच्चों, आंतरिक-बिन्दु  संपत्ति का उल्लंघन होता है क्योंकि माता-पिता

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

यदि बिन्दु  में कोई पेरेंट नहीं है, तो संतुलन बहाल हो जाता है। यदि

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

इसके प्रत्येक चाइल्ड  - और बूढ़े माता-पिता के साथ पुनर्संतुलन जारी रखें

नया बिन्दु  . अन्यथा, यदि भाई-बहन के दो चाइल्ड  हैं

भाई-बहन और नए बिन्दु  के रूप में पुराने माता-पिता के साथ पुनर्संतुलन जारी रखें।

अंत में, बिन्दु  और सिबलिंग के लिए 3 और 1 के पद -अंतर के साथ, और

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

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

किसी बाहरी चाइल्ड  के साथ एक बिन्दु  खोजने के लिए नीचे की ओर खोजें, को हटा दें

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

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

डब्ल्यूएवीएल ट्री में प्रत्येक खोज, सम्मिलन या विलोपन में ट्री में एक ही पथ का अनुसरण करना और पथ में प्रत्येक बिन्दु  के लिए निरंतर चरणों का पालन करना शामिल है। एक डब्ल्यूएवीएल ट्री  में {{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'')}}.

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

प्रत्येक एवीएल ट्री के बिन्दु  ्स को इस तरह से पद  दी जा सकती है कि वह डब्ल्यूएवीएल ट्री बन जाए। और प्रत्येक डब्ल्यूएवीएल ट्री  के बिन्दु  ्स लाल और काले रंग के हो सकते हैं (और इसकी पद ों को फिर से निर्दिष्ट किया जा सकता है) जिससे यह एक लाल-काले ट्री  में बदल जाता है। हालाँकि, कुछ डब्ल्यूएवीएल ट्री  इस तरह से एवीएल ट्री  से नहीं आते हैं और कुछ लाल-काले ट्री  इस तरह से डब्ल्यूएवीएल ट्री  से नहीं आते हैं।