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 found 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.


1 Answer 1


This is case 4, because w's right child is red. the left child (of z) could have any color red/black.

  • 2
    $\begingroup$ Can you expand your answer so that it becomes legible for people without access to CLRS? For example, I have no idea what "case 4" stands for. $\endgroup$ Sep 3, 2019 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.