WAVL ट्री: Difference between revisions

Latest revision as of 14:44, 28 July 2023

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

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

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

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

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

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

संचालन

अन्वेषण

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

सम्मिलन

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

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

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

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

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

विलोपन

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

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

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

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

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

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

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

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

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

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

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

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

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

एवीएल ट्री

^[2]^[1]

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

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

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

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

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

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

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

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

रंग-आधारित और पद -आधारित परिभाषाओं के बीच समानता को एक दिशा में, एक बिन्दु को काले रंग से देखा जा सकता है यदि उसके मूल की पद अधिक है और लाल रंग से यदि उसके मूल की पद समान है। दूसरी दिशा में, किसी बाहरी बिन्दु के किसी भी पथ पर काले बिन्दु की पद को काले बिन्दु की संख्या के बराबर बनाकर और लाल बिन्दु की पद को उसके मूल बिन्दु के बराबर बनाकर रंगों को पद में परिवर्तित किया जा सकता है।^[7]डब्ल्यूएवीएल ट्री में बिन्दु पद को प्रत्येक पद को दो से विभाजित करके और निकटतम पूर्णांक तक पूर्णांकित करके, लाल-काले ट्री की आवश्यकताओं का पालन करते हुए, बिन्दु की पद की एक प्रणाली में परिवर्तित किया जा सकता है।^[8] इस रूपांतरण के कारण, प्रत्येक डब्ल्यूएवीएल ट्री के लिए समान संरचना वाला एक वैध लाल-काला ट्री उपस्थित होता है। क्योंकि लाल-काले ट्री की ऊंचाई सबसे अधिक होती है $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 ^2.9 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.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 ^2.9 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.3 Red–black Trees, pp. 126–129.

[8] 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]

