Issue with the Red Black Delete algorithm mentioned in Introduction to Algorithms,CLRS 3rd edition

Question

RB-DELETE(T, z)
1  y = z
2  y-original-color = y.color
3  if z.left == T.nil
4      x = z.right
5      RB-TRANSPLANT(T, z, z.right)
6  elif z.right == T.nil
7      x = z.left
8      RB-TRANSPLANT(T, z, z.left)
9  else
10     y = TREE-MINIMUM(z.right)
11     y-original-color = y.color
12     x = y.right
13     if y.p == z
14           x.p = y   // issue
15     else    
16           RB-TRANSPLANT(T, y, y.right)
17           y.right = z.right
18           y.right.p = y
19     RB-TRANSPLANT(T, z, y)
20     y.left = z.left
21     y.left.p = y
22     y.color = z.color
23 if y-original-color == BLACK
24     RB-DELETE-FIXUP(T, x)

My concern is this: in line 12 we are assigning x as a child of y. and in line 14 ,we are assigning parent of x equal to y. why do we need to assign this in line 14, isn't parent of x is y already(as defined in line 12). I think line 14 should be replaced by simple pass statement.

If you implement it you will know (I don't happen to have that book handy). — 500 - Internal Server Error, May 19 '20 at 09:23
@500-InternalServerError,can you tell me how the implementation will affect this?for example I am implementing this in python, i will just delete line 13,14 and replace line 15 with ```if y.p != z``` — Mr Sukhe, May 19 '20 at 09:34

score 0 · Answer 1 · answered May 19 '20 at 09:57

I was making a silly mistake, was not considering the case when x is a sentinel nil node.the assignment is necessary for the algorithm, the assignment should take place even if the condition in line 13 doesn't meet, in that case, RB-Transplant subroutine takes care of it.

Issue with the Red Black Delete algorithm mentioned in Introduction to Algorithms,CLRS 3rd edition

1 Answers1

Linked