लाल-काला ट्री: Difference between revisions

लाल-काले ट्री
लाल-काले ट्री
Type	ट्री
Invented	1972
Invented by	रुडोल्फ बेयर
Complexities in big O notation
Space
Space complexity
Space
Time complexity
Function
Search
Insert
Delete

Latest revision as of 12:43, 28 July 2023

अभिकलित्र विज्ञान में, लाल-काले ट्री एक विशेष द्विभाजी अन्वेषण ट्री डेटा संरचना है जो तीव्रता से भंडारण और क्रमित की गई जानकारी की पुनर्प्राप्ति के लिए जाना जाता है और यह आश्वासन देता है कि संचालन एक ज्ञात समय के भीतर पूर्ण हो जाएगा। अन्य स्व-संतुलन द्विभाजी अन्वेषण ट्री की तुलना में, लाल-काले ट्री में नोड्स में "रंग" नामक एक अतिरिक्त बिट होता है जो "लाल" और "काले" का प्रतिनिधित्व करता है जिसका उपयोग ट्री को पुन: व्यवस्थित करते समय यह सुनिश्चित करने के लिए किया जाता है कि यह सदैव लगभग संतुलित रहता है। ^[3]

जब ट्री को संशोधित किया जाता है, तो नए ट्री को पुन: व्यवस्थित किया जाता है और रंग गुणों को पुनः स्थापित करने के लिए "पुनः रंगा" जाता है जो कि सबसे खराब स्थिति में ट्री कितना असंतुलित हो सकता है,उसे रोकता है। गुणों को इस प्रकार रूपांकित किया गया है कि यह पुनर्व्यवस्थित करना और पुनः रंगना कुशलतापूर्वक किया जा सकता है।

(पुनः) संतुलन सही नहीं है, परन्तु बड़े O समय $O(\log n)$ में अन्वेषण की प्रत्याभूति देता है, जहाँ $n$ ट्री में प्रविष्टियों (या कुंजियों) की संख्या है। ट्री को पुनर्व्यवस्थित करने और पुन: रंगने के साथ-साथ, $O(\log n)$ समय को सम्मिलित करने और हटाने की क्रिया भी की जाती है।^[4]

प्रत्येक नोड के रंग को पथानुसरण करने के लिए प्रति नोड केवल एक बिट जानकारी की आवश्यकता होती है क्योंकि केवल दो रंग होते हैं। ट्री में लाल-काले ट्री होने के कारण विशिष्ट कोई अन्य डेटा सम्मिलित नहीं है, इसलिए इसकी मेमोरी पदचिन्ह उत्कृष्ट (बिना रंग वाले) द्विभाजी अन्वेषण ट्री के लगभग समान है। कुछ स्थितियों में, अतिरिक्त जानकारी को बिना किसी अतिरिक्त मेमोरी लागत के संग्रहीत किया जा सकता है।

इतिहास

1972 में, रूडोल्फ बायर^[5] ने एक डेटा संरचना का आविष्कार किया जो B-ट्री की एक विशेष अनुक्रम-4 स्थिति थी। इन ट्रीज ने समान संख्या में नोड्स के साथ मूल से पर्ण तक सभी पथों को बनाए रखा, जिससे पूर्णतया संतुलित ट्री बने। हालाँकि, वे द्वयी अन्वेषण ट्री नहीं थे। बायर ने अपने पत्र में उन्हें "सममित द्वयी बी-ट्री" कहा और बाद में वे 2-3-4 ट्री या केवल 2-4 ट्री के रूप में लोकप्रिय हो गए।^[6]

1978 के एक पत्र में, संतुलित ट्रीज़ के लिए एक द्विवर्णी रूपरेखा,^[7] लियोनिदास जे. गुइबास और रॉबर्ट सेडगेविक (अभिकलित्र वैज्ञानिक) ने सममित द्वयी बी-ट्री से लाल-काले ट्री की उत्पत्ति की।^[8] लाल रंग इसलिए चुना गया क्योंकि यह प्रतिलिपि पीआरएसी में कार्य करने के पर्यन्त लेखकों के लिए उपलब्ध रंगीन लेजर मुद्रक द्वारा निर्मित सबसे अच्छा दिखने वाला रंग था।^[9] गुइबास की एक अन्य प्रतिक्रिया में कहा गया है कि यह ट्री को चित्रित करने के लिए उनके पास उपलब्ध लाल और काले लेखनियों के कारण था।^[10]

1993 में, अर्ने एंडर्सन ने सम्मिलित करने और हटाने के संचालन को सरल बनाने के लिए दाएं झुकाव वाले ट्री का विचार प्रस्तुत किया।^[11]

1999 में, क्रिस ओकासाकी ने दर्शाया कि निविष्ट संचालन को पूर्णतया कार्यात्मक कैसे बनाया जाए। इसके संतुलन कार्य को केवल 4 असंतुलित स्थितियों और एक व्यतिक्रम संतुलित स्थितियों की ध्यान रखने की आवश्यकता है।^[12]

मूल कलन विधियों में 8 असंतुलित स्थितियों का उपयोग किया गया था, परन्तु कॉर्मेन एट अल. (2001) इसे घटाकर 6 असंतुलित स्थिति कर दिया।^[3]सेडगेविक ने दर्शाया कि निविष्ट संचालन को जावा (प्रोग्रामिंग भाषा) कोड की केवल 46 पंक्तियों में अनुप्रयुक्त किया जा सकता है।^[13]^[14]2008 में, सेडगेविक ने एंडर्सन के विचार का लाभ उठाते हुए बाएं झुकाव वाले लाल-काले ट्री का प्रस्ताव रखा, जिसने सम्मिलित करने और हटाने के संचालन को सरल बना दिया। सेडगेविक ने मूल रूप से ऐसे नोड्स की अनुमति दी थी जिनके दो बच्चे लाल हैं, जिससे उनके ट्री 2-3-4 ट्री की तरह हो गए, परन्तु बाद में यह प्रतिबंध जोड़ा गया, जिससे नए ट्री 2-3 ट्री की तरह बन गए। सेडगेविक ने निविष्ट कलन विधि को केवल 33 पंक्तियों में अनुप्रयुक्त किया, जिससे कोड की उनकी मूल 46 पंक्तियाँ काफी छोटी हो गईं।^[15]^[16]

शब्दावली

लाल-काले ट्री का उदाहरण

चित्र 1: ...स्पष्ट शून्य पर्णो के साथ

चित्र 2: ... अंतर्निहित बाएँ और दाएँ संलगनी बिंदुओं के साथ

लाल-काले ट्री एक विशेष प्रकार का द्विभाजी अन्वेषण ट्री है, जिसका उपयोग अभिकलित्र विज्ञान में तुलनीय डेटा के खंडों को व्यवस्थित करने के लिए किया जाता है, जैसे कि पाठ के खंड या संख्याएं (उदाहरण के लिए आंकड़े 1 और 2 में संख्याएं) है। कुंजी और/या डेटा ले जाने वाले नोड्स को प्रायः "आंतरिक नोड" कहा जाता है, परन्तु इसे बहुत विशिष्ट बनाने के लिए उन्हें इस आलेख में गैर-शून्य नोड भी कहा जाता है।

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

पथ के इन अंत वस्तुओं को "रंग" का श्रेय देना वास्तव में आवश्यक नहीं है, क्योंकि NIL या BLACK स्थिति NIL से निहित है (यह टिप्पणी भी देखें)।

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

इसके बजाय, निष्पादन समय की सीमांत राशि बचाने के लिए, इन (संभवतः कई) शून्य पर्णो को एक अद्वितीय (और काले) प्रहरी नोड (मान शून्य के संकेतक के बजाय) के संकेतक के रूप में अनुप्रयुक्त किया जा सकता है।

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

किसी नोड की काली गहराई को मूल से उस नोड तक काले नोड्स की संख्या (अर्थात काले पूर्वजों की संख्या) के रूप में परिभाषित किया गया है। लाल-काले ट्री की काली ऊंचाई मूल से पर्णो तक किसी भी पथ में काले नोड की संख्या है, जो, आवश्यकता 4 के अनुसार, स्थिर है (वैकल्पिक रूप से, इसे किसी भी पर्ण नोड की काली गहराई के रूप में परिभाषित किया जा सकता है)।^[17]^{: 154–165}किसी नोड की काली ऊँचाई उसके द्वारा मूलित उप-ट्री की काली ऊँचाई है। इस आलेख में, शून्य नोड की काली ऊंचाई 0 पर निर्धारित की जाएगी, क्योंकि इसका उप-ट्री रिक्त है जैसा कि चित्र 2 में सुझाया गया है और इसकी ट्री की ऊंचाई भी 0 है।

गुणधर्म

द्वयी अन्वेषण ट्री पर लगाई गई आवश्यकताओं के अतिरिक्त निम्नलिखित को लाल-काले ट्री द्वारा संतुष्ट किया जाना चाहिए:red–black tree:^[18]

प्रत्येक नोड या तो लाल या काले है।
सभी शून्य नोड (चित्र 1) को काला माना जाता है।
लाल नोड में लाल बच्चा नहीं होता है।
किसी दिए गए नोड से उसके किसी भी वंशज शून्य नोड तक का प्रत्येक पथ समान संख्या में काले नोड से होकर गुजरता है।
(निष्कर्ष) यदि नोड N में बिल्कुल एक बच्चा है, तो यह एक लाल बच्चा होना चाहिए, क्योंकि यदि यह काला होता, तो इसके शून्य वंशज N के शून्य बच्चे की तुलना में एक अलग काली गहराई पर बैठेंगे, जो आवश्यकता 4 का उल्लंघन करेगा।

कुछ लेखक, उदाहरण के लिए: कॉर्मेन और अन्य,^[18]पांचवीं आवश्यकता के रूप में अनुरोध करें कि मूल काली है; परन्तु मेहलहॉर्न और सैंडर्स ^[17]या सेडगेविक और वेन नहीं है।^[16]^{: 432–447} चूँकि मूल को सदैव लाल से काले में परिवर्तित किया जा सकता है, इस नियम का विश्लेषण पर बहुत कम प्रभाव पड़ता है। यह आलेख इसे भी छोड़ देता है, क्योंकि यह पुनरावर्ती कलन विधियों और प्रमाणों को थोड़ा विक्षुब्ध करता है।

उदाहरण के तौर पर, प्रत्येक पूर्ण द्वयी ट्री जिसमें केवल काले नोड होते हैं, एक लाल-काला ट्री होता है।

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

आवश्यकताएँ लाल-काले ट्रीज के एक महत्वपूर्ण गुणधर्म को अनुप्रयुक्त करते हैं: मूल से सबसे दूर के पर्ण तक का रास्ता मूल से निकटतम पर्ण तक के रास्ते से दोगुने से अधिक लंबा नहीं होता है। परिणाम यह है कि ट्री ऊंचाई-संतुलित द्विभाजी अन्वेषण ट्री है। चूंकि मान डालने, हटाने और $h$ ट्री की खोजने जैसे कार्यों के लिए ऊंचाई के अनुपात में सबसे खराब स्थिति वाले समय की आवश्यकता होती है, ऊंचाई पर यह ऊपरी सीमा लाल-काले ट्रीज को सबसे खराब स्थिति में कुशल होने की अनुमति देती है, अर्थात् संख्या में लघुगणक $n$ प्रविष्टियों में से,अर्थात, $h\in O(\log n)$ , जो सामान्य द्विभाजी अन्वेषण ट्री के स्थिति में नहीं है। गणितीय प्रमाण के लिए सीमा का प्रमाण अनुभाग देखें।

लाल-काले ट्री, सभी द्विभाजी अन्वेषण ट्री की तरह, अपने तत्वों की काफी कुशल अनुक्रमिक अधिगमन (उदाहरण के लिए अनुक्रम में पथक्रमण, अर्थात बाएं-मूल-दाएं क्रम में) की अनुमति देते हैं। परन्तु वे मूल से पर्ण तक पथक्रमण के माध्यम से स्पर्शोन्मुख रूप से इष्टतम प्रत्यक्ष अभिगम का भी समर्थन करते हैं, जिसके परिणामस्वरूप $O(\log n)$ अन्वेषण समय है।

क्रम 4 के B-ट्री की सादृश्यता

चित्र 3: ऊपर के उदाहरण जैसा ही लाल-काला ट्री, अब B-ट्री के रूप में

एक लाल-काले ट्री संरचना में क्रम 4 के B-ट्री के समान होता है,^[19] जहां प्रत्येक नोड में 1 और 3 मान और (तदनुसार) 2 और 4 संतान संकेतक के मध्य हो सकते हैं। ऐसे B-ट्री में, प्रत्येक नोड में लाल-काले ट्री के काले नोड में मान से मेल खाने वाला केवल एक मान होगा, एक ही नोड में इसके पहले और/या बाद में एक वैकल्पिक मान होगा, दोनों लाल-काले ट्री एक समान लाल नोड से मेल खाएंगे।

इस तुल्यता को देखने का एक तरीका लाल-काले ट्री के आलेखीय प्रतिनिधित्व में लाल नोड को ऊपर ले जाना है, ताकि वे एक क्षैतिज गुच्छ बनाकर, अपने मूल काले नोड के साथ क्षैतिज रूप से संरेखित हों। B-ट्री में, या लाल-काले ट्री के संशोधित आलेखीय प्रतिनिधित्व में, सभी पर्ण नोड एक ही गहराई पर हैं।

