मैं Left Leaning Red Black Trees के बारे में सीख रहा हूं।बाएं झुकाव लाल काले पेड़ों में हटाना
पेपर में उल्लिखित विलोपन एल्गोरिदम में, यदि नोड के लिए मुख्य मिलान और सही उपट्री उस नोड के लिए नल है, तो वह नोड हटा दिया जाता है। लेकिन वहां एक बाएं उप-विषय भी हो सकता है जिसे माना नहीं जाता है।
मैं को समझने में सक्षम नहीं हूं, बाएं उपट्री न्यूल क्यों होगा। न्यूनतम या अधिकतम को हटाने पर भी इसी तरह की चीज की जाती है। क्या कोई इस पर मुझे मार्गदर्शन कर सकता है?
ऐसा लगता है आप कोड के इस टुकड़े के बारे में बात कर रहे हैं:
if (isRed(h.left))
h = rotateRight(h);
if (key.compareTo(h.key) == 0 && (h.right == null))
return null;
यहाँ छोड़ दिया वंशज नहीं किया जा सकता "लाल" क्योंकि पूर्ववर्ती कोड सही करने के लिए यह बारी बारी से होगा।
इसके अलावा वंश छोड़कर "काला" नहीं हो सकता है क्योंकि इस मामले में h के बाईं ओर एक पथ है जिसमें कम से कम एक "काला" नोड होता है जबकि इसके दाईं ओर कोई भी पथ "काला" नोड्स नहीं होता है। लेकिन आरबी-पेड़ में हर पथ पर काले नोड्स की संख्या समान होनी चाहिए।
इसका मतलब है कि वहां कोई बाएं वंशज नहीं है और नोड h एक पत्ता नोड है।
deleteMin कार्य में बाएं उप-पेड़ खाली होने पर सही उप-पेड़ की जांच करने की आवश्यकता नहीं है क्योंकि एलएलआरबी पेड़ का कोई सही उप-पेड़ इसी बाएं उप-पेड़ से अधिक नहीं हो सकता है।
बाएं झुकाव लाल काले पेड़ वास्तव में बेहतर या पहले कार्यान्वयन से भी सरल हैं या नहीं, इसका एक दिलचस्प विश्लेषण है। लेख Left-Leaning Red Black Trees Considered Harmful हार्वर्ड कॉम्प साइंस प्रोफेसर Eddie Kohler द्वारा लिखा गया था। वह लिखते हैं:
Tricky writing
Sedgewick’s paper is tricky. As of 2013, the insert section presents 2–3–4 trees as
the default and describes 2–3 trees as a variant. The delete implementation, however,
only works for 2–3 trees. If you implement the default variant of insert and the
only variant of delete,your tree won’t work. The text doesn’t highlight the switch
from 2–3–4 to 2–3: not kind.