1
$\begingroup$

I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest et al), and have been studying the deletion algorithm for red black trees. However, I am confounded at the moment while I am trying to delete a node from the tree.

The algorithm could be referred at Page No. 324, third edition, Introduction to Algorithms,(CLRS).

Suppose I have a red black tree as follows:

The problem RB Tree

This RB TRee was constructed by inserting the number 1 to 7 in non decreasing order (i.e. 1,2,3,4,5,6,7).

Suppose we wish to delete the root of the tree, node 2.

Then as per the delete algorithm, on page-324,

1. y = z (i.e. y = ROOT of the tree)
2. y-original-color = BLACK
3. z.left exists, skip lines 4-5
6. z.right exists, skip lines 7-8
9. Now y = tree-minimum(z-right), i.e. y is a pointer to 3
10. y-original color = BLACK
11. x = y.right (i.e. T.NIL only)
12. y's parent = pointer to 4, which is not z (i.e. ROOT), skip line 13
14. Else transplant y with y.right, i.e. left of '4' is T.NIL now
15. Lines 15-16 fix the new parent issue for the transplanting node
17. Line 17 transplants z (i.e. the ROOT) with the pointer y, i.e. 3 is the root now
18. Lines 18-21 fix the parent and left child issue for the new ROOT
21. as y-original-color is BLACK, call the RB-DELETE-FIXUP function for x 

As x is T.NIL, this is passed as an argument for the RB-DELETE-FIXUP function. However, there is an issue.

  1. How can we claim the parent of this x, i.e. the T.NIL, for the purpose of finding its sibling?
  2. Even if we claim that 4 be the parent of this x, and 6 be the sibling (as per the diagram), then the deletion falls under none of the categories mentioned in the book, since 6 is a BLACK parent and both of its children are RED.

I have been following the algorithm and have been quite confounded by this case. Maybe there is a misinterpretation on my end regarding following the algorithm. Any help in this regard would be appreciated.

Thankyou.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.