WAVL ट्री

कंप्यूटर विज्ञान में, डब्ल्यूएवीएल ट्री या कमजोर एवीएल ट्री एक स्व-संतुलन द्विआधारी विवृत्त ट्री है। डब्ल्यूएवीएल ट्री का नाम एवीएल ट्री के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज ट्री है, और यह एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित है, जो सभी पद संतुलित ट्री के एक सामान्य ढांचे में आते हैं। अन्य संतुलित बाइनरी खोज ट्री की तरह, डब्ल्यूएवीएल ट्री प्रति संचालन $O (log n)$ समय में सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं। ^[1]

डब्ल्यूएवीएल ट्री को एवीएल ट्री लाल-काले ट्री दोनों के कुछ सर्वोत्तम गुणों को संयोजित करने के लिए प्ररूपित किया गया है। लाल-काले ट्री की तुलना में एवीएल ट्री का एक लाभ यह है कि वे अधिक संतुलित होते हैं: उनकी अधिकतम ऊंचाई होती है $\log _{\varphi }n\approx 1.44\log _{2}n$ , जबकि लाल-काले ट्री की अधिकतम ऊंचाई $2\log _{2}n$ से अधिक होती है, यदि एक डब्ल्यूएवीएल ट्री केवल सम्मिलन का उपयोग करके, बिना हटाए बनाया जाता है, तो इसमें वही छोटी ऊँचाई होती है जो एवीएल ट्री में होती है। दूसरी ओर, लाल-काले ट्री को अपने ट्री के कम पुनर्गठन में एवीएल ट्री के सापेक्ष में लाभ होता है। एवीएल ट्री में, प्रत्येक विलोपन के लिए ट्री के घूर्णन संचालन की एक लघुगणकीय संख्या की आवश्यकता हो सकती है, जबकि लाल-काले ट्री में सरल विलोपन संचालन होते हैं जो केवल ट्री के घूर्णन की एक स्थिर संख्या का उपयोग करते हैं। डब्ल्यूएवीएल ट्री, लाल-काले ट्री की तरह, केवल ट्री के घूर्णन की एक स्थिर संख्या का उपयोग करते हैं, और स्थिरांक लाल-काले ट्री के सापेक्ष में भी उत्तम है।^[2]^[1]

^[1]डब्ल्यूएवीएल ट्री एवीएल ट्रीज को कहा जाता है जिन्हें ह्युप्लर, सेन & टारजन (2015). ने प्रस्तुत किया था। उन्ही लेखकों ने एवीएल ट्रीज, एवीएल ट्रीज और लाल-काले ट्रीज को पद -संतुलित ट्री के एक प्रकार के रूप में प्रदर्शित किया।

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

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

पद बाइनरी ट्री एक बाइनरी ट्री है जहां प्रत्येक नोड x एक पद r(x) से जुड़ा होता है। परंपरा के अनुसार, खाली नोड की पद -1 होती है। एक नोड x के लिए जो रूट नहीं है, पद अंतर है $r(p(x))-r(x)$ , और यदि पद अंतर i है तो ऐसे नोड को आई-चाइल्ड कहा जाता है। एक नोड प्रकार का होता है $i,j$ यदि इसके बाएं बच्चे और दाएं बच्चे की पद का अंतर 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 प्रकार के नोड की अनुमति देकर एवीएल ट्री को सामान्यीकृत करता है। एक साधारण प्रमाण से पता चलता है कि एक कमजोर एवीएल ट्री को इस तरह से रंगा जा सकता है जो लाल-काले ट्री का प्रतिनिधित्व करता है। तो एक अर्थ में, कमजोर एवीएल ट्री एवीएल ट्री और लाल-काले ट्री के गुणों को जोड़ता है।

परिभाषा

