WAVL ट्री

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

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

WAVL वृक्षों की शुरुआत किसके द्वारा की गई थी? Haeupler, Sen & Tarjan (2015). उन्हीं लेखकों ने एवीएल पेड़ों, डब्ल्यूएवीएल पेड़ों और लाल-काले पेड़ों के बारे में एक सामान्य दृष्टिकोण भी प्रदान किया, क्योंकि ये सभी एक प्रकार के रैंक-संतुलित पेड़ हैं।

रैंक संतुलित वृक्ष रूपरेखा

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

रैंक बाइनरी ट्री एक बाइनरी ट्री है जहां प्रत्येक नोड x एक रैंक r(x) से जुड़ा होता है। परंपरा के अनुसार, खाली नोड की रैंक -1 होती है। एक नोड x के लिए जो रूट नहीं है, रैंक अंतर है $r(p(x))-r(x)$, और यदि रैंक अंतर i है तो ऐसे नोड को आई-चाइल्ड कहा जाता है। एक नोड प्रकार का होता है $i,j$ यदि इसके बाएं बच्चे और दाएं बच्चे की रैंक का अंतर i और j है (आदेश की परवाह किए बिना)।

इसके साथ, हम अतिरिक्त नियम परिभाषित कर सकते हैं, जो विभिन्न पेड़ों से मेल खाते हैं:

• AVL नियम, जो AVL ट्री से मेल खाता है: प्रत्येक नोड प्रकार 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-नोड सही है.

कमज़ोर AVL वृक्ष को कमज़ोर AVL नियम द्वारा परिभाषित किया गया है:

• कमजोर एवीएल नियम: सभी रैंक अंतर 1 या 2 हैं, और सभी लीफ नोड्स की रैंक 0 है।

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

परिभाषा

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

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

संचालन

खोज रहा हूँ

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

सम्मिलन

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

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

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

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

विलोपन

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

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

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

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

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

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

रैंकों के साथ फाइबोनैचि वृक्ष

हटाने के बाद रैंक के साथ फाइबोनैचि वृक्ष

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

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

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

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

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

एवीएल पेड़

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

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

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

लाल-काले पेड़

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

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

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

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

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

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