लाल-काले ट्री तब संरचनात्मक रूप से क्रम 4 के B-ट्री के बराबर होता है, जिसमें 3 मानों की अधिकतम क्षमता के साथ प्रति गुच्छ 33% मानों का न्यूनतम भरण कारक होता है।

हालाँकि, यह B-ट्री प्रकार अभी भी लाल-काले ट्री की तुलना में अधिक सामान्य है, क्योंकि यह लाल-काले ट्री के रूपांतरण में अस्पष्टता की अनुमति देता है - क्रम 4 के समकक्ष B-ट्री से कई लाल-काले ट्री का उत्पादन किया जा सकता है (चित्र 3 देखें)। यदि B-ट्री गुच्छ में केवल 1 मान है, तो यह न्यूनतम, काला है और इसमें दो संतान संकेतक हैं। यदि किसी गुच्छ में 3 मान हैं, तो केंद्रीय मान काला होगा और उसके किनारों पर संग्रहीत प्रत्येक मान लाल होगा। हालाँकि, यदि गुच्छ में दो मान हैं, तो उनमें से कोई भी लाल-काले ट्री में काला नोड बन सकता है (और दूसरा लाल होगा)।

तो अनुक्रम-4 B-ट्री यह नहीं बनाए रखता है कि प्रत्येक गुच्छ में कौन सा मान सम्पूर्ण गुच्छ के लिए मूल काला ट्री है और उसी गुच्छ में अन्य मानों का जनक है। इसके बावजूद, लाल-काले ट्री पर परिचालन समय की स्थिति में अधिक किफायती है क्योंकि आपको मानों के सदिश को बनाए रखने की आवश्यकता नहीं है।^[20] यदि मानों को संदर्भ द्वारा संग्रहीत करने के बजाय सीधे प्रत्येक नोड में संग्रहीत किया जाता है तो यह महंगा हो सकता है। हालाँकि, बी-ट्री नोड समष्टि में अधिक किफायती हैं क्योंकि आपको प्रत्येक नोड के लिए रंग विशेषता को संग्रहीत करने की आवश्यकता नहीं है। इसके बजाय, आपको यह जानना होगा कि गुच्छ सदिश में किस खाँच का उपयोग किया जाता है। यदि मान संदर्भ द्वारा संग्रहीत किए जाते हैं, उदाहरण के लिए: वस्तुओं, शून्य संदर्भों का उपयोग किया जा सकता है और इसलिए गुच्छ को एक सदिश द्वारा दर्शाया जा सकता है जिसमें मान संकेतकों के लिए 3 खाँच और ट्री में बाल संदर्भों के लिए 4 खाँच होते हैं। उस स्थिति में, B-ट्री मेमोरी में अधिक सघन हो सकते है, जिससे डेटा स्थानीयता में सुधार हो सकता है।

वही सादृश्य बड़े अनुक्रम वाले B-ट्री के साथ बनाया जा सकता है जो संरचनात्मक रूप से रंगीन द्वयी ट्री के बराबर हो सकते हैं: आपको केवल अधिक रंगों की आवश्यकता है। मान लीजिए कि आप नीला जोड़ते हैं, तो नीला-लाल-काला ट्री लाल-काले ट्री की तरह परिभाषित होता है परन्तु अतिरिक्त बाधा के साथ कि पदानुक्रम में कोई भी दो क्रमिक नोड नीले नहीं होंगे और सभी नीले नोड लाल नोड के बच्चे होंगे, तो यह एक B-ट्री के बराबर हो जाता है जिसके गुच्छ में निम्नलिखित रंगों में अधिकतम 7 मान होंगे: नीला, लाल, नीला, काला, नीला, लाल, नीला (प्रत्येक गुच्छ के लिए, अधिकतम 1 काले नोड, 2 लाल नोड और 4 नीले नोड) होंगे।

मानों की मध्यम मात्रा के लिए, रंगीन द्वयी ट्री में सम्मिलन और विलोपन बी-ट्री की तुलना में तीव्र होते हैं क्योंकि रंगीन ट्री नोड के प्रत्येक क्षैतिज गुच्छ के भरण कारक को अधिकतम करने का प्रयास नहीं करते हैं (रंगीन द्वयी में केवल न्यूनतम भरण कारक की प्रत्याभूति होती है) ट्री, समूहों के विभाजन या समागमों की संख्या को सीमित करते हुए)। B-ट्री, घूर्णन करने के लिए तीव्र होंगे (क्योंकि रंगीन द्वयी ट्री में कई अलग-अलग नोड के बजाय घूर्णन प्रायः एक ही गुच्छ के भीतर होंगे)। हालाँकि, बड़ी मात्रा में भंडारण के लिए, B-ट्री बहुत तीव्र होंगे क्योंकि वे एक ही गुच्छ में कई बच्चों को समूहित करके अधिक सघन होंगे जहाँ उन्हें स्थानीय रूप से पहुँचा जा सकता है।

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

अनुप्रयोग और संबंधित डेटा संरचनाएँ

लाल-काले ट्री सम्मिलन समय, विलोपन समय और अन्वेषण समय के लिए सबसे खराब स्थिति की प्रत्याभूति देते हैं। यह न केवल उन्हें वास्तविक समय अनुप्रयोगों जैसे समय-संवेदनशील अनुप्रयोगों में मूल्यवान बनाता है, बल्कि यह उन्हें अन्य डेटा संरचनाओं में मूल्यवान इमारती खंड बनाता है जो सबसे खराब स्थिति की प्रत्याभूति प्रदान करते हैं; उदाहरण के लिए, अभिकलनात्मक ज्यामिति में उपयोग की जाने वाली कई डेटा संरचनाएं लाल-काले ट्रीज पर आधारित हो सकती हैं और वर्तमान लिनक्स कर्नेल और ईपोल प्रणाली कॉल कार्यान्वयन में उपयोग किए जाने वाले पूर्णतया निष्पक्ष अनुसूचक लाल-काले ट्रीज का उपयोग करता है।^[21]

एवीएल ट्री एक अन्य संरचना $O(\log n)$ खोज, सम्मिलन, और निष्कासन समर्थन का करता है। एवीएल ट्रीज का रंग लाल-काला हो सकता है, इस प्रकार ये आरबी ट्री का एक उपसमूह हैं। सबसे खराब स्थिति वाली ऊंचाई आरबी ट्रीज की सबसे खराब स्थिति वाली ऊंचाई का 0.720 गुना है, इसलिए एवीएल ट्री अधिक कठोरता से संतुलित होते हैं। 79 रनों में यथार्थवादी परीक्षण स्थितियों के साथ बेन पफैफ के प्रदर्शन माप में एवीएल से आरबी अनुपात 0.677 और 1.077 के मध्य, माध्यिका 0.947 और ज्यामितीय माध्य 0.910 पाया गया।^[22] डब्ल्यूएवीएल ट्रीज का प्रदर्शन उन दोनों के मध्य में होता है।

लाल-काले ट्री कार्यात्मक प्रोग्रामिंग में भी विशेष रूप से मूल्यवान हैं, जहां वे सबसे सामान्य सतत डेटा संरचनाओं में से एक हैं, जिनका उपयोग सहयोगी सरणी और समूह बनाने के लिए किया जाता है जो उत्परिवर्तन के बाद पिछले संस्करणों को बनाए रख सकते हैं। लाल-काले ट्री के सतत संस्करण समय के अतिरिक्त, प्रत्येक प्रविष्टि या विलोपन के लिए $O(\log n)$ समष्टि की आवश्यकता होती है।

प्रत्येक 2-4 ट्री के लिए, समान क्रम में डेटा तत्वों के साथ संबंधित लाल-काले ट्री होते हैं। 2-4 ट्री पर सम्मिलन और विलोपन संचालन भी लाल-काले ट्रीज में रंग-फ़्लिपिंग और घूर्णन के बराबर हैं। यह 2-4 ट्रीज को लाल-काले ट्री के पीछे के तर्क को समझने के लिए एक महत्वपूर्ण उपकरण बनाता है और यही कारण है कि कई परिचयात्मक कलन विधि पाठ लाल-काले ट्री से ठीक पहले 2-4 ट्रीज का परिचय देते हैं, हालाँकि व्यवहार में 2-4 ट्रीज का प्रायः उपयोग नहीं किया जाता है।

2008 में, सेडगेविक ने कार्यान्वयन में स्वतंत्रता की पहले से अनिर्दिष्ट डिग्री को समाप्त करके लाल-काले ट्री का एक सरल संस्करण प्रस्तुत किया, जिसे बाएं-झुकाव वाला लाल-काला ट्री कहा जाता है।^[23] एलएलआरबी एक अतिरिक्त अपरिवर्तनीयता बनाए रखता है कि सभी लाल लिंक को सम्मिलित करने और हटाने के अतिरिक्त बाईं ओर झुकना चाहिए। संचालन के किसी भी क्रम के लिए लाल-काले ट्रीज को 2-3 ट्रीज,^[24] या 2-4 ट्रीज,^[23]के बराबर बनाया जा सकता है। 2-4 ट्रीज समदूरीकता का वर्णन 1978 में सेडगेविक द्वारा किया गया था।^[7]2-4 ट्री के साथ, समदूरीकता को एक विभाजन के अनुरूप "रंग फ्लिप" द्वारा हल किया जाता है, जिसमें दो बच्चों के नोड का लाल रंग बच्चों को छोड़ देता है और मूल नोड में चला जाता है।

टैंगो ट्री का मूल विवरण, तीव्र खोजों के लिए अनुकूलित एक प्रकार का ट्री, विशेष रूप से अपने डेटा संरचना के भाग के रूप में लाल-काले ट्रीज का उपयोग करता है।^[25]

जावा (प्रोग्रामिंग भाषा) 8 के अनुसार, हैश तालिका को ऐसे संशोधित किया गया है कि कि अलग-अलग तत्वों को संयोजनट्टनी हैशकोड के साथ संग्रहीत करने के लिए श्रृंखलित सूची का उपयोग करने के बजाय, एक लाल-काले ट्री का उपयोग किया जाता है। इसके परिणामस्वरूप ऐसे तत्व $O(m)$ से $O(\log m)$ को खोजने की समय जटिलता में सुधार होता है, जहाँ $m$ संयोजनट्टनी हैशकोड वाले तत्वों की संख्या है।^[26]

संचालन

लाल-काले ट्री पर अन्वेषण या ट्री पथक्रमण जैसे केवल पढ़ने योग्य संचालन को द्वयी अन्वेषण ट्री के लिए उपयोग किए जाने वाले संचालन से किसी संशोधन की आवश्यकता नहीं होती है, क्योंकि प्रत्येक लाल-काले ट्री एक साधारण द्वयी अन्वेषण ट्री की एक विशेष स्थिति है। हालाँकि, सम्मिलन या निष्कासन का तत्काल परिणाम लाल-काले ट्री के गुणों का उल्लंघन कर सकता है, जिसके पुनःस्थापन को पुनर्संतुलन कहा जाता है ताकि लाल-काले ट्री स्व-संतुलन बन जाएं।सबसे खराब स्थिति में इसके लिए एक छोटी संख्या, $O(\log n)$ की आवश्यकता होती है। बड़े O संकेत पद्धति में, जहाँ $n$ ट्री में औसतन या परिशोधित वस्तुओं की संख्या $O(1)$ है, एक स्थिर संख्या,^[27]^: 310 ^[17]^: 158 रंग परिवर्तन (जो व्यवहार में बहुत तीव्र होते हैं); और तीन से अधिक ट्री चक्र नहीं^[28] (प्रविष्टि के लिए दो) है।

यदि नीचे दिया गया उदाहरण कार्यान्वयन उपयुक्त नहीं है, तो स्पष्टीकरण के साथ अन्य कार्यान्वयन बेन पफैफ के^[29] एनोटेटेड C लाइब्रेरी जीएनयू लिबाव्ल (जून 2019 तक वी2.0.3) में पाए जा सकते हैं।

अन्तर्स्थापित करने और हटाने के संचालन का विवरण उदाहरण, सी++ कोड के साथ प्रदर्शित किया जाएगा, जो प्रकार परिभाषाओं, नीचे दिए गए मैक्रो और क्रमावर्तन के लिए सहायक फलन का उपयोग करता है:

// Basic type definitions:

enum color_t { BLACK, RED };

struct RBnode {     // node of red–black tree
  RBnode* parent;   // == NIL if root of the tree
  RBnode* child[2]; // == NIL if child is empty
    // The index is:
    //   LEFT  := 0, if (key < parent->key)
    //   RIGHT := 1, if (key > parent->key)
  enum color_t color;
  int key;
};

#define NIL   NULL // null pointer  or  pointer to sentinel node
#define LEFT  0
#define RIGHT 1
#define left  child[LEFT]
#define right child[RIGHT]

struct RBtree { // red–black tree
  RBnode* root; // == NIL if tree is empty
};

// Get the child direction (∈ { LEFT, RIGHT })
//   of the non-root non-NIL  RBnode* N:
#define childDir(N) ( N == (N->parent)->right ? RIGHT : LEFT )

बाएं घूर्णन और
दायां घूर्णन, एनिमेटेड।

RBnode* RotateDirRoot(
    RBtree* T,   // red–black tree
    RBnode* P,   // root of subtree (may be the root of T)
    int dir) {   // dir ∈ { LEFT, RIGHT }
  RBnode* G = P->parent;
  RBnode* S = P->child[1-dir];
  RBnode* C;
  assert(S != NIL); // pointer to true node required
  C = S->child[dir];
  P->child[1-dir] = C; if (C != NIL) C->parent = P;
  S->child[  dir] = P; P->parent = S;
  S->parent = G;
  if (G != NULL)
    G->child[ P == G->right ? RIGHT : LEFT ] = S;
  else
    T->root = S;
  return S; // new root of subtree
}

#define RotateDir(N,dir) RotateDirRoot(T,N,dir)
#define RotateLeft(N)    RotateDirRoot(T,N,LEFT)
#define RotateRight(N)   RotateDirRoot(T,N,RIGHT)

प्रतिदर्श कोड और प्रविष्टि और निष्कासन के आरेख पर टिप्पणी

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

एक लाल नोड और एक (गैर-शून्य) काले नोड (काली ऊंचाई ≥ 1) का प्रतीक है, गैर-शून्य नोड के लाल या काले रंग का प्रतीक है, परन्तु एक ही आरेख में एक ही रंग है। आरेखों में शून्य नोड्स का प्रतिनिधित्व नहीं किया गया है।
चर N वर्तमान नोड को दर्शाता है, जिसे आरेखों में N या N लेबल किया गया है।
एक आरेख में तीन स्तम्भ और दो से चार क्रियाएं होती हैं। बायां स्तम्भ पहले पुनरावृत्ति को दर्शाता है, दायां स्तम्भ उच्च पुनरावृत्तियों को दर्शाता है, मध्य स्तम्भ किसी स्थिति के विभाजन को उसके विभिन्न कार्यों में दर्शाता है।^[30]

क्रिया "प्रविष्टि" नोड्स के समूह को उनके रंगों के साथ दर्शाती है जो एक स्थिति को परिभाषित करती है और अधिकतर कुछ आवश्यकताओं का उल्लंघन करती है।
एक नीली पट्टी वर्तमान नोड N को वलय करती है और अन्य नोड्स को N के साथ उनके संबंध के अनुसार लेबल किया जाता है।
यदि एक घूर्णन को उपयोगी माना जाता है, तो इसे अगली क्रिया में चित्रित किया जाता है, जिसे "घूर्णन" का नाम दिया गया है।
यदि कुछ रंग बदलना उपयोगी माना जाता है, तो इसे अगली क्रिया में चित्रित किया जाता है, जिसे रंग लेबल किया जाता है।^[31]
यदि अभी भी सुधार की कुछ आवश्यकता है, तो स्थिति अन्य स्थितियों के कोड का उपयोग करते हैं और यह वर्तमान नोड N के पुन: समनदेशन के बाद होता है, जिसमें पुन: एक नीली वलय होती है और जिसके सापेक्ष अन्य नोड को भी पुन: समनुदेशित करना पड़ सकता है। इस क्रिया को पुन: समनुदेशित लेबल किया गया है।
सम्मिलित करने और हटाने दोनों के लिए, (बिल्कुल) एक स्थिति है जो मूल के समीप एक काले स्तर को दोहराता है; तब पुन: निर्दिष्ट तारामंडल संबंधित लूप अपरिवर्तनीय को संतुष्ट करता है।

शीर्ष पर एक काले वृत्त के साथ संभवतः क्रमांकित त्रिकोण एक लाल-काले उप-ट्री का प्रतिनिधित्व करता है (आवश्यकता 3 के अनुसार अपने मूल से जुड़ा हुआ) जिसकी काली ऊंचाई पुनरावृत्ति स्तर शून्य से एक के बराबर है, अर्थात, प्रथम पुनरावृत्ति में शून्य इसकी मूल लाल या काली हो सकती है।
संभवतः क्रमांकित त्रिभुज एक लाल-काले उप-ट्री का प्रतिनिधित्व करता है जिसकी काली ऊँचाई एक कम है, अर्थात, इसके मूल की दूसरी पुनरावृत्ति में काली ऊँचाई शून्य है।

टिप्पणी

सरलता के लिए, प्रतिदर्श कोड विच्छेदन का उपयोग करता है:

U == शून्य || U->color == BLACK // considered black

और संयोजन:

U != शून्य && U->color == RED // not considered black

इस प्रकार, यह ध्यान में रखा जाना चाहिए कि U == NIL है, तो दोनों कथनों का कुल मूल्यांकन नहीं किया जाता है। फिर दोनों ही स्थितियों में U->color को नहीं छुआ जाता है (लघुपथन मूल्यांकन देखें)।
(considered black मानी गई टिप्पणी आवश्यकता 2 के अनुरूप है)।

यदि प्रस्ताव साकार हो जाता है, तो संबंधित if-विवरण बहुत कम बार घटित होंगे।^[30]

निवेशन

निवेशन नए (गैर-शून्य) नोड, मान लीजिए N, को शून्य नोड के द्वयी अन्वेषण ट्री में स्थिति पर रखकर प्रारंभ होता है, जिसकी अनुक्रम में पथक्रमण पूर्ववर्ती कुंजी नए नोड की कुंजी से कम तुलना करती है, जो बदले में इसके अनुक्रम में आनुक्रमिक कुंजी से कम तुलना करता है, प्रायः यह स्थिति निविष्ट संचालन से ठीक पहले ट्री के भीतर एक खोज का परिणाम है और इसमें एक नोड P के साथ एक दिशा dir के साथ P->child[dir] == NIL सम्मिलित है। नया निविष्ट नोड अस्थायी रूप से रंगीन है लाल ताकि सभी पथों में पहले की तरह ही काले नोड्स की संख्या हो। परन्तु यदि इसका जनक, मान लीजिए P, भी लाल है तो यह क्रिया लाल-उल्लंघन का परिचय देती है।

निविष्ट संचालन के पुनर्संतुलन लूप में निम्नलिखित अपरिवर्तनीयता है:

प्रत्येक पुनरावृत्ति के प्रारम्भ में वर्तमान नोड N (लाल) है।
आवश्यकता 3 संभावित अपवाद N←P के साथ सभी युग्म नोड←जनक के लिए संतुष्ट है जब P भी लाल है (N पर एक लाल-उल्लंघन)।
अन्य सभी गुण (आवश्यकता 4 सहित) सम्पूर्ण ट्री में संतुष्ट हैं।

सम्मिलित आरेखों पर टिप्पणी

पहले				स्थिति →	घूर्णन	समनुदेशन	बाद में				→ अगला	Δh
P	G	U	x	स्थिति →	घूर्णन	समनुदेशन	P	G	U	x	→ अगला	Δh
—				I3							→
				I1							→
	—			I4							→
				I2		N:=G	?				?	2
			i	I5	P↶N	N:=P				o	I6	0
			o	I6	P↷G						→
सम्मिलन: यह सारांश अपने पहले स्तम्भ में वह सब दर्शाता है, नक्षत्रों के संभावित स्थितियों^[32] को सम्मिलित किया गया है।

आरेखों में, P का उपयोग N के माता-पिता के लिए, G का उपयोग दादा-दादी के लिए और U, N के चाचा को दर्शाएगा।
आरेख मूल नोड P को उसके मूल G के बाएं बच्चे के रूप में दर्शाते हैं, भले ही P का दोनों ओर होना संभव है। प्रतिदर्श कोड पार्श्व चर dir के माध्यम से दोनों संभावनाओं को समाविष्ट करता है।
N निवेशन नोड है, परन्तु जैसे-जैसे संचालन आगे बढ़ता है अन्य नोड भी चालू हो सकते हैं (स्थिति आई2 देखें)।
आरेख उन स्थितियों को दर्शाते हैं जहां P भी लाल, लाल-उल्लंघन है।
स्तम्भ x बच्चे की दिशा में परिवर्तन को इंगित करता है, अर्थात, o (बाहरी के लिए) का अर्थ है कि P और N दोनों बाएं या दोनों दाएं बच्चे हैं, जबकि i (आंतरिक के लिए) का अर्थ है कि बच्चे की दिशा P से N की ओर बदलती है।
स्तम्भ समूह पहले उस स्थिति को परिभाषित करता है, जिसका नाम स्तम्भ स्थिति में दिया गया है। जिससे रिक्त छोड़ी गई कोष्ठिकाओं में संभावित मानों को अनदेखा कर दिया जाता है। इसलिए आई2 की स्थिति में प्रतिदर्श कोड N की संतान दिशाओं की दोनों संभावनाओं को समाविष्ट करता है, हालांकि संबंधित आरेख केवल एक दर्शाता है।
सारांश में पंक्तियों को इस तरह क्रमबद्ध किया गया है कि सभी संभावित आरबी स्थितियों का समावेशन सरलता से समझ में आ सके।
स्तम्भ घूर्णन इंगित करता है कि क्या घूर्णन पुनर्संतुलन में योगदान देता है।
स्तम्भ समनुदेशन अगले चरण में प्रवेश करने से पहले N का समनुदेशन दिखाता है। यह संभवतः अन्य नोड पी, जी, यू के पुन: समनुदेशन को भी प्रेरित करता है।
यदि स्थिति द्वारा कुछ बदला गया है, तो इसे बाद स्तम्भ समूह में दर्शाया जाता है।
अगले स्तम्भ में एक तीर → दर्शाता है कि इस चरण के साथ पुनर्संतुलन पूर्ण हो गया है। यदि बाद वाला स्तम्भ बिल्कुल एक स्थिति को निर्धारित करता है, तो इस स्थिति को अगले स्थिति के रूप में दिया जाता है, अन्यथा प्रश्न चिह्न होते हैं।
लूप अनुभाग निविष्ट स्थिति आई1 और निविष्ट स्थिति आई2 में समाहित है, जहां स्थिति आई2 में पुनर्संतुलन $\Delta h=2$ की समस्या बढ़ जाती है, ट्री का स्तर या ट्री में 1 काला स्तर ऊंचा है, इसमें दादा G नया वर्तमान नोड N बन जाता है। इसलिए यह अधिकतम ${\tfrac {h}{2}}$ होता है, ट्री के सुधार के लिए पुनरावृत्ति के चरण है (जहाँ $h$ ट्री की ऊंचाई है), क्योंकि प्रत्येक चरण के साथ वृद्धि की संभावना तीव्रता से कम हो जाती है, वास्तव में परिशोधित स्थिर कुल पुनर्संतुलन लागत औसतन स्थिर रहती है।
लूप के निकाय से, स्थिति आई1 अपने आप बाहर निकल जाता है और स्थिति आई4, आई6, आई5 + आई6 और आई3 की शाखाएं बाहर निकल जाती हैं।
लूप के बाहर आई6 और आई5 + आई6 स्थितियों में घुमाव होते हैं। इसलिए, कुल मिलाकर अधिकतम दो घुमाव होते हैं।

निविष्ट स्थिति आई1

वर्तमान नोड का मूल P काला है, इसलिए आवश्यकता 3 मान्य है। आवश्यकता 4 लूप अचर के अनुसार भी अनुप्रयुक्त होती है।

    if (P->color == BLACK) {
      // Case_I1 (P black):
      return; // insertion complete
    }
    // From now on P is red.
    if ((G = P->parent) == NULL) 
      goto Case_I4; // P red and root
    // else: P red and G!=NULL.
    dir = childDir(P); // the side of parent G on which node P is located
    U = G->child[1-dir]; // uncle
    if (U == NIL || U->color == BLACK) // considered black
      goto Case_I56; // P red && U black

निविष्ट स्थिति आई2

पहली पुनरावृत्ति

उच्चतर पुनरावृत्ति

निविष्ट स्थिति आई2

यदि माता-पिता P और चाचा U दोनों लाल हैं, तो उन दोनों को पुन: काले रंग से रंगा जा सकता है और दादा-दादी G आवश्यकता 4 को बनाए रखने के लिए लाल हो जाते हैं। चूँकि माता-पिता या चाचा से होकर कोई भी रास्ता दादा-दादी से होकर गुजरना चाहिए, इन पथों पर काले नोड की संख्या में कोई परिवर्तन नहीं आया है। हालाँकि, दादा-दादी G अब आवश्यकता 3 का उल्लंघन कर सकते हैं, यदि उसके पास लाल माता-पिता हैं। G को N में पुनः लेबल करने के बाद लूप अचर पूर्ण हो जाता है ताकि पुनर्संतुलन को एक काले स्तर (= 2 ट्री स्तर) पर पुनरावृत्त किया जा सके।

    // Case_I2 (P+U red):
    P->color = BLACK;
    U->color = BLACK;
    G->color = RED;
    N = G; // new current node
    // iterate 1 black level higher
    //   (= 2 tree levels)
  } while ((P = N->parent) != NULL);
  // end of the (do while)-loop

निविष्ट स्थिति आई3

निविष्ट स्थिति आई2 को ${\tfrac {h-1}{2}}$ गुना निष्पादित किया गया है और अब ट्री की कुल ऊंचाई $h~$ , 1 गुना बढ़ गई है। वर्तमान नोड N ट्री की (लाल) मूल है, और सभी आरबी-गुण संतुष्ट हैं।

  // Leaving the (do while)-loop (after having fallen through from Case_I2).
  // Case_I3: N is the root and red.
  return; // insertion complete

निविष्ट स्थिति आई4

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

Case_I4: // P is the root and red:
  P->color = BLACK;
  return; // insertion complete

निविष्ट स्थिति आई5

पहली पुनरावृत्ति

उच्चतर पुनरावृत्ति

निविष्ट स्थिति आई5

मूल P लाल है परन्तु चाचा U काला है। अंतिम लक्ष्य मूल नोड P को दादा-दादी की स्थिति में घुमाना है, परन्तु यह कार्य नहीं करेगा यदि N, G का आंतरिक पोता है (अर्थात, यदि N, G के दाएं बच्चे का बायां बच्चा है या G के बाएं बच्चे का बच्चा)। P पर एक dir-घूर्णन वर्तमान नोड N और उसके मूल P की भूमिकाओं को बदल देता है। घूर्णन N के माध्यम से पथ जोड़ता है (वे जो 2 लेबल वाले उप-ट्री में हैं, आरेख देखें) और P के माध्यम से पथ हटा देता है (वे जो 4 लेबल वाले उप-ट्री में हैं)। परन्तु P और N दोनों लाल हैं, इसलिए आवश्यकता 4 संरक्षित है। स्थिति 6 में आवश्यकता 3 को पुनः स्थापित किया गया है।

Case_I56: // P red && U black:
  if (N == P->child[1-dir])
  { // Case_I5 (P red && U black && N inner grandchild of G):
    RotateDir(P,dir); // P is never the root
    N = P; // new current node
    P = G->child[dir]; // new parent of N
    // fall through to Case_I6
  }

निविष्ट स्थिति आई6

पहली पुनरावृत्ति

उच्चतर पुनरावृत्ति

निविष्ट स्थिति आई6

वर्तमान नोड N अब G का "बाहरी" पोता होना निश्चित है (बाएँ बच्चे के बाएँ या दाएँ बच्चे के दाएँ)। अब (1-dir)-G पर घुमाएं, P को G के स्थान पर रखा गया है और P को N और G का माता-पिता बनाया गया है। G काला है और उसका पूर्व बच्चा P लाल है, क्योंकि आवश्यकता 3 का उल्लंघन किया गया है। P और G के रंगों को बदलने के बाद परिणामी ट्री आवश्यकता 3 को पूर्ण करता है। आवश्यकता4 भी संतुष्ट रहता है, क्योंकि काले G से होकर जाने वाले सभी रास्ते अब काले P से होकर गुजरते हैं।

  // Case_I6 (P red && U black && N outer grandchild of G):
  RotateDirRoot(T,G,1-dir); // G may be the root
  P->color = BLACK;
  G->color = RED;
  return; // insertion complete
} // end of RBinsert1

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

निष्कासन

साधारण स्थिति

लेबल N वर्तमान नोड को दर्शाता है कि प्रवेश पर वह नोड है जिसे हटाया जाना है।

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

यदि N के पास बिल्कुल एक गैर-शून्य बच्चा है, तो निष्कर्ष 5 के अनुसार, यह एक लाल बच्चा होना चाहिए।

यदि N एक लाल नोड है, तो इसमें बिल्कुल एक गैर-शून्य बच्चा नहीं हो सकता है, क्योंकि इसे आवश्यकता 3 के अनुसार काला होना होगा। इसके अतिरिक्त, निष्कर्ष 5 के अनुसार इसमें बिल्कुल एक काला बच्चा नहीं हो सकता है। परिणामस्वरूप, लाल नोड N बिना किसी संतान के है और इसे सरलता से हटाया जा सकता है।

यदि N एक काला नोड है, तो इसमें दो लाल बच्चे, एक लाल बच्चा या कोई भी गैर-शून्य बच्चा नहीं हो सकता है। यदि N के पास एक भी लाल बच्चा है, तो बाद वाले को काले रंग से रंगने के बाद उसे इस बच्चे से बदल दिया जाता है।

यदि N के दो गैर-शून्य बच्चे हैं, तो उसके दाएँ उप-ट्री में न्यूनतम तत्व के लिए एक अतिरिक्त संचालन (जो कि N का अनुक्रम में उत्तराधिकारी है, मान लीजिए ${\text{y}}$ ) N और के मध्य कोई अन्य नोड नहीं के साथ एक नोड ${\text{y}}$ ढूँढता है (जैसा कि यहां दिखाया गया है)। यह नोड ${\text{y}}$ उसका कोई बायाँ बच्चा नहीं है और इस प्रकार उसके पास अधिकतम एक गैर-शून्य बच्चा है। यदि ${\text{y}}$ , N के स्थान पर हटाया जाना है, N और ${\text{y}}$ से संबंधित लाल-काला ट्री डेटा है,अर्थात, दो नोड के रंग और संकेतक का आदान-प्रदान करना होगा। परिणामस्वरूप, संशोधित लाल-काला ट्री पहले जैसा ही है, अतिरिक्त इसके कि N और ${\text{y}}$ के मध्य का क्रम उलट दिया गया है। इस विकल्प के परिणामस्वरूप उपरोक्त अधिक सरल स्थितियों में से एक हो सकता है, परन्तु यदि ${\text{y}}$ बिना बच्चे और काले के हम पहुंचते हैं।

एक काली बिना मूल वाली पर्ण को हटाना

जटिल स्थिति तब होती है जब N मूल नहीं है, उसका रंग काला है और उसकी कोई उचित संतान नहीं है (⇔ केवल शून्य संतान)। पहले पुनरावृत्ति में, N को शून्य से बदल दिया गया है।

void RBdelete2(
  RBtree* T,         // -> red–black tree
  struct RBnode* N)  // -> node to be deleted
 {
  struct RBnode* P = N->parent;  // -> parent node of N
  byte dir;          // side of P on which N is located (∈ { LEFT, RIGHT })
  struct RBnode* S;  // -> sibling of N
  struct RBnode* C;  // -> close   nephew
  struct RBnode* D;  // -> distant nephew

  // P != NULL, since N is not the root.
  dir = childDir(N); // side of parent P on which the node N is located
  // Replace N at its parent P by NIL:
  P->child[dir] = NIL;
  goto Start_D;      // jump into the loop

  // start of the (do while)-loop:
  do {
    dir = childDir(N);   // side of parent P on which node N is located
Start_D:
    S = P->child[1-dir]; // sibling of N (has black height >= 1)
    D = S->child[1-dir]; // distant nephew
    C = S->child[  dir]; // close   nephew
    if (S->color == RED)
      goto Case_D3;                  // S red ===> P+C+D black
    // S is black:
    if (D != NIL && D->color == RED) // not considered black
      goto Case_D6;                  // D red && S black
    if (C != NIL && C->color == RED) // not considered black
      goto Case_D5;                  // C red && S+D black
    // Here both nephews are == NIL (first iteration) or black (later).
    if (P->color == RED)
      goto Case_D4;                  // P red && C+S+D black

विलोप संचालन के पुनर्संतुलन लूप में निम्नलिखित अपरिवर्तनीयता है:

प्रत्येक पुनरावृत्ति के प्रारम्भ में N की काली ऊंचाई पुनरावृत्ति संख्या शून्य से एक के बराबर होती है, जिसका अर्थ है कि पहले पुनरावृत्ति में यह शून्य है और उच्च पुनरावृत्तियों में N एक वास्तविक काला नोड है।
N से होकर जाने वाले पथों पर काले नोड की संख्या विलोपन से पहले की तुलना में एक कम है, जबकि यह अन्य सभी पथों पर अपरिवर्तित है, इसलिए यदि अन्य पथ उपस्थित हैं तो P पर काला-उल्लंघन होता है।
अन्य सभी गुण (आवश्यकता 3 सहित) सम्पूर्ण ट्री में संतुष्ट हैं।

विलोप आरेखों पर टिप्पणी

पहले				स्थिति →	घूर्णन	समनुदेशन	बाद में				→ अगला	Δh
P	C	S	D	स्थिति →	घूर्णन	समनुदेशन	P	C	S	D	→ अगला	Δh
—				D1							→
				D2		N:=P	?				?	1
				D3	P↶S	N:=N					D6	0
											D5	0
											D4	0
				D4							→
				D5	C↷S	N:=N					D6	0
				D6	P↶S						→
विलोपन: यह सारांश अपने पहले के स्तंभों में वह सब दर्शाता है रंग नक्षत्रों के संभावित स्थितियों^[32] को सम्मिलित किया गया है।

नीचे दिए गए चित्र में, P का उपयोग N के माता-पिता के लिए, S का उपयोग N के भाई-बहन के लिए, C (अर्थात् करीबी भतीजा) का उपयोग S के बच्चे के लिए N के समान दिशा में किया गया है, और D (अर्थात् दूर का भतीजा) का उपयोग S के दूसरे बच्चे के लिए किया गया है (S नहीं हो सकता) पहले पुनरावृत्ति में एक शून्य नोड, क्योंकि इसमें काली ऊंचाई एक होनी चाहिए, जो इसके विलोपन से पहले N की काली ऊंचाई थी, परन्तु C और D शून्य नोड हो सकते हैं)।
आरेख वर्तमान नोड N को उसके मूल P के बाएं बच्चे के रूप में दर्शाते हैं, भले ही N का दोनों तरफ होना संभव है। कोड प्रतिदर्श पार्श्व चर dir के माध्यम से दोनों संभावनाओं को समाविष्ट करते हैं।
निष्कासन के प्रारम्भ में (पहले पुनरावृत्ति में), N हटाए जाने वाले नोड की जगह लेने वाला शून्य नोड है, क्योंकि माता-पिता के नोड में इसका स्थान ही महत्व की एकमात्र चीज है, इसे विलोप आरेख के बाएं स्तम्भ में (अर्थ: वर्तमान नोड N एक शून्य नोड और बायां बच्चा है) द्वारा दर्शाया गया है। जैसे-जैसे संचालन आगे बढ़ता है, उचित नोड्स (काली ऊंचाई ≥ 1) भी चालू हो सकते हैं (उदाहरण के लिए स्थिति D2 देखें)।
विलोप आरेख में ( और ) की गणना करके यह देखा जा सकता है कि एन के माध्यम से पथों में अन्य पथों की तुलना में एक गोली कम है। इसका अर्थ है पी पर काला-उल्लंघन - यदि यह उपस्थित है।
पहले स्तम्भ समूह में रंग समूह उस स्थिति को परिभाषित करता है, जिसका नाम स्थिति स्तम्भ में दिया गया है। जिससे रिक्त छोड़ी गई कोष्ठिकाओं में संभावित मानों को अनदेखा कर दिया जाता है।
सारांश में पंक्तियों को इस तरह क्रमबद्ध किया गया है कि सभी संभावित आरबी स्थितियों का समावेशन सरलता से समझ में आ सके।
स्तम्भ घूर्णन इंगित करता है कि क्या घूर्णन पुनर्संतुलन में योगदान देता है।
स्तम्भ समनुदेशन बाद के पुनरावृत्ति चरण में प्रवेश करने से पहले N का समनुदेशन दर्शाता है। यह संभवतः अन्य नोड P, C, S, D के पुन: समनुदेशन को भी प्रेरित करता है।
यदि स्थिति द्वारा कुछ बदला गया है, तो इसे बाद स्तम्भ समूह में दर्शाया जाता है।
अगले स्तम्भ में एक तीर → दर्शाता है कि इस चरण के साथ पुनर्संतुलन पूर्ण हो गया है। यदि बाद वाला स्तम्भ बिल्कुल एक स्थिति को निर्धारित करता है, तो इस स्थिति को अगले स्थिति के रूप में दिया जाता है, अन्यथा प्रश्न चिह्न होते हैं।
लूप Start_D से विलोप स्थिति डी2 तक के अनुभागों में समाहित है, जहां पुनर्संतुलन $\Delta h=1$ की समस्या बढ़ जाती है, ट्री में उच्च स्तर होता है जिसमें मूल P नया वर्तमान नोड N बन जाता है। इसलिए इसमें अधिकतम $h$ समय लगता है, ट्री के सुधार के लिए पुनरावृत्तियाँ है (जहाँ $h$ ट्री की ऊंचाई है), क्योंकि प्रत्येक पुनरावृत्ति के साथ वृद्धि की संभावना तीव्रता से घट जाती है, कुल पुनर्संतुलन लागत औसतन स्थिर होती है, वास्तव में परिशोधित स्थिर होती है। केवल एक तरफ: मेहलहॉर्न और सैंडर्स बताते हैं: एवीएल ट्री निरंतर परिशोधन अद्यतन लागत का समर्थन नहीं करते हैं।^[17]^{: 165, 158} यह विलोपन के बाद पुनर्संतुलन के लिए सत्य है, परन्तु एवीएल प्रविष्टि के लिए नहीं है।^[33]
लूप के निकाय से बाहर डी3, डी6, डी5 + डी6, डी4 और डी1 से बाहर निकलने वाली शाखाएँ हैं; अनुभाग विलोप स्थिति डी3 की अपनी ही तीन अलग-अलग निकास शाखाएँ हैं जो डी6, डी5 और डी4 से संबंधित हैं।
घुमाव डी6 और डी5 + डी6 और डी3 + डी5 + डी6 की स्थितियों में - सभी लूप के बाहर होता है। इसलिए, कुल मिलाकर अधिकतम तीन घुमाव होते हैं।

विलोप स्थिति डी1

वर्तमान नोड N नया मूल है। प्रत्येक पथ से एक काला नोड हटा दिया गया है, इसलिए आरबी-गुण संरक्षित हैं। ट्री की काली ऊँचाई 1 से कम हो जाती है।

  // Case_D1 (P == NULL):
  return; // deletion complete

विलोप स्थिति डी2

→ प्रतीकों की व्याख्या

पहली पुनरावृत्ति

उच्चतर पुनरावृत्ति

विलोप स्थिति डी2

P, S और S के बच्चे काले हैं। S को लाल रंग से रंगने के बाद S से गुजरने वाले सभी पथों, जो वास्तव में वे पथ हैं जो N से नहीं गुजरते हैं, में एक कम काला नोड होता है। अब P द्वारा मूल किए गए उप-ट्री के सभी पथों में काले नोड्स की संख्या समान है, परन्तु उन पथों की तुलना में एक कम है जो P से नहीं गुजरते हैं, इसलिए आवश्यकता 4 का अभी भी उल्लंघन हो सकता है। P से n को पुनः लेबल करने के बाद लूप अचर पूर्ण हो जाता है ताकि पुनर्संतुलन को एक काले स्तर (= 1 ट्री स्तर) से अधिक पर दोहराया जा सके।

    // Case_D2 (P+C+S+D black):
    S->color = RED;
    N = P; // new current node (maybe the root)
    // iterate 1 black level
    //   (= 1 tree level) higher
  } while ((P = N->parent) != NULL);
  // end of the (do while)-loop

विलोप स्थिति डी3

पहली पुनरावृत्ति

उच्चतर पुनरावृत्ति

विलोप स्थिति डी3

भाई S का रंग लाल है, इसलिए P और भतीजे C और D का रंग काला होना चाहिए। P पर एक dir-घूर्णन S को N के दादा-दादी में बदल देता है। फिर P और S के रंगों को उलटने के बाद, N के माध्यम से पथ अभी भी एक काला नोड छोटा है। परन्तु N के पास अब एक लाल माता-पिता P है और पुनर्निर्धारण के बाद एक काला भाई-बहन S है, इसलिए डी4, डी5, या डी6 स्थितियों में परिवर्तन आरबी-आकार को पुनः स्थापित करने में सक्षम हैं।

Case_D3: // S red && P+C+D black:
  RotateDirRoot(T,P,dir); // P may be the root
  P->color = RED;
  S->color = BLACK;
  S = C; // != NIL
  // now: P red && S black
  D = S->child[1-dir]; // distant nephew
  if (D != NIL && D->color == RED)
    goto Case_D6;      // D red && S black
  C = S->child[  dir]; // close   nephew
  if (C != NIL && C->color == RED)
    goto Case_D5;      // C red && S+D black
  // Otherwise C+D considered black.
  // fall through to Case_D4

विलोप स्थिति डी4

पहली पुनरावृत्ति

उच्चतर पुनरावृत्ति

विलोप स्थिति डी4

भाई-बहन S और S के बच्चे काले हैं, परन्तु P लाल है। S और P के रंगों के आदान-प्रदान से S से गुजरने वाले पथों पर काले नोड्स की संख्या प्रभावित नहीं होती है, परन्तु यह N से गुजरने वाले पथों पर काले नोड्स की संख्या में एक जोड़ देता है, जिससे उन पथों पर हटाए गए काले नोड्स की अदायगी हो जाती है।

Case_D4: // P red && S+C+D black:
  S->color = RED;
  P->color = BLACK;
  return; // deletion complete

विलोप स्थिति डी5

पहली पुनरावृत्ति

उच्चतर पुनरावृत्ति

विलोप स्थिति डी5

भाई S काला है, S का करीबी बच्चा C लाल है, और S का दूर का बच्चा D काला है। S पर (1-dir)-घूर्णन के बाद भतीजा C, S का माता-पिता और N का नया भाई-बहन बन जाता है। S और C के रंगों का आदान-प्रदान होता है। सभी पथों में अभी भी समान संख्या में काले नोड हैं, परन्तु अब N का एक काला भाई-बहन है जिसका दूर का बच्चा लाल है, इसलिए तारामंडल स्थिति डी6 के लिए उपयुक्त है। इस परिवर्तन से न तो N और न ही उसका मूल P प्रभावित होता है और लाल या काला (आरेख में) हो सकता है।

Case_D5: // C red && S+D black:
  RotateDir(S,1-dir); // S is never the root
  S->color = RED;
  C->color = BLACK;
  D = S;
  S = C;
  // now: D red && S black
  // fall through to Case_D6

विलोप स्थिति डी6

पहली पुनरावृत्ति

उच्चतर पुनरावृत्ति

विलोप स्थिति डी6

भाई S काला है, S का दूर का बच्चा D लाल है। P पर एक dir-घूर्णन के बाद भाई-बहन S, P और S के दूर के बच्चे D का माता-पिता बन जाता है। P और S के रंगों का आदान-प्रदान होता है, और D को काला बना दिया जाता है। सम्पूर्ण उप-ट्री के मूल S पर अभी भी एक ही रंग है, अर्थात् या तो लाल या काला (आरेख में), जो परिवर्तन से पहले और बाद में एक ही रंग को संदर्भित करता है। इस प्रकार आवश्यकता 3 संरक्षित रहती है। उप-ट्री में पथ जो N से नहीं गुजरते (आई.ओ.डब्ल्यू. आरेख में D और नोड 3 से होकर गुजरते हैं) पहले की तरह समान संख्या में काले नोड से गुजरते हैं, परन्तु N के पास अब एक अतिरिक्त काला पूर्वज है: या तो P काला हो गया है, या यह था काले और S को काले दादा-दादी के रूप में जोड़ा गया था। इस प्रकार, N से गुजरने वाले पथ एक अतिरिक्त काले नोड से होकर गुजरते हैं, ताकि आवश्यकता 4 पुनः स्थापित हो जाए और कुल ट्री आरबी-आकार में हो।

Case_D6: // D red && S black:
  RotateDirRoot(T,P,dir); // P may be the root
  S->color = P->color;
  P->color = BLACK;
  D->color = BLACK;
  return; // deletion complete
} // end of RBdelete2

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

सीमा का प्रमाण

चित्र 4: लाल-काले ट्री RB_h ऊँचाई h=1,2,3,4,5,
प्रत्येक न्यूनतम संख्या 1,2,4,6 के साथ है। नोड्स के 10 है।

$h\in \mathbb {N}$ के लिए, ऊंचाई $h$ के साथ एक लाल-काले ट्री है।

$m_{h}$	$=2^{\lfloor (h+1)/2\rfloor }+2^{\lfloor h/2\rfloor }-2$
	$={\Biggl \{}$	$2\cdot 2^{\tfrac {h}{2}}-2=2^{{\tfrac {h}{2}}+1}-2$		यदि $h$ सम है।
	$3\cdot 2^{\tfrac {h-1}{2}}-2$		यदि $h$ विषम है।

नोड ( $\lfloor \,\rfloor$ तल फलन हैं) और कम नोड्स के साथ इस ट्री की ऊंचाई का कोई लाल-काला ट्री नहीं है - इसलिए यह न्यूनतम है।
इसकी काली ऊंचाई $\lceil h/2\rceil$ (काली मूल के साथ) या विषम $h$ के लिए (फिर लाल मूल के साथ) $(h-1)/2~$ भी है।

प्रमाण

एक निश्चित ऊंचाई के लाल-काले ट्री में नोड्स की न्यूनतम संख्या होने के लिए, इसमें लाल नोड्स की अधिकतम संख्या के साथ बिल्कुल एक सबसे लंबा पथ होना चाहिए, ताकि न्यूनतम काली ऊंचाई के साथ अधिकतम ट्री की ऊंचाई प्राप्त की जा सके। इस पथ के अतिरिक्त अन्य सभी नोड को काला करना होगा।^[16]^{: 444 प्रमाण रेखाचित्र} यदि इस ट्री से एक नोड हटा दिया जाता है तो यह या तो ऊंचाई खो देता है या कुछ आरबी गुणधर्म खो देता है।

ऊंचाई $h=1$ का आरबी ट्री लाल मूल के साथ न्यूनतम है। इससे सहमति है।

m_{1}=2^{\lfloor (1+1)/2\rfloor }\!+\!2^{\lfloor 1/2\rfloor }\!\!-\!\!2=2^{1}\!+\!2^{0}\!\!-\!\!2=1~.

ऊँचाई $h>1$ का एक न्यूनतम आरबी ट्री (चित्र 4 में RB_h) की एक मूल है जिसके दो उप-ट्री अलग-अलग ऊंचाई के हैं। उच्चतर संतान उप-ट्री भी एक न्यूनतम आरबी ट्री RB_h–1 है, जिसमें एक लंबा पथ भी सम्मिलित है जो इसकी ऊंचाई $h\!\!-\!\!1$ को परिभाषित करता है, यह $m_{h-1}$ नोड और काली ऊंचाई $\lfloor (h\!\!-\!\!1)/2\rfloor =:s$ है। अन्य उप-ट्री (काली) ऊंचाई $s$ का एक आदर्श एक द्वयी ट्री $2^{s}\!\!-\!\!1=2^{\lfloor (h-1)/2\rfloor }\!\!-\!\!1$ काला नोड—और कोई लाल नोड नहीं है। फिर नोड्स की संख्या प्रेरण द्वारा होती है।

	$m_{h}$	$=$	$(m_{h-1})$	$+$	$(1)$	$+$	$(2^{\lfloor (h-1)/2\rfloor }-1)$
			उच्चतर उप-ट्री		(मूल)		दूसरा उप-ट्री
जिसके परिणामस्वरूप
	$m_{h}$	$=$	$(2^{\lfloor h/2\rfloor }+2^{\lfloor (h-1)/2\rfloor }-2)$	$+$	$2^{\lfloor (h-1)/2\rfloor }$
		$=$	$2^{\lfloor h/2\rfloor }+2^{\lfloor (h+1)/2\rfloor }-2$ ■

फलन का आलेख $m_{h}$ विराम बिंदु के साथ उन्नतोदर और खंडों रैखिक फलन $(h=2k\;|\;m_{2k}=2\cdot 2^{k}\!-\!2)$ , जहाँ $k\in \mathbb {N}$ है। $h\geq 1$ के लिए, फलन $m_{h}=$ A027383(h–1) (ओईआईएस में अनुक्रम ए027383) को इस प्रकार सारणीबद्ध किया गया है।

$h$ के लिए फलन को हल करना

असमानता $9>8=2^{3}$ , $3>2^{3/2}$ की ओर ले जाता है जो विषम के लिए $h$ की ओर जाता है।

m_{h}=3\cdot 2^{(h-1)/2}-2={\bigl (}3\cdot 2^{-3/2}{\bigr )}\cdot 2^{(h+2)/2}-2>2\cdot 2^{h/2}-2

.

तो दोनों, सम और विषम स्थिति में, $h$ के साथ अंतराल में है।

	$\log _{2}(n+1)$	$\leq h\leq$	$2\log _{2}(n+2)-2=2\log _{2}(n/2+1)$	${\bigl [}<2\log _{2}(n+1)\;{\bigr ]}$
	(उत्तम द्विआधारी ट्री)		(न्यूनतम लाल-काले ट्री)

$n$ नोड्स की संख्या है।^[34]

निष्कर्ष

एक लाल-काले ट्री $n$ नोड्स (कुंजियाँ) में ट्री की ऊंचाई $h\in O(\log n)$ होती है।

संचालनों और बल्क संचालनों को व्यवस्थित करें

एकल तत्व निविष्ट, विलोप और खोज संचालन के अतिरिक्त, लाल-काले ट्रीज पर कई समूह संचालनों को परिभाषित किया गया है: संयोजन, प्रतिच्छेदन और समूह अंतर है। फिर इन समूह संचालनों के आधार पर सम्मिलन या विलोपन पर तीव्र बल्क संचालनों अनुप्रयुक्त किया जा सकता है। ये समूह संचालन दो सहायक संचालन, विभाजन और सम्मिलन पर निर्भर करते हैं। नए परिचालनों के साथ, लाल-काले ट्रीज का कार्यान्वयन अधिक कुशल और अत्यधिक-समानांतर हो सकता है।^[35] अपनी समय की जटिलताओं को प्राप्त करने के लिए इस कार्यान्वयन के लिए आवश्यक है कि मूल को या तो लाल या काला होने की अनुमति दी जाए और प्रत्येक नोड अपनी स्वयं की काली ऊँचाई संग्रहीत करे।

सम्मिलन: फलन सम्मिलन दो लाल-काले ट्रीज $t 1$ और $t 2$ और एक कुंजी $k$ पर है, जहाँ $t 1 < k < t 2$ है, अर्थात, $t 1$ की सभी कुंजियाँ $k$ से छोटी हैं और $t 2$ की सभी कुंजियाँ $k$ से बड़ी हैं। यह एक ट्री लौटाता है जिसमें $t 1$ , $t 2$ के सभी तत्व $k$ के रूप में भी होते हैं।

यदि दो ट्रीज की काली ऊंचाई समान है, तो सम्मिलन केवल बाएं उप-ट्री

t 1

, मूल

k

और दाएँ उप-ट्री

t 2

के साथ एक नया नोड बनाता है। यदि

t 1

और

t 2

दोनों के मूल काले हैं, तो

k

को लाल रंग में व्यवस्थित करें। अन्यथा

k

को काला कर दिया गया है।

यदि काली ऊँचाई असमान है, तो मान लीजिए

t 1

की काली ऊंचाई

t 2

से अधिक है (दूसरी स्थिति सममित है)। सम्मिलन एक काले नोड

c

तक

t 1

की दाहिनी पृष्ठवंश का अनुसरण करता है, जो

t 2

के साथ संतुलित है। इस बिंदु पर

c

को बदलने के लिए बाएँ बच्चे

c

, मूल

k

(लाल रंग में समूह) और दाएँ बच्चे

t 2

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

विभाजन: एक लाल-काले ट्री को दो छोटे ट्रीज में विभाजित करने के लिए, जो कुंजी $x$ से छोटे हैं और जो कुंजी $x$ से बड़े हैं, पहले लाल-काले ट्री $x$ में डालकर मूल से एक पथ बनाएं। इस प्रविष्टि के बाद, $x$ से कम के सभी मान पथ के बाईं ओर मिलेंगे और $x$ से बड़े सभी मान दाईं ओर मिलेंगे। सम्मिलन अनुप्रयुक्त करने से, बायीं ओर के सभी उप-ट्रीज को नीचे से ऊपर तक मध्यवर्ती नोड के रूप में पथ पर कुंजियों का उपयोग करके बाएँ ट्री बनाने के लिए नीचे से ऊपर की ओर संयोजित किया जाता है और दायाँ भाग सममित होता है।

कुछ अनुप्रयोगों के लिए, विभाजन एक बूलीयन मान भी लौटाता है जो दर्शाता है कि ट्री में

x

दिखाई देता है या नहीं। विभाजन की लागत

O(\log n)

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

समूह $A$ और $B$ का प्रतिनिधित्व करने वाले दो लाल-काले ट्रीज $t 1$ और $t 2$ का संयोजन, एक लाल-काले ट्री $t$ है जो $A \cup B$ का प्रतिनिधित्व करता है। निम्नलिखित पुनरावर्ती फलन इस संयोजन की गणना करता है:

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

प्रतिच्छेदन या अंतर के लिए कलन विधि समान है, परन्तु इसके लिए जॉइन2 सहायक नित्यक्रम की आवश्यकता होती है जो कि सम्मिलन के समान है परन्तु मध्य कुंजी के बिना है। संयोजन, प्रतिच्छेदन या अंतर के नए कार्यों के आधार पर, या तो एक कुंजी या एकाधिक कुंजी को लाल-काले ट्री से डाला या हटाया जा सकता है। चूंकि विभाजन सम्मिलन को कॉल करता है, परन्तु सीधे लाल-काले ट्रीज के संतुलन मानदंडों से निपटता नहीं है, ऐसे कार्यान्वयन को सामान्यतः "सम्मिलन-आधारित" कार्यान्वयन कहा जाता है।

संयोजन, प्रतिच्छेद और भेद प्रत्येक की जटिलता $O\left(m\log \left({n \over m}+1\right)\right)$ है, आकार के दो लाल-काले ट्रीज $m$ और $n(\geq m)$ के लिए है। तुलनाओं की संख्या की दृष्टि से यह जटिलता इष्टतम है। अधिक महत्वपूर्ण बात यह है कि चूंकि संयोजन, प्रतिच्छेदन या अंतर के लिए पुनरावर्ती कॉल एक-दूसरे से स्वतंत्र हैं, इसलिए उन्हें समानांतर गहराई $O(\log m\log n)$ के साथ समानांतर में निष्पादित किया जा सकता है।^[35]जब $m=1$ ,यदि बड़े ट्री के मूल का उपयोग छोटे ट्री को विभाजित करने के लिए किया जाता है, तो सम्मिलन-आधारित कार्यान्वयन में एकल-तत्व सम्मिलन और विलोपन के समान अभिकलनात्मक निर्देशित अचक्रीय आलेख (DAG) होता है।

समानांतर कलन विधि

वस्तुओं की क्रमबद्ध सूचियों से लाल-काले ट्रीज के निर्माण के लिए समानांतर कलन विधि नियत समय में चल सकते हैं या $O(\log \log n)$ समय, अभिकलित्र मॉडल पर निर्भर करता है, यदि उपलब्ध प्रोसेसर की संख्या संख्या के अनुपातिक रूप से आनुपातिक है, $n$ वस्तुओं की जहां $n\to \infty$ हैं। तीव्र अन्वेषण, सम्मिलन और विलोपन समानांतर कलन विधि भी ज्ञात हैं।^[36]

लाल-काले ट्रीज के लिए सम्मिलन-आधारित कलन विधि बल्क संचालन के लिए समानांतर हैं, जिसमें संयोजन, प्रतिच्छेदन, निर्माण, निस्यंदक, मानचित्र अपचयन इत्यादि सम्मिलित हैं।

समानांतर बल्क संचालन

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

बल्क संचालन के लिए कलन विधि केवल लाल-काले ट्री पर अनुप्रयुक्त नहीं होते हैं, बल्कि अन्य क्रमबद्ध अनुक्रम डेटा संरचनाओं के लिए भी अनुकूलित किए जा सकते हैं, जैसे 2-3 ट्री, 2-3-4 ट्री और (A, B) - ट्री, निम्नलिखित में बल्क निविष्ट के लिए अलग-अलग कलन विधियों की व्याख्या की जाएगी, परन्तु समान कलन विधियों को हटाने और अद्यतन करने के लिए भी अनुप्रयुक्त किया जा सकता है। बल्क निविष्ट एक संचालन है जो अनुक्रम $I$ एक ट्री के ऊपर $T$ के प्रत्येक तत्व को सम्मिलित करता है।

सम्मिलन-आधारित

इस दृष्टिकोण को प्रत्येक क्रमबद्ध अनुक्रम डेटा संरचना पर अनुप्रयुक्त किया जा सकता है जो कुशल सम्मिलन और विभाजन-संचालन का समर्थन करता है।^[37]सामान्य विचार विभाजन $I$ और $T$ कई भागों में करना है और इन भागों पर समानांतर में सम्मिलन करें।

सर्वप्रथम बल्क $I$ सम्मिलित किए जाने वाले तत्वों को क्रमबद्ध किया जाना चाहिए।
उसके बाद, कलन विधि $I$ में $k\in \mathbb {N} ^{+}$ भाग $\langle I_{1},\cdots ,I_{k}\rangle$ का लगभग समान आकार विभाजित हो जाता है।
अगले ट्री $T$ $T$ में $k$ $k$ भाग $\langle T_{1},\cdots ,T_{k}\rangle$ $\langle T_{1},\cdots ,T_{k}\rangle$ एक तरह से विभाजित किया जाना चाहिए , ताकि प्रत्येक $j\in \mathbb {N} ^{+}|\,1\leq j<k$ $j\in \mathbb {N} ^{+}|\,1\leq j<k$ के लिए निम्नलिखित बाधाएँ पकड़ती हैं:
1. ${\text{last}}(I_{j})<{\text{first}}(T_{j+1})$
2. ${\text{last}}(T_{j})<{\text{first}}(I_{j+1})$
अब कलन विधि प्रत्येक तत्व $I_{j}$ में $T_{j}$ क्रमानुसार को सम्मिलित करता है। यह चरण प्रत्येक $j$ के लिए किया जाना चाहिए, $k$ प्रोसेसर समानांतर में तक किया जा सकता है।
अंत में, परिणामी ट्रीज को सम्पूर्ण संचालन का अंतिम परिणाम बनाने के लिए जोड़ा जाएगा।

ध्यान दें कि चरण 3 में विभाजन $I$ के लिए बाधाएँ हैं, आश्वस्त करें कि चरण 5 में ट्री को पुन: जोड़ा जा सकता है और परिणामी क्रम को क्रमबद्ध किया जा सकता है।

Index.php?title=File:BulkInsert JoinBased InitialTree.svg

प्रारंभिक ट्री।
Index.php?title=File:BulkInsert JoinBased SplitTree.svg

I और T को विभाजित करें।
Index.php?title=File:BulkInsert JoinBased SplitTreeInserted.svg

विभाजित T में डालें।
Index.php?title=File:BulkInsert JoinBased JoinedTree.svg

संयुक्त

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

फलन

#विभाजन, #सम्मिलन	$\in O(k)$
W(विभाजन) + W(सम्मिलन)	$\in O(\log \|T\|)$
#निवेशन	$\in O(\|I\|)$
W(निवेशी)	$\in O(\log \|T\|)$
W(बल्कइंसर्ट)	$\in O(k\log \|T\|+\|I\|\log \|T\|)$

अनुप्रक्रमण

बल्क संचालन को समानांतर करने का एक अन्य तरीका अनुप्रक्रमण दृष्टिकोण का उपयोग करना है।^[38]यह बुनियादी संचालन को संसाधित करने के कार्य को उप-कार्यों के अनुक्रम में तोड़कर किया जा सकता है। कई बुनियादी संचालनों के लिए प्रत्येक उप-कार्य को एक अलग प्रोसेसर को सौंपकर उप-कार्यों को समानांतर में संसाधित किया जा सकता है।

सबसे पहले बल्क $I$ सम्मिलित किए जाने वाले तत्वों को क्रमबद्ध किया जाना चाहिए।
प्रत्येक तत्व के लिए $I$ कलन विधि तदनुसार सम्मिलन स्थिति $T$ का पता लगाता है। यह प्रत्येक तत्व $\in I$ के लिए समानांतर में किया जा सकता है, तब से $T$ इस प्रक्रिया में उत्परिवर्तित नहीं किया जाएगा। अब $I$ अनुवर्ती भागों $S$ में विभाजित किया जाना चाहिए। प्रत्येक तत्व की प्रविष्टि स्थिति के अनुसार, उदाहरण के लिए, $s_{n,{\mathit {left}}}$ का अगला भाग है। $I$ में वे तत्व सम्मिलित हैं जिनकी प्रविष्टि स्थिति नोड $n$ के बाईं ओर होगी।
मध्य तत्व $m_{n,{\mathit {dir}}}$ प्रत्येक अनुवर्ती का $s_{n,{\mathit {dir}}}$ , $T$ एक नये नोड के रूप में $n'$ में डाला जाएगा। यह प्रत्येक $m_{n,{\mathit {dir}}}$ के लिए समानांतर में किया जा सकता है चूंकि परिभाषा के अनुसार प्रत्येक की सम्मिलन स्थिति के बाद से $m_{n,{\mathit {dir}}}$ अद्वितीय है। यदि $s_{n,{\mathit {dir}}}$ के बाईं या दाईं ओर तत्व $m_{n,{\mathit {dir}}}$ सम्मिलित हैं, उन्हें बाद के नए समूह $S$ जैसे $s_{n',{\mathit {left}}}$ या $s_{n',{\mathit {right}}}$ में समाहित किया जाएगा।
अब $T$ में संभवतः मूलों से पर्णो तक के पथों के अंत में सतत दो लाल नोड होते हैं, जिनको सुधार आवश्यकता होती है। ध्यान दें कि, सुधार करते समय, तत्वों की प्रविष्टि स्थिति $\in S$ यदि संबंधित नोड घूर्णन से प्रभावित होते हैं, तो अद्यतन करना होगा।
यदि दो नोड में अलग-अलग निकटतम काले पूर्वज हैं, तो उन्हें समानांतर में सुधार किया जा सकता है। चूंकि अधिकतम चार नोड में एक ही निकटतम काला पूर्वज हो सकता है, सबसे निचले स्तर पर नोड को समानांतर चरणों की निरंतर संख्या में मरम्मत की जा सकती है।
यह चरण क्रमिक रूप से उपरोक्त काले स्तरों पर अनुप्रयुक्त किया जाएगा जब तक $T$ में पूर्णतया से सुधार किया गया है।
चरण 3 से 5 नए अनुवर्ती तक दोहराए जाएंगे, $S$ रिक्त है। इस नोड पर प्रत्येक तत्व $\in I$ डाला गया है। इन चरणों के प्रत्येक अनुप्रयोग को एक चरण कहा जाता है। चूंकि अनुवर्ती की लंबाई में $S$ , $\in O(|I|)$ है और प्रत्येक चरण में अनुवर्ती को आधा-आधा काटा जा रहा है, चरणों की संख्या $\in O(\log |I|)$ है।
चूंकि सभी चरण ट्रीज के काले स्तरों से ऊपर बढ़ते हैं, इसलिए उन्हें एक पाइपलाइन में समानांतर किया जा सकता है। एक बार जब एक चरण एक काले स्तर पर प्रसंस्करण समाप्त कर लेता है, तो अगला चरण आगे बढ़ने और उस स्तर पर जारी रखने में सक्षम होता है।

प्रारंभिक ट्री।
निवेशी स्थिति खोजें।
चरण 1 तत्वों को सम्मिलित करता है।
चरण 1 बिंदुओं में सुधार प्रारम्भ करता है।
चरण 2 तत्वों को सम्मिलित करता है।
चरण 2 में बिंदुओं में सुधार प्रारम्भ होता है।
चरण 3 तत्वों को सम्मिलित करता है।
चरण 3 में बिंदुओं का विरोहण प्रारम्भ होता है।
चरण 3 में बिंदुओं का विरोहण जारी है।

निष्पादन समय

वर्गीकरण $I$ , इस विश्लेषण में विचार नहीं किया गया है। साथ ही, $|I|$ से छोटा $|T|$ माना जाता है, अन्यथा परिणामस्वरूप ट्री को आखुर से बनाना अधिक कुशल होगा।

T(निवेशी स्थिति खोजें)	$\in O(\log \|T\|)$
#चरण	$\in O(\log \|I\|)$
T(निवेशी) + T(विरोहण)	$\in O(\log \|T\|)$
T(बल्कइंसर्ट) के साथ $\|I\|$ ~ #संसाधक	$\in O(\log \|I\|+2\cdot \log \|T\|)$ $=O(\log \|T\|)$

कार्य

W(निवेशी स्थिति खोजें)	$\in O(\|I\|\log \|T\|)$
#निवेशी, #विरोहण	$\in O(\|I\|)$
W(निवेशी) + W(विरोहण)	$\in O(\log \|T\|)$
W(बल्कइंसर्ट)	$\in O(2\cdot \|I\|\log \|T\|)$ $=O(\|I\|\log \|T\|)$

यह भी देखें

डेटा संरचनाओं की सूची
ट्री डेटा संरचना
ट्री क्रमावर्तन
AA ट्री, लाल-काले ट्री का एक रूप
वाम वृत्ति लाल-काले ट्री
एवीएल ट्री
बी-ट्री (2-3 ट्री, 2-3-4 ट्री, बी+ ट्री, बी*-ट्री, यूबी-ट्री)
स्केप्गोट ट्री
स्पले ट्री
T-ट्री
डब्ल्यूएवीएल ट्री

सन्दर्भ और नोट्स

↑ ^1.0 ^1.1 ^1.2 ^1.3 Paton, James. "Red–Black Trees".
↑ ^2.0 ^2.1 rebalancing only (no lookup), see Tarjan and Mehlhorn.
↑ ^3.0 ^3.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Red–Black Trees". Introduction to Algorithms (2nd ed.). MIT Press. pp. 273–301. ISBN 978-0-262-03293-3.
↑ Morris, John (1998). "Red–Black Trees". Data Structures and Algorithms.
↑ Bayer, Rudolf (1972). "Symmetric binary B-Trees: Data structure and maintenance algorithms". Acta Informatica. 1 (4): 290–306. doi:10.1007/BF00289509. S2CID 28836825.
↑ Drozdek, Adam (2001). जावा में डेटा संरचनाएं और एल्गोरिदम (2 ed.). Sams Publishing. p. 323. ISBN 978-0534376680.
↑ ^7.0 ^7.1 Guibas, Leonidas J.; Sedgewick, Robert (1978). "A Dichromatic Framework for Balanced Trees". Proceedings of the 19th Annual Symposium on Foundations of Computer Science. pp. 8–21. doi:10.1109/SFCS.1978.3.
↑ "लाल काले पेड़". eternallyconfuzzled.com. Archived from the original on 2007-09-27. Retrieved 2015-09-02.
↑ Sedgewick, Robert (2012). Red–Black BSTs. Coursera. A lot of people ask why did we use the name red–black. Well, we invented this data structure, this way of looking at balanced trees, at Xerox PARC that was the home of the personal computer and many other innovations that we live with today entering[sic] graphic user interfaces, Ethernet and object-oriented programmings[sic] and many other things. But one of the things that was invented there was laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors the red looked the best. So, that's why we picked the color red to distinguish red links, the types of links, in three nodes. So, that's an answer to the question for people that have been asking.
↑ "Where does the term "Red/Black Tree" come from?". programmers.stackexchange.com. Retrieved 2015-09-02.
↑ Andersson, Arne (1993-08-11). "Balanced search trees made simple". In Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (eds.). Algorithms and Data Structures (Proceedings). Lecture Notes in Computer Science. Vol. 709. Springer-Verlag Berlin Heidelberg. pp. 60–71. CiteSeerX 10.1.1.118.6192. doi:10.1007/3-540-57155-8_236. ISBN 978-3-540-57155-1. Archived from the original on 2018-12-08. Alt URL
↑ Okasaki, Chris (1999-01-01). "Red–black trees in a functional setting". Journal of Functional Programming. 9 (4): 471–477. doi:10.1017/S0956796899003494. ISSN 1469-7653. S2CID 20298262. Archived from the original (PS) on 2007-09-26. Retrieved 2007-05-13.
↑ Sedgewick, Robert (1983). Algorithms (1st ed.). Addison-Wesley. ISBN 978-0-201-06672-2.
↑ Sedgewick, Robert; Wayne, Kevin. "RedBlackBST.java". algs4.cs.princeton.edu. Retrieved 7 April 2018.
↑ Sedgewick, Robert (2008). "Left-leaning Red–Black Trees".
↑ ^16.0 ^16.1 ^16.2 Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Addison-Wesley Professional. ISBN 978-0-321-57351-3.
↑ ^17.0 ^17.1 ^17.2 ^17.3 Mehlhorn, Kurt; Sanders, Peter (2008). "7. Sorted Sequences" (PDF). Algorithms and Data Structures: The Basic Toolbox. Berlin/Heidelberg: Springer. CiteSeerX 10.1.1.148.2305. doi:10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
↑ ^18.0 ^18.1 Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2022). "13. Red–Black Trees". Introduction to Algorithms (4th ed.). MIT Press. pp. 331–332. ISBN 9780262046305.
↑ Using Knuth’s definition of order: the maximum number of children
↑ Sedgewick, Robert (1998). C++ में एल्गोरिदम. Addison-Wesley Professional. pp. 565–575. ISBN 978-0-201-35088-3.
↑ "The Implementation of epoll (1)". September 2014.
↑ Pfaff 2004
↑ ^23.0 ^23.1 "रॉबर्ट सेडगेविक" (PDF). Cs.princeton.edu. 4 June 2020. Retrieved 26 March 2022.
↑ "संतुलित पेड़" (PDF). Cs.princeton.edu. Retrieved 26 March 2022.
↑ Demaine, E. D.; Harmon, D.; Iacono, J.; Pătraşcu, M. (2007). "Dynamic Optimality—Almost" (PDF). SIAM Journal on Computing. 37 (1): 240. doi:10.1137/S0097539705447347. S2CID 1480961.
↑ "जावा में हैशमैप कैसे काम करता है?". coding-geek.com.
↑ Tarjan, Robert Endre (April 1985). "परिशोधित कम्प्यूटेशनल जटिलता" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 306–318. doi:10.1137/0606031.
↑ The important thing about these tree rotations is that they preserve the in-order sequence of the tree’s nodes.
↑ "Ben Pfaff (2007): Online HTML version of a well-documented collection of binary search tree and balanced tree library routines".
↑ ^30.0 ^30.1 The left columns contain far less nodes than the right ones, especially for removal. This indicates that some efficiency can be gained by pulling the first iteration out of the rebalancing loops of insertion and deletion, because many of the named nodes are NIL nodes in the first iteration and definitively non-NIL later. (See also this remark.)
↑ Rotations have been placed before recoloring for reasons of clarity. But the two commute, so that it is free choice to move the rotation to the tail.
↑ ^32.0 ^32.1 The same partitioning is found in Ben Pfaff.
↑ Dinesh P. Mehta, Sartaj Sahni (Ed.) Handbook of Data Structures and Applications 10.4.2
↑ Equality at the upper bound holds for the minimal RB trees RB_2k of even height $2\cdot k$ with $n=2\cdot 2^{k}-2$ nodes and only for those. So the inequality is marginally more precise than the widespread $h<2\log _{2}(n+1),$ e. g. in Cormen p. 264.
Moreover, these trees are binary trees that admit one and only one coloring conforming to the RB requirements 1 to 4. But there are further such trees, e. g. appending a child node to a black leaf always forces it to red. (A minimal RB tree of odd height allows to flip the root’s color from red to black.)
↑ ^35.0 ^35.1 Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets" (PDF), Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793.
↑ Park, Heejin; Park, Kunsoo (2001). "Parallel algorithms for red–black trees". Theoretical Computer Science. 262 (1–2): 415–435. doi:10.1016/S0304-3975(00)00287-5. Our parallel algorithm for constructing a red–black tree from a sorted list of $n$ items runs in $O(1)$ time with $n$ processors on the CRCW PRAM and runs in $O(\log \log n)$ time with $n/\log \log n$ processors on the EREW PRAM.
↑ Sanders, Peter (2019). Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (eds.). Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox. Springer eBooks. Cham: Springer. pp. 252–253. doi:10.1007/978-3-030-25209-0. ISBN 9783030252090. S2CID 201692657.
↑ Jájá, Joseph (1992). An introduction to parallel algorithms. Reading, Mass. [u.a.]: Addison-Wesley. pp. 65–70. ISBN 0201548569. Zbl 0781.68009.
↑ Missing (Canadian TV series) (in English). A, W Network (Canada); Lifetime (United States).
↑ Robert Sedgewick (2012). बी पेड़. Coursera. 9:48 minutes in. So not only is there some excitement in that dialogue but it's also technically correct that you don't often find with math in popular culture of computer science. A red–black tree tracks every simple path from a node to a descendant leaf with the same number of black nodes they got that right.

अग्रिम पठन

Mathworld: Red–Black Tree
San Diego State University: CS 660: Red–Black tree notes, by Roger Whitney
Pfaff, Ben (June 2004). "Performance Analysis of BSTs in System Software" (PDF). Stanford University.

बाहरी संबंध

Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. Free Software Foundation, Boston 2004, ftp.gnu.org (PDF gzip; 1662 kB)
A complete and working implementation in C
OCW MIT Lecture on Red-black Trees by Erik Demaine
Binary Search Tree Insertion Visualization on YouTube – Visualization of random and pre-sorted data insertions, in elementary binary search trees, and left-leaning red–black trees
An intrusive red–black tree written in C++
Red–black BSTs in 3.3 Balanced Search Trees
Red–black BST Demo

[wiscurl-1] 1.0 ^1.1 ^1.2 ^1.3 Paton, James. "Red–Black Trees".

[InfoBU-2] 2.0 ^2.1 rebalancing only (no lookup), see Tarjan and Mehlhorn.

[Cormen2001-3] 3.0 ^3.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Red–Black Trees". Introduction to Algorithms (2nd ed.). MIT Press. pp. 273–301. ISBN 978-0-262-03293-3.

[4] Morris, John (1998). "Red–Black Trees". Data Structures and Algorithms.

[Bayer72-5] Bayer, Rudolf (1972). "Symmetric binary B-Trees: Data structure and maintenance algorithms". Acta Informatica. 1 (4): 290–306. doi:10.1007/BF00289509. S2CID 28836825.

[6] Drozdek, Adam (2001). जावा में डेटा संरचनाएं और एल्गोरिदम (2 ed.). Sams Publishing. p. 323. ISBN 978-0534376680.

[GS78-7] 7.0 ^7.1 Guibas, Leonidas J.; Sedgewick, Robert (1978). "A Dichromatic Framework for Balanced Trees". Proceedings of the 19th Annual Symposium on Foundations of Computer Science. pp. 8–21. doi:10.1109/SFCS.1978.3.

[8] "लाल काले पेड़". eternallyconfuzzled.com. Archived from the original on 2007-09-27. Retrieved 2015-09-02.

[Sedgewick12-9] Sedgewick, Robert (2012). Red–Black BSTs. Coursera. A lot of people ask why did we use the name red–black. Well, we invented this data structure, this way of looking at balanced trees, at Xerox PARC that was the home of the personal computer and many other innovations that we live with today entering[sic] graphic user interfaces, Ethernet and object-oriented programmings[sic] and many other things. But one of the things that was invented there was laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors the red looked the best. So, that's why we picked the color red to distinguish red links, the types of links, in three nodes. So, that's an answer to the question for people that have been asking.

[10] "Where does the term "Red/Black Tree" come from?". programmers.stackexchange.com. Retrieved 2015-09-02.

[11] Andersson, Arne (1993-08-11). "Balanced search trees made simple". In Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (eds.). Algorithms and Data Structures (Proceedings). Lecture Notes in Computer Science. Vol. 709. Springer-Verlag Berlin Heidelberg. pp. 60–71. CiteSeerX 10.1.1.118.6192. doi:10.1007/3-540-57155-8_236. ISBN 978-3-540-57155-1. Archived from the original on 2018-12-08. Alt URL

[12] Okasaki, Chris (1999-01-01). "Red–black trees in a functional setting". Journal of Functional Programming. 9 (4): 471–477. doi:10.1017/S0956796899003494. ISSN 1469-7653. S2CID 20298262. Archived from the original (PS) on 2007-09-26. Retrieved 2007-05-13.

[Algs1-13] Sedgewick, Robert (1983). Algorithms (1st ed.). Addison-Wesley. ISBN 978-0-201-06672-2.

[14] Sedgewick, Robert; Wayne, Kevin. "RedBlackBST.java". algs4.cs.princeton.edu. Retrieved 7 April 2018.

[15] Sedgewick, Robert (2008). "Left-leaning Red–Black Trees".

[Algs4-16] 16.0 ^16.1 ^16.2 Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Addison-Wesley Professional. ISBN 978-0-321-57351-3.

[Mehlhorn2008-17] 17.0 ^17.1 ^17.2 ^17.3 Mehlhorn, Kurt; Sanders, Peter (2008). "7. Sorted Sequences" (PDF). Algorithms and Data Structures: The Basic Toolbox. Berlin/Heidelberg: Springer. CiteSeerX 10.1.1.148.2305. doi:10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.

[Cormen2009-18] 18.0 ^18.1 Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2022). "13. Red–Black Trees". Introduction to Algorithms (4th ed.). MIT Press. pp. 331–332. ISBN 9780262046305.

[19] Using Knuth’s definition of order: the maximum number of children

[20] Sedgewick, Robert (1998). C++ में एल्गोरिदम. Addison-Wesley Professional. pp. 565–575. ISBN 978-0-201-35088-3.

[21] "The Implementation of epoll (1)". September 2014.

[22] Pfaff 2004

[LLRB-23] 23.0 ^23.1 "रॉबर्ट सेडगेविक" (PDF). Cs.princeton.edu. 4 June 2020. Retrieved 26 March 2022.

[24] "संतुलित पेड़" (PDF). Cs.princeton.edu. Retrieved 26 March 2022.

[DHIP-25] Demaine, E. D.; Harmon, D.; Iacono, J.; Pătraşcu, M. (2007). "Dynamic Optimality—Almost" (PDF). SIAM Journal on Computing. 37 (1): 240. doi:10.1137/S0097539705447347. S2CID 1480961.

[26] "जावा में हैशमैप कैसे काम करता है?". coding-geek.com.

[tarjan-27] Tarjan, Robert Endre (April 1985). "परिशोधित कम्प्यूटेशनल जटिलता" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 306–318. doi:10.1137/0606031.

[28] The important thing about these tree rotations is that they preserve the in-order sequence of the tree’s nodes.

[29] "Ben Pfaff (2007): Online HTML version of a well-documented collection of binary search tree and balanced tree library routines".

[pullout-30] 30.0 ^30.1 The left columns contain far less nodes than the right ones, especially for removal. This indicates that some efficiency can be gained by pulling the first iteration out of the rebalancing loops of insertion and deletion, because many of the named nodes are NIL nodes in the first iteration and definitively non-NIL later. (See also this remark.)

[31] Rotations have been placed before recoloring for reasons of clarity. But the two commute, so that it is free choice to move the rotation to the tail.

[cases-32] 32.0 ^32.1 The same partitioning is found in Ben Pfaff.

[33] Dinesh P. Mehta, Sartaj Sahni (Ed.) Handbook of Data Structures and Applications 10.4.2

[34] Equality at the upper bound holds for the minimal RB trees RB_2k of even height $2\cdot k$ with $n=2\cdot 2^{k}-2$ nodes and only for those. So the inequality is marginally more precise than the widespread $h<2\log _{2}(n+1),$ e. g. in Cormen p. 264.
Moreover, these trees are binary trees that admit one and only one coloring conforming to the RB requirements 1 to 4. But there are further such trees, e. g. appending a child node to a black leaf always forces it to red. (A minimal RB tree of odd height allows to flip the root’s color from red to black.)

[join-based-35] 35.0 ^35.1 Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets" (PDF), Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793.

[36] Park, Heejin; Park, Kunsoo (2001). "Parallel algorithms for red–black trees". Theoretical Computer Science. 262 (1–2): 415–435. doi:10.1016/S0304-3975(00)00287-5. Our parallel algorithm for constructing a red–black tree from a sorted list of $n$ items runs in $O(1)$ time with $n$ processors on the CRCW PRAM and runs in $O(\log \log n)$ time with $n/\log \log n$ processors on the EREW PRAM.

[37] Sanders, Peter (2019). Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (eds.). Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox. Springer eBooks. Cham: Springer. pp. 252–253. doi:10.1007/978-3-030-25209-0. ISBN 9783030252090. S2CID 201692657.

[38] Jájá, Joseph (1992). An introduction to parallel algorithms. Reading, Mass. [u.a.]: Addison-Wesley. pp. 65–70. ISBN 0201548569. Zbl 0781.68009.

[39] Missing (Canadian TV series) (in English). A, W Network (Canada); Lifetime (United States).

[40] Robert Sedgewick (2012). बी पेड़. Coursera. 9:48 minutes in. So not only is there some excitement in that dialogue but it's also technically correct that you don't often find with math in popular culture of computer science. A red–black tree tracks every simple path from a node to a descendant leaf with the same number of black nodes they got that right.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

@@ Line 157: / Line 157: @@
 == गुणधर्म ==
-द्वयी अन्वेषण ट्री पर लगाई गई आवश्यकताओं के अतिरिक्त निम्नलिखित को लाल-काले ट्री द्वारा संतुष्ट किया जाना चाहिए:
+द्वयी अन्वेषण ट्री पर लगाई गई आवश्यकताओं के अतिरिक्त निम्नलिखित को लाल-काले ट्री द्वारा संतुष्ट किया जाना चाहिए:{{nowrap|red–black tree:<ref name="Cormen2009">{{cite book
+|last1=Cormen |first1=Thomas |author-link1=Thomas H. Cormen
+|last2=Leiserson |first2=Charles |author-link2=Charles E. Leiserson
+|first3=Ronald |last3=Rivest |author-link3=Ron Rivest
+|first4=Clifford |last4=Stein |author-link4=Clifford Stein
+|chapter=13. Red–Black Trees
+|title=Introduction to Algorithms |title-link=Introduction to Algorithms
+|edition=4th |year=2022 |publisher=[[MIT Press]] |isbn=9780262046305
+|pages=[https://archive.org/details/introductiontoal00corm_805/page/n328 331]–332
+}}</ref>}}
 # प्रत्येक नोड या तो लाल या काले है।
@@ Line 905: / Line 914: @@
 # चरण 3 से 5 नए अनुवर्ती तक दोहराए जाएंगे, <math>S</math> रिक्त है। इस नोड पर प्रत्येक तत्व <math>\in I</math> डाला गया है। इन चरणों के प्रत्येक अनुप्रयोग को एक चरण कहा जाता है। चूंकि अनुवर्ती की लंबाई में <math>S</math>, <math>\in O(|I|)</math> है और प्रत्येक चरण में अनुवर्ती को आधा-आधा काटा जा रहा है, चरणों की संख्या <math>\in O(\log |I|)</math> है।<br/>चूंकि सभी चरण ट्रीज के काले स्तरों से ऊपर बढ़ते हैं, इसलिए उन्हें एक पाइपलाइन में समानांतर किया जा सकता है। एक बार जब एक चरण एक काले स्तर पर प्रसंस्करण समाप्त कर लेता है, तो अगला चरण आगे बढ़ने और उस स्तर पर जारी रखने में सक्षम होता है।
 <gallery>
-File:Index.php?title=File:Index.php?title=File:Index.php?title=File:BulkInsert Pipelining InitialTree.svg|प्रारंभिक ट्री।
+BulkInsert Pipelining InitialTree.svg|प्रारंभिक ट्री।
-File:Index.php?title=File:Index.php?title=File:Index.php?title=File:BulkInsert Pipelining InsertPositions.svg|निवेशी स्थिति खोजें।
+BulkInsert Pipelining InsertPositions.svg|निवेशी स्थिति खोजें।
-File:Index.php?title=File:Index.php?title=File:Index.php?title=File:BulkInsert Pipelining Stage1Insert.svg|चरण 1 तत्वों को सम्मिलित करता है।
+BulkInsert Pipelining Stage1Insert.svg|चरण 1 तत्वों को सम्मिलित करता है।
-File:Index.php?title=File:Index.php?title=File:Index.php?title=File:BulkInsert Pipelining Stage1Repair.svg|चरण 1 बिंदुओं में सुधार प्रारम्भ करता है।
+BulkInsert Pipelining Stage1Repair.svg|चरण 1 बिंदुओं में सुधार प्रारम्भ करता है।
-File:Index.php?title=File:Index.php?title=File:Index.php?title=File:BulkInsert Pipelining Stage2Insert.svg|चरण 2 तत्वों को सम्मिलित करता है।
+BulkInsert Pipelining Stage2Insert.svg|चरण 2 तत्वों को सम्मिलित करता है।
-File:Index.php?title=File:Index.php?title=File:Index.php?title=File:BulkInsert Pipelining Stage2Repair.svg|चरण 2 में बिंदुओं में सुधार प्रारम्भ होता है।
+BulkInsert Pipelining Stage2Repair.svg|चरण 2 में बिंदुओं में सुधार प्रारम्भ होता है।
-File:Index.php?title=File:Index.php?title=File:Index.php?title=File:BulkInsert Pipelining Stage3Insert.svg|चरण 3 तत्वों को सम्मिलित करता है।
+BulkInsert Pipelining Stage3Insert.svg|चरण 3 तत्वों को सम्मिलित करता है।
-File:Index.php?title=File:Index.php?title=File:Index.php?title=File:BulkInsert Pipelining Stage3Repair1.svg|चरण 3 में बिंदुओं का विरोहण प्रारम्भ होता है।
+BulkInsert Pipelining Stage3Repair1.svg|चरण 3 में बिंदुओं का विरोहण प्रारम्भ होता है।
-File:Index.php?title=File:Index.php?title=File:Index.php?title=File:BulkInsert Pipelining Stage3Repair2.svg|चरण 3 में बिंदुओं का विरोहण जारी है।
+BulkInsert Pipelining Stage3Repair2.svg|चरण 3 में बिंदुओं का विरोहण जारी है।
 </gallery>
 ===== निष्पादन समय =====
@@ Line 942: / Line 950: @@
 | '''W(बल्कइंसर्ट)''' || <math>\in O(2 \cdot |I| \log |T|)</math><br/><math>= O(|I| \log |T|)</math>
 |}
@@ Line 993: / Line 1,011: @@
 {{Data structures}}
-{{DEFAULTSORT:Red-Black Tree}}[[Category: 1972 कंप्यूटिंग में]] [[Category: प्रमाण युक्त लेख]] [[Category: उदाहरण सी कोड वाले लेख]] [[Category: बाइनरी पेड़]] [[Category: पेड़ खोजें]]
+{{DEFAULTSORT:Red-Black Tree}}
-[[Category: Machine Translated Page]]
+[[Category:1972 कंप्यूटिंग में|Red-Black Tree]]
-[[Category:Created On 10/07/2023]]
+[[Category:All articles that are too technical|Red-Black Tree]]
+[[Category:Articles with invalid date parameter in template|Red-Black Tree]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:Collapse templates|Red-Black Tree]]
+[[Category:Created On 10/07/2023|Red-Black Tree]]
+[[Category:Lua-based templates|Red-Black Tree]]
+[[Category:Machine Translated Page|Red-Black Tree]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Red-Black Tree]]
+[[Category:Pages with broken file links|Red-Black Tree]]
+[[Category:Pages with reference errors|Red-Black Tree]]
+[[Category:Pages with script errors|Red-Black Tree]]
+[[Category:Short description with empty Wikidata description|Red-Black Tree]]
+[[Category:Sidebars with styles needing conversion|Red-Black Tree]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Red-Black Tree]]
+[[Category:Templates generating microformats|Red-Black Tree]]
+[[Category:Templates that add a tracking category|Red-Black Tree]]
+[[Category:Templates that are not mobile friendly|Red-Black Tree]]
+[[Category:Templates that generate short descriptions|Red-Black Tree]]
+[[Category:Templates using TemplateData|Red-Black Tree]]
+[[Category:Wikipedia articles that are too technical from जनवरी 2023|Red-Black Tree]]
+[[Category:Wikipedia metatemplates|Red-Black Tree]]

v t e Tree data structures
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal Fibonacci Leftist Pairing Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

लाल-काला ट्री: Difference between revisions

Latest revision as of 12:43, 28 July 2023

इतिहास

शब्दावली

गुणधर्म

क्रम 4 के B-ट्री की सादृश्यता

अनुप्रयोग और संबंधित डेटा संरचनाएँ

संचालन

प्रतिदर्श कोड और प्रविष्टि और निष्कासन के आरेख पर टिप्पणी

निवेशन

सम्मिलित आरेखों पर टिप्पणी

निविष्ट स्थिति आई1

निविष्ट स्थिति आई2

निविष्ट स्थिति आई3

निविष्ट स्थिति आई4

निविष्ट स्थिति आई5

निविष्ट स्थिति आई6

निष्कासन

साधारण स्थिति

एक काली बिना मूल वाली पर्ण को हटाना

विलोप आरेखों पर टिप्पणी

विलोप स्थिति डी1

विलोप स्थिति डी2

विलोप स्थिति डी3

विलोप स्थिति डी4

विलोप स्थिति डी5

विलोप स्थिति डी6

सीमा का प्रमाण

संचालनों और बल्क संचालनों को व्यवस्थित करें

समानांतर कलन विधि

समानांतर बल्क संचालन

सम्मिलन-आधारित

फलन

अनुप्रक्रमण

निष्पादन समय

कार्य

लोकप्रिय संस्कृति

यह भी देखें

सन्दर्भ और नोट्स

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories