लाल काला पेड़ छद्म कोड रिडंडेंसी

Question

एल्गोरिदम तीसरे संस्करण के परिचय में उनके पास लाल-काले पेड़ हटाने का एक छद्म कोड कार्यान्वयन है। यहाँ यह है ...

RB-DELETE(T, z) 
    y = z 
    y-original-color = y.color 
    if z.left == T.nil 
     x = z.right 
     RB-TRANSPLANT(T, z, z.right) 
    elseif z.right == T.nil 
     x = z.left 
     RB-TRANSPLANT(T, z, z.left) 
    else 
     y = TREE-MINIMUM(z.right) 
     y-original-color = y.color 
     x = y.right 
     if y.p == z 
       x.p = y  // <--------- why???? 
     else 
       RB-TRANSPLANT(T, y, y.right) 
       y.right = z.right 
       y.right.p = y 
     RB-TRANSPLANT(T, z, y) 
     y.left = z.left 
     y.left.p = y 
     y.color = z.color 
    if y-original-color == BLACK 
     RB-DELETE-FIXUP(T, x) 

वृक्ष-न्यूनतम सिर्फ एक पेड़ में सबसे छोटा मान पाता है, आरबी प्रत्यारोपण दूसरा पैरामीटर की मूल लेता है और यह तीसरे पैरामीटर के लिए बिंदु है, और तीसरे पैरामीटर के माता-पिता है दूसरे पैरामीटर के माता-पिता बनें।

मेरी टिप्पणी से, वे परीक्षण करते हैं कि y.p z है और यदि ऐसा है तो x.p से y सेट करें। लेकिन एक्स पहले से ही y.right है, तो यह y.right.p = y कहने जैसा है, लेकिन y.right.p पहले से ही y है! वे ऐसा क्यों कर रहे हैं?

यहाँ अपने विवरण है ...

"जब y के मूल माता पिता z है, तथापि, हम नहीं x.p y के मूल माता पिता को इंगित करना चाहते हैं, क्योंकि हम पेड़ से उस नोड निकाल रहे हैं। नोड y, लाइन में y के लिए XP की स्थापना 13 कारणों XP y के माता-पिता की मूल स्थिति को इंगित करने के पेड़ में जेड के स्थान लेने के लिए, भले ही एक्स == T.nil

तो चले जाएँगे क्योंकि। " वे एक्स के माता-पिता को y होना चाहते हैं ... यह पहले से ही y है ...

Answer 1

वे पाठ में बताते हैं कि एक्स भी निल हो सकता है, यानी जब y.right शून्य है। ऐसा लगता है कि इस कोड में नील भी नोड द्वारा दर्शाया गया है, और वे एक लटकते सूचक को छोड़ना नहीं चाहते हैं।