@@ Line 1: / Line 1: @@
-[[कंप्यूटर विज्ञान]] में, WAVL ट्री या कमजोर AVL ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष]] है। WAVL पेड़ों का नाम AVL पेड़ों के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज पेड़ है, और यह AVL पेड़ों और लाल-काले पेड़ों दोनों से निकटता से संबंधित है, जो सभी रैंक संतुलित पेड़ों के एक सामान्य ढांचे में आते हैं।
+[[कंप्यूटर विज्ञान]] में, '''डब्ल्यूएवीएल (WAVL) ट्री''' या कमजोर एवीएल ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष|स्व-संतुलन द्विआधारी विवृत्त ट्री]] है। डब्ल्यूएवीएल ट्री का नाम एवीएल ट्री  के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज ट्री है, और यह एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित है, जो सभी पद संतुलित ट्री के एक सामान्य ढांचे में आते हैं। अन्य संतुलित बाइनरी खोज ट्री की तरह, डब्ल्यूएवीएल ट्री प्रति संचालन {{math|''O''(log ''n'')}} समय में सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं। <ref name="hst15"/>
-अन्य संतुलित बाइनरी खोज पेड़ों की तरह, 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"/>
+डब्ल्यूएवीएल ट्री को एवीएल ट्री लाल-काले ट्री दोनों के कुछ सर्वोत्तम गुणों को संयोजित करने के लिए प्ररूपित किया गया है। लाल-काले ट्री  की तुलना में एवीएल ट्री का एक लाभ यह है कि वे अधिक संतुलित होते हैं: उनकी अधिकतम ऊंचाई होती है <math>\log_{\varphi} n\approx 1.44\log_2 n</math>, जबकि लाल-काले ट्री की अधिकतम ऊंचाई <math>2\log_2 n</math> से अधिक होती है, यदि एक डब्ल्यूएवीएल ट्री केवल सम्मिलन का उपयोग करके, बिना हटाए बनाया जाता है, तो इसमें वही छोटी ऊँचाई होती है जो एवीएल ट्री में होती है। दूसरी ओर, लाल-काले ट्री  को अपने ट्री  के कम पुनर्गठन में एवीएल ट्री के सापेक्ष में लाभ होता है। एवीएल ट्री में, प्रत्येक विलोपन के लिए ट्री के घूर्णन संचालन की एक लघुगणकीय संख्या की आवश्यकता हो सकती है, जबकि लाल-काले ट्री में सरल विलोपन संचालन होते हैं जो केवल ट्री  के घूर्णन की एक स्थिर संख्या का उपयोग करते हैं। डब्ल्यूएवीएल ट्री, लाल-काले ट्री की तरह, केवल ट्री के घूर्णन की एक स्थिर संख्या का उपयोग करते हैं, और स्थिरांक लाल-काले ट्री के सापेक्ष में भी उत्तम है।<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 वृक्षों की शुरुआत किसके द्वारा की गई थी? {{harvtxt|Haeupler|Sen|Tarjan|2015}}. उन्हीं लेखकों ने एवीएल पेड़ों, डब्ल्यूएवीएल पेड़ों और लाल-काले पेड़ों के बारे में एक सामान्य दृष्टिकोण भी प्रदान किया, क्योंकि ये सभी एक प्रकार के रैंक-संतुलित पेड़ हैं।<ref name="hst15">{{citation
+<ref name="hst15">{{citation
   | last1 = Haeupler | first1 = Bernhard
   | last2 = Sen | first2 = Siddhartha
@@ Line 16: / Line 15: @@
   | url = http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf
   | volume = 11
-  | year = 2015}}.</ref>
+  | year = 2015}}.</ref>डब्ल्यूएवीएल ट्री एवीएल ट्रीज को कहा जाता है जिन्हें {{harvtxt|ह्युप्लर|सेन |टारजन |2015}}. ने प्रस्तुत किया था। उन्ही लेखकों ने एवीएल ट्रीज, एवीएल ट्रीज और लाल-काले ट्रीज को पद -संतुलित ट्री के एक प्रकार के रूप में प्रदर्शित किया।
+== पद संतुलित ट्रीज की रूपरेखा ==
+अलग-अलग बाइनरी सर्च ट्री में डालने/हटाने और संतुलन कला विधि  के लिए अलग-अलग कला विधि  होते हैं, जिससे व्यवस्थित अध्ययन करना मुश्किल हो जाता है। लेखक {{harvtxt|ह्युप्लर|सेन |टारजन |2015}} पद  बाइनरी ट्री को परिभाषित करके बाइनरी सर्च ट्री के अध्ययन को एकीकृत करने के लिए पद संतुलित ट्री फ्रेमवर्क का परिचय दें, और प्रत्येक बाइनरी सर्च ट्री पद फलन पर लागू विशिष्ट बाधाओं का पालन करता है। ध्यान दें कि फ़्रेमवर्क उन कला विधि को निर्दिष्ट नहीं करता है जिनमें ये ट्री लागू किए जाते हैं।
+पद बाइनरी ट्री एक बाइनरी ट्री है जहां प्रत्येक बिन्दु   x एक पद  r(x) से जुड़ा होता है। परंपरा के अनुसार, खाली बिन्दु   की पद  -1 होती है। एक बिन्दु  x के लिए जो रूट नहीं है, पद अंतर है <math>r(p(x))-r(x)</math>, और यदि पद अंतर i है तो ऐसे बिन्दु को आई-चाइल्ड कहा जाता है। एक बिन्दु <math>i,j</math> प्रकार का होता है। यदि इसके बाएं चाइल्ड और दाएं चाइल्ड की पद का अंतर i और j है।
-== रैंक संतुलित वृक्ष रूपरेखा ==
+इसके साथ, हम अतिरिक्त नियम परिभाषित कर सकते हैं, जो विभिन्न ट्री से मेल खाते हैं:
-अलग-अलग बाइनरी सर्च ट्री में डालने/हटाने और संतुलन एल्गोरिदम के लिए अलग-अलग एल्गोरिदम होते हैं, जिससे व्यवस्थित अध्ययन करना मुश्किल हो जाता है। के लेखक {{harvtxt|Haeupler|Sen|Tarjan|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 नियम को सामान्य बनाता है।
-इसके साथ, हम अतिरिक्त नियम परिभाषित कर सकते हैं, जो विभिन्न पेड़ों से मेल खाते हैं:
+अब तक ये सभी नियम बाएँ बिन्दु और दाएँ बिन्दु के लिए सममित हैं। ऐसी समरूपता को तोड़कर, यह अन्य नियमों को जन्म देता है:
-* AVL नियम, जो AVL ट्री से मेल खाता है: प्रत्येक नोड प्रकार 1,1 या 1,2 का है।
+* दाएँ-झुकाव वाला दो-तीन नियम, जो दाएँ झुकाव वाले द्विअर्थी 2-3 ट्री से मेल खाता है: प्रत्येक बिन्दु 1,1 या 0,1 है, 0-चाइल्ड का कोई भी माता-पिता 0-बच्चा नहीं है, और कोई 0-बच्चा नहीं है।
-* 2-3 नियम, जो बाइनराइज्ड 2-3 ट्री से मेल खाता है: प्रत्येक नोड 0,1 या 1,1 प्रकार का है, और 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है।
+* वाम-झुकाव वाला दो-तीन नियम, जो बायीं ओर झुके हुए द्विअर्थी 2-3 ट्री  से मेल खाता है: प्रत्येक बिन्दु 1,1 या 0,1 है, 0-चाइल्ड   का कोई भी माता-पिता 0-बच्चा नहीं है, और कोई 0-बच्चा नहीं है सही है।
-* लाल काला नियम, जो लाल-काले पेड़ से मेल खाता है: सभी रैंक अंतर 0 या 1 हैं, और 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है। ध्यान दें कि लाल-काला नियम 0,0 प्रकार के नोड की अनुमति देकर 2-3 नियम को सामान्य बनाता है।
+* दाएं-झुकाव वाला लाल-काला नियम, जो रेफ्ट-झुकाव वाले लाल-काले ट्री  से मेल खाता है: 0-चाइल्ड का कोई भी माता-पिता 0-बच्चा नहीं है, और 0,1-बिन्दु   का कोई 0-बच्चा नहीं बचा है।
+* वाम-झुकाव वाले लाल-काले नियम, जो वाम-झुकाव वाले लाल-काले ट्री  से मेल खाता है: सभी पद 0 या 1 हैं, 0-चाइल्ड का कोई भी माता-पिता 0-बच्चा नहीं है, और 0 का कोई 0-बच्चा नहीं है, 1-बिन्दु सही है.
-अब तक ये सभी नियम बाएँ नोड और दाएँ नोड के लिए सममित हैं। ऐसी समरूपता को तोड़कर, यह अन्य नियमों को जन्म देता है:
+कमज़ोर एवीएल ट्री कमज़ोर एवीएल नियम द्वारा परिभाषित किया गया है:
-* दाएँ-झुकाव वाला दो-तीन नियम, जो दाएँ झुकाव वाले द्विअर्थी 2-3 पेड़ से मेल खाता है: प्रत्येक नोड 1,1 या 0,1 है, 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और कोई 0-बच्चा नहीं है शेष है।
+* कमजोर एवीएल नियम: सभी पद  अंतर 1 या 2 हैं, और सभी लीफ बिन्दु की पद  0 है।
-* वाम-झुकाव वाला दो-तीन नियम, जो बायीं ओर झुके हुए द्विअर्थी 2-3 पेड़ से मेल खाता है: प्रत्येक नोड 1,1 या 0,1 है, 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और कोई 0-बच्चा नहीं है सही है।
-* दाएं-झुकाव वाला लाल-काला नियम, जो रेफ्ट-झुकाव वाले लाल-काले पेड़ से मेल खाता है: 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और 0,1-नोड का कोई 0-बच्चा नहीं बचा है।
-* वाम-झुकाव वाले लाल-काले नियम, जो वाम-झुकाव वाले लाल-काले पेड़ से मेल खाता है: सभी रैंक अंतर 0 या 1 हैं, 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और 0 का कोई 0-बच्चा नहीं है, 1-नोड सही है.
-कमज़ोर AVL वृक्ष को कमज़ोर AVL नियम द्वारा परिभाषित किया गया है:
+ध्यान दें कि कमजोर एवीएल ट्री 2,2 प्रकार के बिन्दु की अनुमति देकर एवीएल ट्री को सामान्यीकृत करता है। एक साधारण प्रमाण से पता चलता है कि एक कमजोर एवीएल ट्री को इस तरह से रंगा जा सकता है जो लाल-काले ट्री का प्रतिनिधित्व करता है। तो एक अर्थ में, कमजोर एवीएल ट्री एवीएल ट्री और लाल-काले ट्री  के गुणों को जोड़ता है।
-* कमजोर एवीएल नियम: सभी रैंक अंतर 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>
+सामान्यतः बाइनरी सर्च ट्री की तरह, डब्ल्यूएवीएल ट्री में दो प्रकार के [[नोड (कंप्यूटर विज्ञान)|बिन्दु]] का संग्रह होता है: आंतरिक बिन्दु और बाहरी बिन्दु एक आंतरिक बिन्दु एक डेटा वस्तु संग्रहीत करता है, और अपने माता-पिता से जुड़ा होता है और ट्री में ठीक दो बच्चों, बाएं चाइल्ड और दाएं चाइल्ड से जुड़ा होता है। एक बाहरी बिन्दु में कोई डेटा नहीं होता है, और उसका लिंक केवल ट्री में उसके मूल बिन्दु से होता है। इन बिन्दु   को एक बाइनरी ट्री बनाने के लिए व्यवस्थित किया जाता है, ताकि किसी भी आंतरिक बिन्दु के लिए {{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>
-WAVL ट्री को अन्य प्रकार के बाइनरी सर्च ट्री से जो अलग करता है, वह है इसका रैंक का उपयोग। ये प्रत्येक नोड से जुड़े नंबर हैं, जो नोड से उसके सबसे दूर के पत्ते के वंशज तक की दूरी का अनुमान प्रदान करते हैं।
+*पद -अंतर संपत्ति: यदि एक गैर-रूट बिन्दु में पद  है {{mvar|r}}, तो उसके माता-पिता का पद या तो होना चाहिए {{math|''r'' + 1}} या {{math|''r'' + 2}}. दूसरे शब्दों में, किसी भी गैर-रूट बिन्दु के लिए पद  अंतर 1 या 2 है।<ref name="gt" />*आंतरिक-बिन्दु गुण: दो बाहरी बच्चों वाले एक आंतरिक बिन्दु की पद  बिल्कुल 1 होनी चाहिए।
-एवीएल पेड़ों के विपरीत, जहां रैंक को नोड्स की ऊंचाई के समान परिभाषित किया जाता है, डब्ल्यूएवीएल पेड़ों में रैंक हमेशा ऊंचाई के बराबर नहीं होती है। नोड 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}} की खोज करना किसी भी संतुलित द्विआधार सर्च ट्री डेटा संरचना की तरह होता है। पहले ट्री की रूट पर प्रारंभ करें, और फिर मूल से रूट तक के पथ पर प्रत्येक बिन्दु पर संग्रहीत डेटा वस्तु के साथ {{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="gt-search"/>
+===सम्मिलन===
+कुंजी के साथ एक आंतरिक बिन्दु सम्मिलित करना {{mvar|k}} डब्ल्यूएवीएल ट्री में खोज की आवश्यकता होती है {{mvar|k}} ट्री  में, एक बाहरी बिन्दु   पर समाप्त होता है, फिर दो बाहरी बच्चों के साथ नए आंतरिक बिन्दु   के साथ उस बाहरी बिन्दु   का प्रतिस्थापन होता है, और अंत में ट्री  का पुनर्संतुलन होता है। पुनर्संतुलन चरण या तो ऊपर से नीचे या नीचे से ऊपर किया जा सकता है,<ref name="hst15"/>लेकिन पुनर्संतुलन का निचला-ऊपर संस्करण वह है जो एवीएल ट्री से सबसे अधिक मेल खाता है।<ref name="gt"/><ref name="hst15"/>
+डब्ल्यूएवीएल ट्री में कुंजी {{mvar|k}} के साथ एक आंतरिक बिन्दु को सम्मिलित करने के लिए, ट्री में {{mvar|k}} की खोज की जाती है, जो एक बाह्य बिन्दु   पर समाप्त होती है, फिर उस बाह्य बिन्दु को दो बाह्य बच्चों के साथ नए आंतरिक बिन्दु से प्रतिस्थापित किया जाता है, और अंततः ट्री को संतुलित किया जाता है। संतुलनाधीन चरण को शीर्ष से नीचे तक या नीचे से शीर्ष तक किया जा सकता है लेकिन संतुलित करने का नीचे से शीर्ष तक वर्जन एवीएल ट्री के सबसे समीप होता है।
-===सम्मिलन===
+पद -अंतर पर विचार करके नीचे-ऊपर पुनर्संतुलन प्रारंभ होता है एक बिन्दु के बीच प्रारंभ में नया डाला गया बिन्दु और उसके अभिभावक. यदि कोई माता-पिता नहीं है, तो संतुलन बहाल हो जाता है। पहले प्रविष्टि प्रारंभ  हुई, पैरेंट और बिन्दु के बीच पद -अंतर 1 या 2,था लेकिन उपट्री के कारण वह अंतर 1 से कम हो गया है बिन्दु पर जड़ें लंबी हो गई हैं। यदि नये पद -अंतर के बीच पैरेंट और बिन्दु 1 है, संतुलन बहाल हो गया है। अन्यथा, यदि भाई-बहन, माता-पिता की दूसरी संतान, के साथ पद -अंतर 1 है माता-पिता, माता-पिता को बढ़ावा दें - वृद्धि करके इसकी पद  बढ़ाएं इसके और इसके प्रत्येक चाइल्ड के बीच पद -अंतर और जारी है नए बिन्दु के रूप में पुराने पैरेंट के साथ पुनर्संतुलन करता है।
-कुंजी के साथ एक आंतरिक नोड सम्मिलित करना {{mvar|k}} WAVL ट्री में खोज की आवश्यकता होती है {{mvar|k}} पेड़ में, एक बाहरी नोड पर समाप्त होता है, फिर दो बाहरी बच्चों के साथ नए आंतरिक नोड के साथ उस बाहरी नोड का प्रतिस्थापन होता है, और अंत में पेड़ का पुनर्संतुलन होता है। पुनर्संतुलन चरण या तो ऊपर से नीचे या नीचे से ऊपर किया जा सकता है,<ref name="hst15"/>लेकिन पुनर्संतुलन का निचला-ऊपर संस्करण वह है जो एवीएल पेड़ों से सबसे अधिक मेल खाता है।<ref name="gt"/><ref name="hst15"/>
-रैंक-अंतर पर विचार करके नीचे-ऊपर पुनर्संतुलन शुरू होता है
+अंत में, बिन्दु और सिबलिंग के लिए 0 और 2 के पद -अंतर के साथ, एक या पद -अंतर से संबंधित समायोजन के साथ, दो ट्री  घूर्णन,संतुलन बहाल कर सकता है. बिन्दु का बीच वाला बच्चा कुंजी वाला होता है बिन्दु और पैरेंट की कुंजियों के बीच यदि उसके लिए पद -अंतर है
-एक नोड के बीच - प्रारंभ में नया डाला गया नोड - और उसके
+चाइल्ड और बिन्दु 2 है, बिन्दु को ट्री और पेरेंट में ऊपर ले जाने के लिए घुमाएँ नीचे, फिर माता-पिता को पदावनत करें - समायोजित करके इसकी पद  कम करें इसके चारों ओर पद -अंतर - और संतुलन बहाल हो जाता है। अन्यथा,चाइल्ड को ऊपर और बिन्दु को नीचे ले जाने के लिए घुमाएँ, फिर दोबारा घुमाएँ चाइल्ड को ऊपर और माता-पिता को नीचे ले जाएँ। चाइल्ड को प्रमोट करो, डिमोट करो बिन्दु और पैरेंट, और संतुलन बहाल हो जाता है।
-अभिभावक. यदि कोई माता-पिता नहीं है, तो संतुलन बहाल हो जाता है। पहले
-प्रविष्टि शुरू हुई, पैरेंट और नोड के बीच रैंक-अंतर 1 या था
-, लेकिन उपवृक्ष के कारण वह अंतर 1 से कम हो गया है
-नोड पर जड़ें लंबी हो गई हैं। यदि नये रैंक-अंतर के बीच
-पैरेंट और नोड 1 है, संतुलन बहाल हो गया है। अन्यथा, यदि
-भाई-बहन, माता-पिता की दूसरी संतान, के साथ रैंक-अंतर 1 है
-माता-पिता, माता-पिता को बढ़ावा दें - वृद्धि करके इसकी रैंक बढ़ाएं
-इसके और इसके प्रत्येक बच्चे के बीच रैंक-अंतर - और जारी है
-नए नोड के रूप में पुराने पैरेंट के साथ पुनर्संतुलन।
-अंत में, नोड और सिबलिंग के लिए 0 और 2 के रैंक-अंतर के साथ, एक या
+इस प्रकार, कुल मिलाकर, सम्मिलन प्रक्रिया में एक खोज, नए बिन्दु की एक निरंतर संख्या का निर्माण, पद  परिवर्तनों की एक लघुगणकीय संख्या और ट्री के घूर्णन की एक निरंतर संख्या सम्मिलित होती है।<ref name="gt" /><ref name="hst15" />
-रैंक-अंतर से संबंधित समायोजन के साथ, दो वृक्ष घूर्णन,
-संतुलन बहाल कर सकता है. नोड का बीच वाला बच्चा कुंजी वाला होता है
-नोड और पैरेंट की कुंजियों के बीच। यदि उसके लिए रैंक-अंतर है
-चाइल्ड और नोड 2 है, नोड को पेड़ और पेरेंट में ऊपर ले जाने के लिए घुमाएँ
-नीचे, फिर माता-पिता को पदावनत करें - समायोजित करके इसकी रैंक कम करें
-इसके चारों ओर रैंक-अंतर - और संतुलन बहाल हो जाता है। अन्यथा,
-बच्चे को ऊपर और नोड को नीचे ले जाने के लिए घुमाएँ, फिर दोबारा घुमाएँ
-बच्चे को ऊपर और माता-पिता को नीचे ले जाएँ। बच्चे को प्रमोट करो, डिमोट करो
-नोड और पैरेंट, और संतुलन बहाल हो जाता है।
-इस प्रकार, कुल मिलाकर, सम्मिलन प्रक्रिया में एक खोज, नए नोड्स की एक निरंतर संख्या का निर्माण, रैंक परिवर्तनों की एक लघुगणकीय संख्या और पेड़ के घूर्णन की एक निरंतर संख्या शामिल होती है।<ref name="gt"/><ref name="hst15"/>
 ===विलोपन===
-WAVL ट्री से आंतरिक नोड को हटाना सामान्य से शुरू होता है
+डब्ल्यूएवीएल ट्री से एक आंतरिक बिन्दु  को हटाने की प्रक्रिया साधारण बाइनरी सर्च ट्री हटाने से प्रारंभ होती है। एक आंतरिक बिन्दु   के लिए जो किसी बाह्य बच्चे के बिना होता है, इसका अर्थ है कि उसे ट्री में उसके उत्तरजीवी का पता लगाना होगा, बिन्दु   को उसके उत्तरजीवी के साथ बदलना होगा, और फिर बिन्दु को नए ट्री स्थान से हटाना होगा, जहां उसका बाएं बच्चा आवश्यकतानुसार एक बाह्य बिन्दु होगा। एक आंतरिक बिन्दु को हटाने के लिए जो एक बाह्य बच्चे के साथ होता है, उसे दूसरे बच्चे से प्रतिस्थापित करें।
-बाइनरी सर्च ट्री#विलोपन। संख्या वाले आंतरिक नोड के लिए
-बाहरी संतान, इसका मतलब है पेड़ में अपना उत्तराधिकारी ढूंढना,
-नोड को उसके उत्तराधिकारी के साथ बदलना, और फिर नोड को हटाना
-अपने नए वृक्ष की स्थिति से, जहां उसका बायां बच्चा अनिवार्य रूप से एक है
-बाहरी नोड. किसी बाहरी बच्चे के साथ आंतरिक नोड को हटाने के लिए,
-नोड को दूसरे बच्चे के साथ बदलें।
-रैंक-अंतर पर विचार करके नीचे-ऊपर पुनर्संतुलन शुरू होता है
+पद -अंतर संतुलनाधीन चरण पाठकों में सोचना प्रारंभ करता है जो बिन्दु   के बीच पद  -अंतर होता है - प्रारंभिक रूप में, हटाए गए बिन्दु   को प्रतिस्थापित करने वाला बिन्दु  । यदि कोई माता-पिता नहीं है, तो संतुलन संशोधित होता है। हटाने की प्रारंभिक तिथि से पहले, माता-पिता और बिन्दु   के बीच पद  -अंतर 1 या 2 था, लेकिन इस अंतर को 1 के साथ बढ़ा दिया गया है क्योंकि बिन्दु के द्वारा जड़ी उपट्री  को छोटा कर दिया गया है। यदि माता-पिता के पास अब दो बाह्य बच्चे हैं, तो आंतरिक-बिन्दु संपत्ति को उल्लंघन किया जाता है क्योंकि माता-पिता का पद   2 होता है। माता-पिता को अवमानित किया जाना चाहिए, और संतुलनाधीनीकरण जारी रखना चाहिए जहां माता-पिता उन्हीं का बिन्दु है जो अत्यंत छोटे उपट्री      के मूल है।
-एक नोड के बीच - प्रारंभ में, वह नोड जिसने हटाए गए नोड को प्रतिस्थापित किया -
-और उसके जनक. यदि कोई माता-पिता नहीं है, तो संतुलन बहाल हो जाता है। पहले
-विलोपन शुरू हुआ, पैरेंट और नोड के बीच रैंक-अंतर 1 या था
-, लेकिन उपवृक्ष के कारण वह अंतर 1 से बढ़ गया है
-नोड पर रूट छोटा हो गया है। यदि माता-पिता के पास अब दो बाहरी हैं
-बच्चों, आंतरिक-नोड संपत्ति का उल्लंघन होता है क्योंकि माता-पिता
-रैंक 2 है। माता-पिता को पदावनत किया जाना चाहिए, और पुनर्संतुलन जारी रखा जाना चाहिए
-पैरेंट के साथ नोड के रूप में जो कि बहुत छोटे उपवृक्ष की जड़ है।
-यदि नोड में कोई पेरेंट नहीं है, तो संतुलन बहाल हो जाता है। यदि
+यदि बिन्दु का माता-पिता नहीं है, तो संतुलन संशोधित हो जाता है। यदि बिन्दु और माता-पिता के बीच पद -अंतर 1 से 2 तक बढ़ गया है, तो संतुलन संशोधित हो जाता है। अन्यथा, यदि सहोदर, माता-पिता का दूसरा बच्चा, माता-पिता के साथ पद  -अंतर 2 है, तो माता-पिता को अवमानित करें - उसका पद कम करें, अर्थात उसके और प्रत्येक बच्चे के बीच पद  -अंतर को कम करें - और पुराने माता-पिता को नए बिन्दु के रूप में संतुलनाधीनीकरण जारी रखें। अन्यथा, यदि सहोदर के दोनों बच्चों के बीच पद  -अंतर 2 हैं, तो माता-पिता और सहोदर को अवमानित करें और पुराने माता-पिता को नए बिन्दु के रूप में संतुलनाधीनीकरण जारी रखें।
-नोड और पैरेंट के बीच रैंक-अंतर 1 से बढ़कर 2 हो गया है, संतुलन
-बहाल कर दिया गया है. अन्यथा, यदि भाई-बहन, माता-पिता की दूसरी संतान,
-माता-पिता के साथ रैंक-अंतर 2 है, माता-पिता को पदावनत करें -
-इसके बीच के रैंक-अंतर को कम करके इसकी रैंक को कम करें
-इसके प्रत्येक बच्चे - और बूढ़े माता-पिता के साथ पुनर्संतुलन जारी रखें
-नया नोड. अन्यथा, यदि भाई-बहन के दो बच्चे हैं
-भाई-बहन के साथ 2 का रैंक-अंतर, माता-पिता को पदावनत करता है और
-भाई-बहन और नए नोड के रूप में पुराने माता-पिता के साथ पुनर्संतुलन जारी रखें।
-अंत में, नोड और सिबलिंग के लिए 3 और 1 के रैंक-अंतर के साथ, और
+अंत में, जहां बिन्दु और सहोदर के बीच पद-अंतर 3 और 1 है, और सहोदर के पास एक बच्चा है जिसका पद -अंतर 1 है, वहां एक या दो ट्री परिवर्तन, पद-अंतरों को संबंधित समायोजन के साथ, संतुलन को संशोधित कर सकते हैं। सहोदर के बच्चों को भांजी और भतीजा के रूप में पहचानें, जहां भांजी की कुंजी माता-पिता और सहोदर की कुंजियों के बीच होती है, और भतीजा की कुंजी नहीं होती है। यदि सहोदर और भतीजा के बीच पद-अंतर 1 है, तो सहोदर को ऊपर ले जाने और माता-पिता को नीचे ले जाने के लिए ट्री परिवर्तन करें, सहोदर को पदोन्नत करें और माता-पिता को एक बार कम करें, कम से कम, और आवश्यक होने पर दो बार कम करें जिससे आंतरिक-बिन्दु गुण का उल्लंघन न हो। अन्यथा, सहोदर और भतीजा के बीच पद-अंतर को 1 के रूप में रखकर, भांजी को ऊपर ले जाने और सहोदर को नीचे ले जाने के लिए ट्री परिवर्तन करें, फिर से ट्री परिवर्तन करें भांजी को ऊपर ले जाने और माता-पिता को नीचे ले जाने के लिए, भांजी को दो बार पदोन्नत करें, सहोदर को एक बार कम करें, और माता-पिता को दो बार कम करें।
-भाई-बहन के बच्चे का रैंक-अंतर 1, एक या दो पेड़ है
-रैंक-अंतर से जुड़े समायोजन के साथ रोटेशन, कर सकते हैं
-संतुलन बहाल करें. भाई-बहन के बच्चों को भतीजी और के रूप में पहचानें
-भतीजा, जहां भतीजी की चाबी की चाबियों के बीच में होती है
-माता-पिता और भाई-बहन, और भतीजे की चाबी नहीं है। यदि
-भाई-बहन और भतीजे के बीच पद-अंतर 1 है, घूमने के लिए घुमाएँ
-भाई-बहन को ऊपर और माता-पिता को नीचे, भाई-बहन को बढ़ावा देना और माता-पिता को पदावनत करना
-उल्लंघन से बचने के लिए यदि आवश्यक हो तो एक बार, कम से कम और दो बार
-आंतरिक-नोड संपत्ति। अन्यथा, बीच रैंक-अंतर के साथ
-भाई-बहन और भतीजे को 1 के रूप में, भतीजी और भाई-बहन को ऊपर ले जाने के लिए घुमाएँ
-नीचे, भतीजी को ऊपर और माता-पिता को नीचे ले जाने के लिए फिर से घुमाएँ, बढ़ावा दें
-भतीजी को दो बार पदावनत करें, भाई-बहन को एक बार पदावनत करें, और दो बार माता-पिता को पदावनत करें।
-कुल मिलाकर, विलोपन में एक शामिल होता है
+कुल मिलाकर, विलोपन में एक सम्मिलित होता है किसी बाहरी चाइल्ड के साथ एक बिन्दु खोजने के लिए नीचे की ओर खोजें, को हटा दें नए बिन्दु की एक स्थिर संख्या, पद परिवर्तन की एक लघुगणकीय संख्या,और ट्री के घूमने की एक स्थिर संख्या रहने दे।
-किसी बाहरी बच्चे के साथ एक नोड खोजने के लिए नीचे की ओर खोजें, को हटा दें
-नए नोड्स की एक स्थिर संख्या, रैंक परिवर्तन की एक लघुगणकीय संख्या,
-और पेड़ों के घूमने की एक स्थिर संख्या।[1][2]
-एक डिलीट के परिणाम की तुलना करना सार्थक है जो एक AVL ट्री में कई स्तरों पर घुमाव का कारण बनता है और एक WAVL ट्री में किए गए रोटेशन और रैंक परिवर्तनों के साथ। दूसरी छवि में मान 12 वाले नोड को हटा दिया गया है, इसके बाद दाएं घुमाव और सभी बाहरी नोड्स को शून्य रैंक दिया गया है।
+यह महत्वपूर्ण है कि एवीएल ट्री में कई स्तरों पर घुमाने वाले चक्रवात होने के कारण हटाने के परिणाम को डब्ल्यूएवीएल ट्री में किए गए चक्रवात और पद परिवर्तनों के साथ तुलना किया जाए। दूसरी छवि में, मान 12 वाले बिन्दु को हटा दिया गया है, इसके बाद दाएं घूमाने और सभी बाह्य बिन्दु को पद शून्य के रूप में निर्धारित किया गया है।
-    [[File:FibonacciTreeWRanks.png|thumb|रैंकों के साथ फाइबोनैचि वृक्ष]] [[File:Fibonacci Tree after Delete.png|thumb|हटाने के बाद रैंक के साथ फाइबोनैचि वृक्ष]]
+    [[File:FibonacciTreeWRanks.png|thumb|पदो के साथ फाइबोनैचि ट्री ]] [[File:Fibonacci Tree after Delete.png|thumb|हटाने के बाद पद  के साथ फाइबोनैचि ट्री ]]
 ==कम्प्यूटेशनल जटिलता==
-WAVL ट्री में प्रत्येक खोज, सम्मिलन या विलोपन में ट्री में एक ही पथ का अनुसरण करना और पथ में प्रत्येक नोड के लिए निरंतर चरणों का पालन करना शामिल है। एक WAVL पेड़ में {{mvar|n}} आइटम जिनमें केवल सम्मिलन हुआ है, अधिकतम पथ लंबाई है <math>\log_{\varphi} n\approx 1.44\log_2 n</math>. यदि सम्मिलन और विलोपन दोनों हो सकते हैं, तो अधिकतम पथ लंबाई है <math>2\log_2 n</math>. इसलिए, किसी भी मामले में, WAVL ट्री में प्रत्येक खोज, सम्मिलन या विलोपन के लिए सबसे खराब स्थिति का समय {{mvar|n}} डेटा आइटम है {{math|''O''(log ''n'')}}.
+डब्ल्यूएवीएल ट्री में प्रत्येक खोज, सम्मिलन या विलोपन में ट्री में एक ही पथ का अनुसरण करना और पथ में प्रत्येक बिन्दु   के लिए निरंतर चरणों का पालन करना सम्मिलित   है। एक डब्ल्यूएवीएल ट्री  में {{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'')}}.
-इसके अतिरिक्त, सम्मिलन और विलोपन के लिए एक नोड खोजने के बाद, पेड़ पुनर्गठन संचालन की परिशोधित जटिलता स्थिर रहती है। नोड को जोड़ना या हटाना स्वयं एक स्थिर समय है, घुमावों की मात्रा हमेशा अधिकतम स्थिर होती है और यह दिखाया जा सकता है कि नोड्स में रैंक परिवर्तन की कुल मात्रा सम्मिलन और विलोपन दोनों की संख्या में रैखिक है।
+इसके अतिरिक्त, सम्मिलन और विलोपन के लिए एक बिन्दु   खोजने के बाद, ट्री  पुनर्गठन संचालन की परिशोधित जटिलता स्थिर रहती है। बिन्दु   को जोड़ना या हटाना स्वयं एक स्थिर समय है, घुमावों की मात्रा हमेशा अधिकतम स्थिर होती है और यह दिखाया जा सकता है कि बिन्दु  ्स में पद  परिवर्तन की कुल मात्रा सम्मिलन और विलोपन दोनों की संख्या में रैखिक है।
 ==संबंधित संरचनाएं==
-WAVL पेड़, AVL पेड़ और लाल-काले पेड़ दोनों से निकटता से संबंधित हैं।
+डब्ल्यूएवीएल ट्री, एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित हैं। प्रत्येक एवीएल ट्री के बिन्दु को इस तरह से पद दी जा सकती है कि वह डब्ल्यूएवीएल ट्री बन जाए। और प्रत्येक डब्ल्यूएवीएल ट्री  के बिन्दु लाल और काले रंग के हो सकते हैं  जिससे यह एक लाल-काले ट्री  में बदल जाता है। यद्यपि, कुछ डब्ल्यूएवीएल ट्री इस तरह से एवीएल ट्री से नहीं आते हैं और कुछ लाल-काले ट्री इस तरह से डब्ल्यूएवीएल ट्री से नहीं आते हैं।
-प्रत्येक AVL ट्री के नोड्स को इस तरह से रैंक दी जा सकती है कि वह WAVL ट्री बन जाए। और प्रत्येक WAVL पेड़ के नोड्स लाल और काले रंग के हो सकते हैं (और इसकी रैंकों को फिर से निर्दिष्ट किया जा सकता है) जिससे यह एक लाल-काले पेड़ में बदल जाता है। हालाँकि, कुछ WAVL पेड़ इस तरह से AVL पेड़ों से नहीं आते हैं और कुछ लाल-काले पेड़ इस तरह से WAVL पेड़ों से नहीं आते हैं।
+===एवीएल ट्री ===
+<ref name="gt"/><ref name="hst15"/>
+एक एवीएल ट्री एक प्रकार का संतुलित द्विआधार सर्च ट्री है जिसमें प्रत्येक आंतरिक बिन्दु के दो बच्चों की ऊंचाइयों में अधिकतम एक तक का अंतर होना चाहिए। बाह्य बिन्दु की ऊंचाई शून्य होती है, और किसी भी आंतरिक बिन्दु की ऊंचाई हमेशा उसके दो बच्चों की ऊंचाइयों की अधिकतम ऊंचाई प्लस एक होती है। इस प्रकार, एक एवीएल ट्री की ऊंचाई की फलन एक डब्ल्यूएवीएल ट्री की नियमों का पालन करती है, और हम प्रत्येक बिन्दु की ऊंचाई को उसकी पद के रूप में उपयोग करके किसी भी एवीएल ट्री को एक डब्ल्यूएवीएल ट्री में बदल सकते हैं।<ref name="hst15" /><ref name="gt" />
-===एवीएल पेड़===
+एक एवीएल ट्री और डब्ल्यूएवीएल ट्री के बीच मुख्य अंतर उत्पन्न होता है जब एक बिन्दु के पास दो बच्चे होते हैं जिनकी ऊंचाई या पद       समान होती है। एक एवीएल ट्री में, यदि एक बिन्दु x के पास दो ऐसे बच्चे होते हैं जिनकी ऊंचाई h होती है और एक दूसरे के समान होती है, तो x की ऊंचाई केवल h + 1 होनी चाहिए। इसके विपरीत, एक डब्ल्यूएवीएल ट्री में, यदि एक बिन्दु x के पास दो ऐसे बच्चे होते हैं जिनकी पद r होती है और एक दूसरे के समान होती है, तो x का पद या तो r + 1 या r + 2 हो सकता है। इसका कारण यह है कि डब्ल्यूएवीएल ट्री में ऊंचाई से सामान्यतः बराबर नहीं होती है। पद में अधिकतम परिवर्तिता के कारण, संरचनाओं में अधिकतम परिवर्तिता होती है: कुछ डब्ल्यूएवीएल ट्री ऐसी हो सकती हैं जिन्हें पद को संशोधित करके भी एवीएल ट्री में बदला नहीं जा सकता है, क्योंकि इसमें ऐसे बिन्दु सम्मिलित होते हैं जिनके बच्चों की ऊंचाई में एक से अधिक अंतर होता है। यद्यपि, हम कह सकते हैं कि सभी एवीएल ट्री डब्ल्यूएवीएल ट्री हैं। एवीएल ट्री डब्ल्यूएवीएल ट्री होते हैं जिनमें पद अंतर 2 वाले बिन्दु के प्रकार नहीं होते हैं।।<ref name="gt" />
-एवीएल ट्री एक प्रकार का संतुलित बाइनरी सर्च ट्री है जिसमें प्रत्येक आंतरिक नोड के दो बच्चों की ऊंचाई अधिकतम एक से भिन्न होनी चाहिए।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, Section 4.2 AVL Trees, pp. 120–125.</ref> किसी बाहरी नोड की ऊंचाई शून्य है, और किसी भी आंतरिक नोड की ऊंचाई हमेशा उसके दो बच्चों की ऊंचाई से एक प्लस अधिक होती है। इस प्रकार, AVL पेड़ की ऊंचाई फ़ंक्शन WAVL पेड़ की बाधाओं का पालन करती है, और हम प्रत्येक नोड की ऊंचाई को उसके रैंक के रूप में उपयोग करके किसी भी AVL पेड़ को WAVL पेड़ में परिवर्तित कर सकते हैं।<ref name="gt"/><ref name="hst15"/>
-AVL ट्री और WAVL ट्री के बीच मुख्य अंतर तब उत्पन्न होता है जब एक नोड में समान रैंक या ऊंचाई वाले दो बच्चे होते हैं। AVL ट्री में, यदि एक नोड {{mvar|x}} के एक ही कद के दो बच्चे हैं {{mvar|h}} एक दूसरे के रूप में, तो की ऊंचाई {{mvar|x}} बिलकुल होना चाहिए {{math|''h'' + 1}}. इसके विपरीत, WAVL पेड़ में, यदि एक node {{mvar|x}} के एक ही रैंक के दो बच्चे हैं {{mvar|r}} एक दूसरे के रूप में, फिर की रैंक {{mvar|x}} या तो किया जा सकता है {{math|''r'' + 1}} या {{math|''r'' + 2}}. ऐसा इसलिए है क्योंकि WAVL ट्री में रैंक पूरी तरह से ऊंचाई के बराबर नहीं है। रैंकों में इस अधिक लचीलेपन से संरचनाओं में भी अधिक लचीलापन आता है: कुछ WAVL पेड़ों को उनके रैंकों को संशोधित करके भी AVL पेड़ों में नहीं बनाया जा सकता है, क्योंकि उनमें ऐसे नोड शामिल होते हैं जिनके बच्चों की ऊंचाई एक से अधिक भिन्न होती है।<ref name="hst15"/>हालाँकि, हम कह सकते हैं कि सभी AVL पेड़ WAVL पेड़ हैं। AVL पेड़ बिना किसी प्रकार के नोड वाले WAVL पेड़ हैं जिनके दोनों बच्चों की रैंक में अंतर 2 है।<ref name="gt" />
+यदि एक डब्ल्यूएवीएल ट्री केवल सम्मिलन संचालन का उपयोग करके बनाया गया है, तो इसकी संरचना समान सम्मिलन अनुक्रम द्वारा बनाए गए एवीएल ट्री की संरचना के समान होगी, और इसकी पद संबंधित एवीएल ट्री की पद के समान होगी। केवल विलोपन कार्यों के माध्यम से ही एक डब्ल्यूएवीएल ट्री एक एवीएल ट्री से भिन्न हो सकता है। विशेष रूप से इसका तात्पर्य यह है कि केवल सम्मिलन के माध्यम से बनाए गए डब्ल्यूएवीएल ट्री की ऊंचाई अधिकतम होती है <math>\log_{\varphi} n\approx 1.44\log_2 n</math> तक होती है।<ref name="hst15" />
-यदि एक WAVL ट्री केवल सम्मिलन संचालन का उपयोग करके बनाया गया है, तो इसकी संरचना समान सम्मिलन अनुक्रम द्वारा बनाए गए AVL वृक्ष की संरचना के समान होगी, और इसकी रैंक संबंधित AVL वृक्ष की रैंक के समान होगी। केवल विलोपन कार्यों के माध्यम से ही एक WAVL वृक्ष एक AVL वृक्ष से भिन्न हो सकता है। विशेष रूप से इसका तात्पर्य यह है कि केवल सम्मिलन के माध्यम से बनाए गए WAVL पेड़ की ऊंचाई अधिकतम होती है <math>\log_{\varphi} n\approx 1.44\log_2 n</math>.<ref name="hst15"/>
-===लाल-काले पेड़===
+===लाल-काले ट्री ===
-लाल-काला पेड़ एक संतुलित बाइनरी खोज पेड़ है जिसमें प्रत्येक नोड का एक रंग (लाल या काला) होता है, जो निम्नलिखित गुणों को संतुष्ट करता है:
+लाल-काला ट्री एक संतुलित बाइनरी खोज ट्री है जिसमें प्रत्येक बिन्दु  का एक रंग होता है, जो निम्नलिखित गुणों को संतुष्ट करता है:
-* बाहरी नोड्स काले हैं.
+* बाहरी बिन्दु काले हैं.
-* यदि कोई आंतरिक नोड लाल है, तो उसके दोनों बच्चे काले हैं।
+* यदि कोई आंतरिक बिन्दु लाल है, तो उसके दोनों चाइल्ड काले हैं।
-* रूट से बाहरी नोड तक के सभी पथों में समान संख्या में ब्लैक नोड होते हैं।
+* रूट से बाहरी बिन्दु तक के सभी पथों में समान संख्या में काले बिन्दु होते हैं।
-लाल-काले पेड़ों को समान रूप से नोड्स पर संग्रहीत रैंकों की एक प्रणाली के संदर्भ में परिभाषित किया जा सकता है, जो निम्नलिखित आवश्यकताओं को पूरा करता है (WAVL पेड़ों में रैंकों की आवश्यकताओं से भिन्न):
+लाल-काले ट्री  को समान रूप से बिन्दु पर संग्रहीत पद की एक प्रणाली के संदर्भ में परिभाषित किया जा सकता है, जो निम्नलिखित आवश्यकताओं को पूरा करता है।
-* बाहरी नोड की रैंक हमेशा 0 होती है और उसके मूल नोड की रैंक हमेशा 1 होती है।
+* बाहरी बिन्दु की पद  हमेशा 0 होती है और उसके मूल बिन्दु की पद 1 होती है।
-* किसी भी गैर-रूट नोड की रैंक या तो उसके मूल नोड की रैंक या उसके मूल नोड की रैंक माइनस 1 के बराबर होती है।
+* किसी भी गैर-रूट बिन्दु की पद  या तो उसके मूल बिन्दु की पद या उसके मूल बिन्दु की पद - 1 के बराबर होती है।
-* किसी भी जड़-पत्ती पथ पर लगातार दो किनारों में रैंक अंतर 0 नहीं होता है।
+* किसी भी जड़-पत्ती पथ पर लगातार दो किनारों में पद अंतर 0 नहीं होता है।
-रंग-आधारित और रैंक-आधारित परिभाषाओं के बीच समानता को एक दिशा में, एक नोड को काले रंग से देखा जा सकता है यदि उसके मूल की रैंक अधिक है और लाल रंग से यदि उसके मूल की रैंक समान है। दूसरी दिशा में, किसी बाहरी नोड के किसी भी पथ पर काले नोड की रैंक को काले नोड की संख्या के बराबर बनाकर और लाल नोड की रैंक को उसके मूल नोड के बराबर बनाकर रंगों को रैंक में परिवर्तित किया जा सकता है।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, Section 4.3 Red–black Trees, pp. 126–129.</ref>
+रंग-आधारित और पद -आधारित परिभाषाओं के बीच समानता को एक दिशा में, एक बिन्दु को काले रंग से देखा जा सकता है यदि उसके मूल की पद अधिक है और लाल रंग से यदि उसके मूल की पद  समान है। दूसरी दिशा में, किसी बाहरी बिन्दु के किसी भी पथ पर काले बिन्दु की पद को काले बिन्दु की संख्या के बराबर बनाकर और लाल बिन्दु की पद  को उसके मूल बिन्दु के बराबर बनाकर रंगों को पद  में परिवर्तित किया जा सकता है।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, Section 4.3 Red–black Trees, pp. 126–129.</ref>डब्ल्यूएवीएल ट्री में बिन्दु पद  को प्रत्येक पद को दो से विभाजित करके और निकटतम पूर्णांक तक पूर्णांकित करके, लाल-काले ट्री की आवश्यकताओं का पालन करते हुए, बिन्दु की पद की एक प्रणाली में परिवर्तित किया जा सकता है।<ref>In {{harvtxt|Haeupler|Sen|Tarjan|2015}} the conversion is done by rounding down, because the ranks of external nodes are &minus;1 rather than&nbsp;0. {{harvtxt|Goodrich|Tamassia|2015}} give a formula that also rounds down, but because they use rank&nbsp;0 for external nodes their formula incorrectly assigns red–black rank&nbsp;0 to internal nodes with WAVL rank&nbsp;1.</ref> इस रूपांतरण के कारण, प्रत्येक डब्ल्यूएवीएल ट्री के लिए समान संरचना वाला एक वैध लाल-काला ट्री उपस्थित होता है। क्योंकि लाल-काले ट्री की ऊंचाई सबसे अधिक होती है <math>2\log_2 n</math>, डब्ल्यूएवीएल ट्री के लिए भी यही सच है।<ref name="gt"/><ref name="hst15"/> यद्यपि ऐसे लाल-काले ट्री  उपस्थित हैं जिन्हें वैध डब्ल्यूएवीएल ट्री पद फलन नहीं दिया जा सकता है।<ref name="hst15"/>
-WAVL ट्री में नोड्स की रैंक को प्रत्येक रैंक को दो से विभाजित करके और निकटतम पूर्णांक तक पूर्णांकित करके, लाल-काले पेड़ों की आवश्यकताओं का पालन करते हुए, नोड्स की रैंक की एक प्रणाली में परिवर्तित किया जा सकता है।<ref>In {{harvtxt|Haeupler|Sen|Tarjan|2015}} the conversion is done by rounding down, because the ranks of external nodes are &minus;1 rather than&nbsp;0. {{harvtxt|Goodrich|Tamassia|2015}} give a formula that also rounds down, but because they use rank&nbsp;0 for external nodes their formula incorrectly assigns red–black rank&nbsp;0 to internal nodes with WAVL rank&nbsp;1.</ref> इस रूपांतरण के कारण, प्रत्येक WAVL पेड़ के लिए समान संरचना वाला एक वैध लाल-काला पेड़ मौजूद होता है। क्योंकि लाल-काले पेड़ों की ऊंचाई सबसे अधिक होती है <math>2\log_2 n</math>, WAVL पेड़ों के लिए भी यही सच है।<ref name="gt"/><ref name="hst15"/>हालाँकि, ऐसे लाल-काले पेड़ मौजूद हैं जिन्हें वैध WAVL ट्री रैंक फ़ंक्शन नहीं दिया जा सकता है।<ref name="hst15"/>
-इस तथ्य के बावजूद कि, अपने वृक्ष संरचनाओं के संदर्भ में, WAVL पेड़ लाल-काले पेड़ों के विशेष मामले हैं, उनके अद्यतन संचालन अलग-अलग हैं। WAVL ट्री अपडेट ऑपरेशन में उपयोग किए जाने वाले ट्री रोटेशन ऐसे परिवर्तन कर सकते हैं जिन्हें लाल-काले पेड़ में अनुमति नहीं दी जाएगी, क्योंकि वे वास्तव में केवल एक ही रंग में परिवर्तन करने के बजाय लाल-काले पेड़ के बड़े उप-वृक्षों का रंग बदलने का कारण बनेंगे। पेड़ में पथ.<ref name="hst15"/>यह WAVL पेड़ों को लाल-काले पेड़ों की तुलना में, सबसे खराब स्थिति में, प्रति विलोपन कम पेड़ रोटेशन करने की अनुमति देता है।<ref name="gt"/><ref name="hst15"/>
+इस तथ्य के बाद भी, अपने ट्री संरचनाओं के संदर्भ में, डब्ल्यूएवीएल ट्री लाल-काले ट्री के विशेष स्थितिया हैं, उनके अद्यतन संचालन अलग-अलग हैं। डब्ल्यूएवीएल ट्री अपडेट संचालन में उपयोग किए जाने वाले ट्री वर्तन ऐसे परिवर्तन कर सकते हैं जिन्हें लाल-काले ट्री  में अनुमति नहीं दी जाएगी, क्योंकि वे वास्तव में केवल एक ही रंग में परिवर्तन करने के अतिरिक्त लाल-काले ट्री  के बड़े उप-ट्री का रंग बदलने का कारण बनेंगे।<ref name="hst15"/>यह डब्ल्यूएवीएल ट्री को लाल-काले ट्री  की तुलना में, सबसे निम्न स्थिति में, प्रति विलोपन कम ट्री वर्तन करने की अनुमति देता है।<ref name="gt"/><ref name="hst15"/>
 ==संदर्भ==
 {{reflist}}
-[[Category: बाइनरी पेड़]] [[Category: पेड़ खोजें]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 10/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:पेड़ खोजें]]
+[[Category:बाइनरी पेड़]]

Anonymous

Search

WAVL ट्री: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 14:44, 28 July 2023

Contents

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

परिभाषा

संचालन

अन्वेषण

सम्मिलन

विलोपन

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

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

एवीएल ट्री

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

WAVL ट्री: Difference between revisions

Latest revision as of 14:44, 28 July 2023

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

परिभाषा

संचालन

अन्वेषण

सम्मिलन

विलोपन

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

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

एवीएल ट्री

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories