CODEWITHSUNDEEP
algorithmdata-structuresred-black-tree
Mr Sukhe
Mr Sukhe

Reputation: 77

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

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.

Upvotes: 1

Views: 297

Answers (2)

Jason
Jason

Reputation: 3535

In line 12, although x is the y.right, however, if x is a sentinel nil at the moment of line 12, then x.p is just an arbitrary value, not defined. Therefore, it becomes necessary to reinstate x.p = y in line 14

Upvotes: 0

Mr Sukhe
Mr Sukhe

Reputation: 77

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.

Upvotes: 0

Related Questions