WAVL ट्री: Difference between revisions

From Vigyanwiki
No edit summary
 
(9 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में, डब्ल्यूएवीएल ट्री या कमजोर एवीएल ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष|स्व-संतुलन द्विआधारी विवृत्त ट्री]] है। डब्ल्यूएवीएल ट्री का नाम एवीएल ट्री  के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज ट्री है, और यह एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित है, जो सभी पद संतुलित ट्री के एक सामान्य ढांचे में आते हैं। अन्य संतुलित बाइनरी खोज ट्री की तरह, डब्ल्यूएवीएल ट्री प्रति संचालन {{math|''O''(log ''n'')}} समय में सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं। <ref name="hst15"/>
[[कंप्यूटर विज्ञान]] में, '''डब्ल्यूएवीएल (WAVL) ट्री''' या कमजोर एवीएल ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष|स्व-संतुलन द्विआधारी विवृत्त ट्री]] है। डब्ल्यूएवीएल ट्री का नाम एवीएल ट्री  के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज ट्री है, और यह एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित है, जो सभी पद संतुलित ट्री के एक सामान्य ढांचे में आते हैं। अन्य संतुलित बाइनरी खोज ट्री की तरह, डब्ल्यूएवीएल ट्री प्रति संचालन {{math|''O''(log ''n'')}} समय में सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं। <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"/>
डब्ल्यूएवीएल ट्री को एवीएल ट्री लाल-काले ट्री दोनों के कुछ सर्वोत्तम गुणों को संयोजित करने के लिए प्ररूपित किया गया है। लाल-काले ट्री  की तुलना में एवीएल ट्री का एक लाभ यह है कि वे अधिक संतुलित होते हैं: उनकी अधिकतम ऊंचाई होती है <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"/>
Line 53: Line 53:
डब्ल्यूएवीएल ट्री में कुंजी {{mvar|k}} के साथ एक आंतरिक बिन्दु को सम्मिलित करने के लिए, ट्री में {{mvar|k}} की खोज की जाती है, जो एक बाह्य बिन्दु  पर समाप्त होती है, फिर उस बाह्य बिन्दु को दो बाह्य बच्चों के साथ नए आंतरिक बिन्दु से प्रतिस्थापित किया जाता है, और अंततः ट्री को संतुलित किया जाता है। संतुलनाधीन चरण को शीर्ष से नीचे तक या नीचे से शीर्ष तक किया जा सकता है लेकिन संतुलित करने का नीचे से शीर्ष तक वर्जन एवीएल ट्री के सबसे समीप होता है।
डब्ल्यूएवीएल ट्री में कुंजी {{mvar|k}} के साथ एक आंतरिक बिन्दु को सम्मिलित करने के लिए, ट्री में {{mvar|k}} की खोज की जाती है, जो एक बाह्य बिन्दु  पर समाप्त होती है, फिर उस बाह्य बिन्दु को दो बाह्य बच्चों के साथ नए आंतरिक बिन्दु से प्रतिस्थापित किया जाता है, और अंततः ट्री को संतुलित किया जाता है। संतुलनाधीन चरण को शीर्ष से नीचे तक या नीचे से शीर्ष तक किया जा सकता है लेकिन संतुलित करने का नीचे से शीर्ष तक वर्जन एवीएल ट्री के सबसे समीप होता है।


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


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


इस प्रकार, कुल मिलाकर, सम्मिलन प्रक्रिया में एक खोज, नए बिन्दु की एक निरंतर संख्या का निर्माण, पद  परिवर्तनों की एक लघुगणकीय संख्या और ट्री के घूर्णन की एक निरंतर संख्या सम्मिलित होती है।<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, लेकिन उपट्री  के कारण वह अंतर 1 से बढ़ गया है
बिन्दु   पर रूट छोटा हो गया है। यदि माता-पिता के पास अब दो बाहरी हैं
बच्चों, आंतरिक-बिन्दु   संपत्ति का उल्लंघन होता है क्योंकि माता-पिता
पद 2 है। माता-पिता को पदावनत किया जाना चाहिए, और पुनर्संतुलन जारी रखा जाना चाहिए
पैरेंट के साथ बिन्दु   के रूप में जो कि बहुत छोटे उपट्री की जड़ है।


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


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


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


एक डिलीट के परिणाम की तुलना करना सार्थक है जो एक एवीएल ट्री में कई स्तरों पर घुमाव का कारण बनता है और एक डब्ल्यूएवीएल ट्री में किए गए रोटेशन और पद परिवर्तनों के साथ। दूसरी छवि में मान 12 वाले बिन्दु   को हटा दिया गया है, इसके बाद दाएं घुमाव और सभी बाहरी बिन्दु ्स को शून्य पद  दिया गया है।
यह महत्वपूर्ण है कि एवीएल ट्री में कई स्तरों पर घुमाने वाले चक्रवात होने के कारण हटाने के परिणाम को डब्ल्यूएवीएल ट्री में किए गए चक्रवात और पद परिवर्तनों के साथ तुलना किया जाए। दूसरी छवि में, मान 12 वाले बिन्दु को हटा दिया गया है, इसके बाद दाएं घूमाने और सभी बाह्य बिन्दु को पद शून्य के रूप में निर्धारित किया गया है।
   [[File:FibonacciTreeWRanks.png|thumb|पद ों के साथ फाइबोनैचि ट्री ]] [[File:Fibonacci Tree after Delete.png|thumb|हटाने के बाद पद  के साथ फाइबोनैचि ट्री ]]
   [[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'')}}.
डब्ल्यूएवीएल ट्री में प्रत्येक खोज, सम्मिलन या विलोपन में ट्री में एक ही पथ का अनुसरण करना और पथ में प्रत्येक बिन्दु  के लिए निरंतर चरणों का पालन करना सम्मिलित  है। एक डब्ल्यूएवीएल ट्री  में {{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'')}}.


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


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


===एवीएल ट्री ===
===एवीएल ट्री ===
एवीएल ट्री एक प्रकार का संतुलित बाइनरी सर्च ट्री है जिसमें प्रत्येक आंतरिक बिन्दु   के दो बच्चों की ऊंचाई अधिकतम एक से भिन्न होनी चाहिए।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, Section 4.2 AVL Trees, pp. 120–125.</ref> किसी बाहरी बिन्दु   की ऊंचाई शून्य है, और किसी भी आंतरिक बिन्दु   की ऊंचाई हमेशा उसके दो बच्चों की ऊंचाई से एक प्लस अधिक होती है। इस प्रकार, एवीएल ट्री की ऊंचाई फलन डब्ल्यूएवीएल ट्री की बाधाओं का पालन करती है, और हम प्रत्येक बिन्दु   की ऊंचाई को उसके पद के रूप में उपयोग करके किसी भी एवीएल ट्री को डब्ल्यूएवीएल ट्री में परिवर्तित कर सकते हैं।<ref name="gt"/><ref name="hst15"/>
<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" />


एवीएल ट्री और डब्ल्यूएवीएल ट्री के बीच मुख्य अंतर तब उत्पन्न होता है जब एक बिन्दु  में समान पद या ऊंचाई वाले दो चाइल्ड  होते हैं। एवीएल ट्री में, यदि एक बिन्दु  {{mvar|x}} के एक ही कद के दो चाइल्ड  हैं {{mvar|h}} एक दूसरे के रूप में, तो की ऊंचाई {{mvar|x}} बिलकुल होना चाहिए {{math|''h'' + 1}}. इसके विपरीत, डब्ल्यूएवीएल ट्री में, यदि एक node {{mvar|x}} के एक ही पद  के दो चाइल्ड  हैं {{mvar|r}} एक दूसरे के रूप में, फिर की पद  {{mvar|x}} या तो किया जा सकता है {{math|''r'' + 1}} या {{math|''r'' + 2}}. ऐसा इसलिए है क्योंकि डब्ल्यूएवीएल ट्री में पद  पूरी तरह से ऊंचाई के बराबर नहीं है। पद ों में इस अधिक लचीलेपन से संरचनाओं में भी अधिक लचीलापन आता है: कुछ डब्ल्यूएवीएल ट्री को उनके पद ों को संशोधित करके भी एवीएल ट्री  में नहीं बनाया जा सकता है, क्योंकि उनमें ऐसे बिन्दु  शामिल होते हैं जिनके बच्चों की ऊंचाई एक से अधिक भिन्न होती है।<ref name="hst15"/>हालाँकि, हम कह सकते हैं कि सभी एवीएल ट्री  डब्ल्यूएवीएल ट्री  हैं। एवीएल ट्री  बिना किसी प्रकार के बिन्दु  वाले डब्ल्यूएवीएल ट्री  हैं जिनके दोनों बच्चों की पद  में अंतर 2 है।<ref name="gt" />
यदि एक डब्ल्यूएवीएल ट्री केवल सम्मिलन संचालन का उपयोग करके बनाया गया है, तो इसकी संरचना समान सम्मिलन अनुक्रम द्वारा बनाए गए एवीएल ट्री की संरचना के समान होगी, और इसकी पद संबंधित एवीएल ट्री की पद के समान होगी। केवल विलोपन कार्यों के माध्यम से ही एक डब्ल्यूएवीएल ट्री एक एवीएल ट्री से भिन्न हो सकता है। विशेष रूप से इसका तात्पर्य यह है कि केवल सम्मिलन के माध्यम से बनाए गए डब्ल्यूएवीएल ट्री की ऊंचाई अधिकतम होती है <math>\log_{\varphi} n\approx 1.44\log_2 n</math> तक होती है।<ref name="hst15" />


यदि एक डब्ल्यूएवीएल ट्री केवल सम्मिलन संचालन का उपयोग करके बनाया गया है, तो इसकी संरचना समान सम्मिलन अनुक्रम द्वारा बनाए गए एवीएल ट्री  की संरचना के समान होगी, और इसकी पद  संबंधित एवीएल ट्री  की पद  के समान होगी। केवल विलोपन कार्यों के माध्यम से ही एक डब्ल्यूएवीएल ट्री  एक एवीएल ट्री  से भिन्न हो सकता है। विशेष रूप से इसका तात्पर्य यह है कि केवल सम्मिलन के माध्यम से बनाए गए डब्ल्यूएवीएल ट्री  की ऊंचाई अधिकतम होती है <math>\log_{\varphi} n\approx 1.44\log_2 n</math>.<ref name="hst15"/>




===लाल-काले ट्री ===
===लाल-काले ट्री ===
लाल-काला ट्री एक संतुलित बाइनरी खोज ट्री है जिसमें प्रत्येक बिन्दु   का एक रंग (लाल या काला) होता है, जो निम्नलिखित गुणों को संतुष्ट करता है:
लाल-काला ट्री एक संतुलित बाइनरी खोज ट्री है जिसमें प्रत्येक बिन्दु का एक रंग होता है, जो निम्नलिखित गुणों को संतुष्ट करता है:
* बाहरी बिन्दु ्स काले हैं.
* बाहरी बिन्दु काले हैं.
* यदि कोई आंतरिक बिन्दु   लाल है, तो उसके दोनों चाइल्ड   काले हैं।
* यदि कोई आंतरिक बिन्दु लाल है, तो उसके दोनों चाइल्ड काले हैं।
* रूट से बाहरी बिन्दु   तक के सभी पथों में समान संख्या में ब्लैक बिन्दु   होते हैं।
* रूट से बाहरी बिन्दु तक के सभी पथों में समान संख्या में काले बिन्दु होते हैं।
लाल-काले ट्री  को समान रूप से बिन्दु ्स पर संग्रहीत पद ों की एक प्रणाली के संदर्भ में परिभाषित किया जा सकता है, जो निम्नलिखित आवश्यकताओं को पूरा करता है (डब्ल्यूएवीएल ट्री  में पद ों की आवश्यकताओं से भिन्न):
लाल-काले ट्री  को समान रूप से बिन्दु पर संग्रहीत पद की एक प्रणाली के संदर्भ में परिभाषित किया जा सकता है, जो निम्नलिखित आवश्यकताओं को पूरा करता है।
* बाहरी बिन्दु   की पद  हमेशा 0 होती है और उसके मूल बिन्दु   की पद हमेशा 1 होती है।
* बाहरी बिन्दु की पद  हमेशा 0 होती है और उसके मूल बिन्दु की पद 1 होती है।
* किसी भी गैर-रूट बिन्दु   की पद  या तो उसके मूल बिन्दु   की पद या उसके मूल बिन्दु   की पद माइनस 1 के बराबर होती है।
* किसी भी गैर-रूट बिन्दु की पद  या तो उसके मूल बिन्दु की पद या उसके मूल बिन्दु की पद - 1 के बराबर होती है।
* किसी भी जड़-पत्ती पथ पर लगातार दो किनारों में पद अंतर 0 नहीं होता है।
* किसी भी जड़-पत्ती पथ पर लगातार दो किनारों में पद अंतर 0 नहीं होता है।
रंग-आधारित और पद -आधारित परिभाषाओं के बीच समानता को एक दिशा में, एक बिन्दु   को काले रंग से देखा जा सकता है यदि उसके मूल की पद अधिक है और लाल रंग से यदि उसके मूल की पद  समान है। दूसरी दिशा में, किसी बाहरी बिन्दु   के किसी भी पथ पर काले बिन्दु   की पद को काले बिन्दु