लाल-काले पेड़ों के बारे में बहुत सारे प्रश्न हैं लेकिन उनमें से कोई भी जवाब नहीं देता कि वे कैसे काम करते हैं। इसे लाल-काले क्यों कहा जाता है? यह पेड़ को संतुलित कैसे रखता है (इस प्रकार एक असंतुलित सामान्य बाइनरी खोज पेड़ पर प्रदर्शन बढ़ रहा है)? मैं सिर्फ एक और अवलोकन की तलाश कर रहा हूं कि यह कैसे और क्यों काम करता है।लाल-काले पेड़ कैसे काम करता है?
खोज और ट्रैवर्सल के लिए, यह किसी भी बाइनरी पेड़ जैसा ही है।
आवेषण और हटाना के लिए, अधिक परिष्कृत एल्गोरिदम लागू होते हैं जिसका उद्देश्य यह सुनिश्चित करना है कि पेड़ बहुत असंतुलित न हो। ये गारंटी देते हैं कि सभी सिंगल-आइटम ऑपरेशंस हमेशा खराब ओ (लॉग एन) समय पर चलेंगे, जबकि एक साधारण बाइनरी पेड़ में बाइनरी पेड़ इतना असंतुलित हो सकता है कि यह प्रभावी रूप से एक लिंक की गई सूची है, जिससे ओ (एन) सबसे खराब केस प्रदर्शन प्रत्येक एकल आइटम ऑपरेशन।
लाल-काले पेड़ का मूल विचार बी-पेड़ की नकल करना है जिसमें 3 कुंजी और 4 बच्चे प्रति नोड हैं। बी-पेड़ (या बी + पेड़ जैसे बदलाव) मुख्य रूप से डेटाबेस इंडेक्स और हार्ड डिस्क पर संग्रहीत डेटा के लिए उपयोग किए जाते हैं।
प्रत्येक बाइनरी पेड़ नोड में "रंग" होता है - लाल या काला। प्रत्येक काला नोड बी-पेड़ समानता में होता है, उस उप-त्रिज्या के लिए उपट्री रूट जो बी-पेड़ नोड के भीतर फिट बैठता है। अगर इस नोड में लाल बच्चे हैं, तो उन्हें एक ही बी-पेड़ नोड का हिस्सा माना जाता है। तो यह संभव है (हालांकि अभ्यास में नहीं किया गया) एक लाल-काले पेड़ को बी-पेड़ और पीठ में परिवर्तित करने के लिए, (अधिकांश) संरचना संरक्षित है। एकमात्र संभावित विसंगति यह है कि जब बी-पेड़ नोड में दो चाबियाँ और तीन बच्चे होते हैं, तो आपके पास समान लाल-काले पेड़ में काले नोड में जाने की कुंजी होती है।
उदाहरण के लिए, लाल-काले पेड़ के साथ, रूट से पत्ती की प्रत्येक पंक्ति में काले नोड्स की एक ही संख्या होती है। यह नियम बी-पेड़ नियम से लिया गया है कि सभी पत्ते नोड एक ही गहराई पर हैं।
हालांकि यह मूल विचार है जिसमें से लाल-काले पेड़ व्युत्पन्न होते हैं, लेकिन सभी बी-पेड़ नियमों को लागू करने के लिए प्रयुक्त एल्गोरिदम संशोधित होते हैं (वहां मामूली अपवाद हो सकता है - मैं भूल जाता हूं) अद्यतन, लेकिन बाइनरी पेड़ के रूप के लिए तैयार हैं। इसका मतलब यह है कि लाल-काले पेड़ डालने या हटाने से परिणाम के लिए एक अलग संरचना हो सकती है, जिससे आप बी-पेड़ डालने या हटाने के साथ तुलना करने की अपेक्षा करेंगे।
अधिक जानकारी के लिए, Wikipedia link का पालन करें जो MigDus पहले से ही आपूर्ति की गई है।
एक लाल-काला पेड़ एक आदेश दिया गया बाइनरी पेड़ है जहां प्रत्येक चरम रंग लाल या काला रंग होता है। अंतर्ज्ञान यह है कि एक लाल चरम को उसी ऊंचाई पर देखा जाना चाहिए क्योंकि उसके माता-पिता (यानी, लाल अक्षरों के किनारे को "अवरोही" के बजाय "क्षैतिज" के रूप में माना जाता है)।
[मेरा मानना है कि नहीं विकिपीडिया प्रविष्टि इस बात को स्पष्ट करता है।]
लाल-काले पेड़ों के लिए हमेशा की तरह नियमों की आवश्यकता है कि एक लाल शीर्ष कभी नहीं एक और लाल शिखर को इंगित। इसका मतलब यह है कि किसी काले subtex (बीबीबी, बीबीआर, आरबीबी, आरआरबी - [बाएं बच्चे] [रूट] [दायां बच्चा] के लिए रूट किसी भी subtree के लिए संभव चरम व्यवस्था 234 पेड़ के अनुरूप है।
लाल-काले पेड़ को खोजना सामान्य बाइनरी पेड़ की खोज के समान ही है। सम्मिलन और हटाना समान है, सिवाय इसके कि लाल-काले आविष्कार को संरक्षित करने के लिए किसी बिंदु पर "फिक्स-अप" रोटेशन की आवश्यकता हो सकती है।
चीयर्स!
"अंतर्ज्ञान यह है कि एक लाल चरम को अपने माता-पिता के समान ऊंचाई पर देखा जाना चाहिए (यानी।, एक लाल कशेरुक के किनारे को "अवरोही" के बजाय "क्षैतिज" के रूप में माना जाता है)। * * लाइटबुल पल, धन्यवाद! * –
यह उत्तर स्वीकार किया जाना चाहिए मुझे लगता है। –