आमतौर पर बाइनरी सर्च ट्री की तरह, डब्ल्यूएवीएल ट्री में दो प्रकार के नोड (कंप्यूटर विज्ञान) का संग्रह होता है: आंतरिक नोड्स और बाहरी नोड्स। एक आंतरिक नोड एक डेटा आइटम संग्रहीत करता है, और अपने माता-पिता से जुड़ा होता है (निर्दिष्ट रूट नोड को छोड़कर जिसका कोई माता-पिता नहीं है) और ट्री में ठीक दो बच्चों, बाएं बच्चे और दाएं बच्चे से जुड़ा होता है। एक बाहरी नोड में कोई डेटा नहीं होता है, और उसका लिंक केवल ट्री में उसके मूल नोड से होता है। इन नोड्स को एक बाइनरी ट्री बनाने के लिए व्यवस्थित किया जाता है, ताकि किसी भी आंतरिक नोड के लिए $x$ बाएँ और दाएँ बच्चों के माता-पिता $x$ हैं $x$ अपने आप। बाहरी गांठें ट्री की पत्तियाँ बनाती हैं।^[3] डेटा आइटम को ट्री में इस तरह व्यवस्थित किया जाता है कि ट्री का एक इनऑर्डर ट्रैवर्सल डेटा आइटम को क्रमबद्ध क्रम में सूचीबद्ध करता है।^[4] डब्ल्यूएवीएल ट्री को अन्य प्रकार के बाइनरी सर्च ट्री से जो अलग करता है, वह है इसका पद का उपयोग। ये प्रत्येक नोड से जुड़े नंबर हैं, जो नोड से उसके सबसे दूर के पत्ते के वंशज तक की दूरी का अनुमान प्रदान करते हैं। एवीएल ट्री के विपरीत, जहां पद को नोड्स की ऊंचाई के समान परिभाषित किया जाता है, डब्ल्यूएवीएल ट्री में पद हमेशा ऊंचाई के बराबर नहीं होती है। नोड x के पद अंतर को x के मूल पद और x के पद के बीच अंतर के रूप में परिभाषित किया गया है। पद ों को निम्नलिखित गुणों का पालन करना आवश्यक है:^[2]^[1]*बाहरी-नोड संपत्ति: प्रत्येक बाहरी नोड की पद होती है $0$ ^[5]

पद -अंतर संपत्ति: यदि एक गैर-रूट नोड में पद है $r$ , तो उसके माता-पिता का पद या तो होना चाहिए $r + 1$ या $r + 2$ . दूसरे शब्दों में, किसी भी गैर-रूट नोड के लिए पद अंतर 1 या 2 है।^[2]*आंतरिक-नोड संपत्ति: दो बाहरी बच्चों वाले एक आंतरिक नोड की पद बिल्कुल 1 होनी चाहिए।

संचालन

खोज रहा हूँ

कुंजी की तलाश की जा रही है $k$ डब्ल्यूएवीएल ट्री में किसी भी संतुलित बाइनरी सर्च ट्री डेटा संरचना के समान ही है। कोई ट्री की जड़ से शुरुआत करता है और फिर बार-बार तुलना करता है $k$ रूट से पथ पर प्रत्येक नोड पर संग्रहीत डेटा आइटम के साथ, नोड के बाएं बच्चे के पथ का अनुसरण करते हुए $k$ नोड पर मान से छोटा है या इसके बजाय सही बच्चे के पथ का अनुसरण कर रहा है $k$ नोड पर मान से बड़ा है। जब एक नोड जिसका मान बराबर हो $k$ पहुँच जाता है, या कोई बाहरी नोड पहुँच जाता है, खोज रुक जाती है।^[6] यदि खोज किसी आंतरिक नोड पर रुकती है, तो कुंजी $k$ मिल गया है। यदि इसके बजाय, खोज किसी बाहरी नोड पर रुक जाती है, तो वह स्थिति कहाँ है $k$ डाला जाएगा (यदि डाला गया हो) मिल गया है।^[6]

सम्मिलन

कुंजी के साथ एक आंतरिक नोड सम्मिलित करना $k$ डब्ल्यूएवीएल ट्री में खोज की आवश्यकता होती है $k$ ट्री में, एक बाहरी नोड पर समाप्त होता है, फिर दो बाहरी बच्चों के साथ नए आंतरिक नोड के साथ उस बाहरी नोड का प्रतिस्थापन होता है, और अंत में ट्री का पुनर्संतुलन होता है। पुनर्संतुलन चरण या तो ऊपर से नीचे या नीचे से ऊपर किया जा सकता है,^[1]लेकिन पुनर्संतुलन का निचला-ऊपर संस्करण वह है जो एवीएल ट्री से सबसे अधिक मेल खाता है।^[2]^[1]

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

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

इस प्रकार, कुल मिलाकर, सम्मिलन प्रक्रिया में एक खोज, नए नोड्स की एक निरंतर संख्या का निर्माण, पद परिवर्तनों की एक लघुगणकीय संख्या और ट्री के घूर्णन की एक निरंतर संख्या शामिल होती है।^[2]^[1]

विलोपन

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

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

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

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

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

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

पद ों के साथ फाइबोनैचि ट्री

हटाने के बाद पद के साथ फाइबोनैचि ट्री

कम्प्यूटेशनल जटिलता

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

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

संबंधित संरचनाएं

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

एवीएल ट्री

एवीएल ट्री एक प्रकार का संतुलित बाइनरी सर्च ट्री है जिसमें प्रत्येक आंतरिक नोड के दो बच्चों की ऊंचाई अधिकतम एक से भिन्न होनी चाहिए।^[7] किसी बाहरी नोड की ऊंचाई शून्य है, और किसी भी आंतरिक नोड की ऊंचाई हमेशा उसके दो बच्चों की ऊंचाई से एक प्लस अधिक होती है। इस प्रकार, एवीएल ट्री की ऊंचाई फ़ंक्शन डब्ल्यूएवीएल ट्री की बाधाओं का पालन करती है, और हम प्रत्येक नोड की ऊंचाई को उसके पद के रूप में उपयोग करके किसी भी एवीएल ट्री को डब्ल्यूएवीएल ट्री में परिवर्तित कर सकते हैं।^[2]^[1]

एवीएल ट्री और डब्ल्यूएवीएल ट्री के बीच मुख्य अंतर तब उत्पन्न होता है जब एक नोड में समान पद या ऊंचाई वाले दो बच्चे होते हैं। एवीएल ट्री में, यदि एक नोड $x$ के एक ही कद के दो बच्चे हैं $h$ एक दूसरे के रूप में, तो की ऊंचाई $x$ बिलकुल होना चाहिए $h + 1$ . इसके विपरीत, डब्ल्यूएवीएल ट्री में, यदि एक node $x$ के एक ही पद के दो बच्चे हैं $r$ एक दूसरे के रूप में, फिर की पद $x$ या तो किया जा सकता है $r + 1$ या $r + 2$ . ऐसा इसलिए है क्योंकि डब्ल्यूएवीएल ट्री में पद पूरी तरह से ऊंचाई के बराबर नहीं है। पद ों में इस अधिक लचीलेपन से संरचनाओं में भी अधिक लचीलापन आता है: कुछ डब्ल्यूएवीएल ट्री को उनके पद ों को संशोधित करके भी एवीएल ट्री में नहीं बनाया जा सकता है, क्योंकि उनमें ऐसे नोड शामिल होते हैं जिनके बच्चों की ऊंचाई एक से अधिक भिन्न होती है।^[1]हालाँकि, हम कह सकते हैं कि सभी एवीएल ट्री डब्ल्यूएवीएल ट्री हैं। एवीएल ट्री बिना किसी प्रकार के नोड वाले डब्ल्यूएवीएल ट्री हैं जिनके दोनों बच्चों की पद में अंतर 2 है।^[2]

यदि एक डब्ल्यूएवीएल ट्री केवल सम्मिलन संचालन का उपयोग करके बनाया गया है, तो इसकी संरचना समान सम्मिलन अनुक्रम द्वारा बनाए गए एवीएल ट्री की संरचना के समान होगी, और इसकी पद संबंधित एवीएल ट्री की पद के समान होगी। केवल विलोपन कार्यों के माध्यम से ही एक डब्ल्यूएवीएल ट्री एक एवीएल ट्री से भिन्न हो सकता है। विशेष रूप से इसका तात्पर्य यह है कि केवल सम्मिलन के माध्यम से बनाए गए डब्ल्यूएवीएल ट्री की ऊंचाई अधिकतम होती है $\log _{\varphi }n\approx 1.44\log _{2}n$ .^[1]

लाल-काले ट्री

लाल-काला ट्री एक संतुलित बाइनरी खोज ट्री है जिसमें प्रत्येक नोड का एक रंग (लाल या काला) होता है, जो निम्नलिखित गुणों को संतुष्ट करता है:

बाहरी नोड्स काले हैं.
यदि कोई आंतरिक नोड लाल है, तो उसके दोनों बच्चे काले हैं।
रूट से बाहरी नोड तक के सभी पथों में समान संख्या में ब्लैक नोड होते हैं।

लाल-काले ट्री को समान रूप से नोड्स पर संग्रहीत पद ों की एक प्रणाली के संदर्भ में परिभाषित किया जा सकता है, जो निम्नलिखित आवश्यकताओं को पूरा करता है (डब्ल्यूएवीएल ट्री में पद ों की आवश्यकताओं से भिन्न):

बाहरी नोड की पद हमेशा 0 होती है और उसके मूल नोड की पद हमेशा 1 होती है।
किसी भी गैर-रूट नोड की पद या तो उसके मूल नोड की पद या उसके मूल नोड की पद माइनस 1 के बराबर होती है।
किसी भी जड़-पत्ती पथ पर लगातार दो किनारों में पद अंतर 0 नहीं होता है।

रंग-आधारित और पद -आधारित परिभाषाओं के बीच समानता को एक दिशा में, एक नोड को काले रंग से देखा जा सकता है यदि उसके मूल की पद अधिक है और लाल रंग से यदि उसके मूल की पद समान है। दूसरी दिशा में, किसी बाहरी नोड के किसी भी पथ पर काले नोड की पद को काले नोड की संख्या के बराबर बनाकर और लाल नोड की पद को उसके मूल नोड के बराबर बनाकर रंगों को पद में परिवर्तित किया जा सकता है।^[8] डब्ल्यूएवीएल ट्री में नोड्स की पद को प्रत्येक पद को दो से विभाजित करके और निकटतम पूर्णांक तक पूर्णांकित करके, लाल-काले ट्री की आवश्यकताओं का पालन करते हुए, नोड्स की पद की एक प्रणाली में परिवर्तित किया जा सकता है।^[9] इस रूपांतरण के कारण, प्रत्येक डब्ल्यूएवीएल ट्री के लिए समान संरचना वाला एक वैध लाल-काला ट्री मौजूद होता है। क्योंकि लाल-काले ट्री की ऊंचाई सबसे अधिक होती है $2\log _{2}n$ , डब्ल्यूएवीएल ट्री के लिए भी यही सच है।^[2]^[1]हालाँकि, ऐसे लाल-काले ट्री मौजूद हैं जिन्हें वैध डब्ल्यूएवीएल ट्री पद फ़ंक्शन नहीं दिया जा सकता है।^[1]

इस तथ्य के बावजूद कि, अपने ट्री संरचनाओं के संदर्भ में, डब्ल्यूएवीएल ट्री लाल-काले ट्री के विशेष मामले हैं, उनके अद्यतन संचालन अलग-अलग हैं। डब्ल्यूएवीएल ट्री अपडेट ऑपरेशन में उपयोग किए जाने वाले ट्री रोटेशन ऐसे परिवर्तन कर सकते हैं जिन्हें लाल-काले ट्री में अनुमति नहीं दी जाएगी, क्योंकि वे वास्तव में केवल एक ही रंग में परिवर्तन करने के बजाय लाल-काले ट्री के बड़े उप-ट्री ों का रंग बदलने का कारण बनेंगे। ट्री में पथ.^[1]यह डब्ल्यूएवीएल ट्री को लाल-काले ट्री की तुलना में, सबसे खराब स्थिति में, प्रति विलोपन कम ट्री रोटेशन करने की अनुमति देता है।^[2]^[1]

संदर्भ

↑ ^1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2015), "Rank-balanced trees" (PDF), ACM Transactions on Algorithms, 11 (4): Art. 30, 26, doi:10.1145/2689412, MR 3361215.
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 ^2.8 Goodrich, Michael T.; Tamassia, Roberto (2015), "4.4 Weak AVL Trees", Algorithm Design and Applications, Wiley, pp. 130–138.
↑ Goodrich & Tamassia (2015), Section 2.3 Trees, pp. 68–83.
↑ Goodrich & Tamassia (2015), Chapter 3 Binary Search Trees, pp. 89–114.
↑ In this we follow Goodrich & Tamassia (2015). In the version described by Haeupler, Sen & Tarjan (2015), the external nodes have rank −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.
↑ ^6.0 ^6.1 Goodrich & Tamassia (2015), Section 3.1.2 Searching in a Binary Search Tree, pp. 95–96.
↑ Goodrich & Tamassia (2015), Section 4.2 AVL Trees, pp. 120–125.
↑ Goodrich & Tamassia (2015), Section 4.3 Red–black Trees, pp. 126–129.
↑ In Haeupler, Sen & Tarjan (2015) the conversion is done by rounding down, because the ranks of external nodes are −1 rather than 0. Goodrich & Tamassia (2015) give a formula that also rounds down, but because they use rank 0 for external nodes their formula incorrectly assigns red–black rank 0 to internal nodes with WAVL rank 1.

[hst15-1] 1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2015), "Rank-balanced trees" (PDF), ACM Transactions on Algorithms, 11 (4): Art. 30, 26, doi:10.1145/2689412, MR 3361215.

[gt-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 ^2.8 Goodrich, Michael T.; Tamassia, Roberto (2015), "4.4 Weak AVL Trees", Algorithm Design and Applications, Wiley, pp. 130–138.

[3] Goodrich & Tamassia (2015), Section 2.3 Trees, pp. 68–83.

[4] Goodrich & Tamassia (2015), Chapter 3 Binary Search Trees, pp. 89–114.

[5] In this we follow Goodrich & Tamassia (2015). In the version described by Haeupler, Sen & Tarjan (2015), the external nodes have rank −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.

[gt-search-6] 6.0 ^6.1 Goodrich & Tamassia (2015), Section 3.1.2 Searching in a Binary Search Tree, pp. 95–96.

[7] Goodrich & Tamassia (2015), Section 4.2 AVL Trees, pp. 120–125.

[8] Goodrich & Tamassia (2015), Section 4.3 Red–black Trees, pp. 126–129.

[9] In Haeupler, Sen & Tarjan (2015) the conversion is done by rounding down, because the ranks of external nodes are −1 rather than 0. Goodrich & Tamassia (2015) give a formula that also rounds down, but because they use rank 0 for external nodes their formula incorrectly assigns red–black rank 0 to internal nodes with WAVL rank 1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Anonymous

Search

WAVL ट्री

Namespaces

More

Page actions

Contents

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

परिभाषा

संचालन

खोज रहा हूँ

सम्मिलन

विलोपन

कम्प्यूटेशनल जटिलता

संबंधित संरचनाएं

एवीएल ट्री

लाल-काले ट्री

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

WAVL ट्री

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

परिभाषा

संचालन

खोज रहा हूँ

सम्मिलन

विलोपन

कम्प्यूटेशनल जटिलता

संबंधित संरचनाएं

एवीएल ट्री

लाल-काले ट्री

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories