Is this red-black tree insertion "fix-up" algorithm incomplete?

0
votes

I'm reading Introduction to Algorithms, 3rd Edition (ISBN-10: 9780262033848) and in it is the following algorithm to "fix" a red-black tree after the insertion of a red node.

enter image description here

On line 3 it says to set y = to 'z's parent's parent's right child' (z's right uncle). My question is, what if z is only the third insertion and it is a left child of a left child? Wouldn't there need to be another case that handles z not having a right uncle but its parent being a red left child? 

   gp (blck)
   /
  p (red)
 /
z (red)
1
algorithmbinary-search-treered-black-treered-black-tree-insertion

1 Answers

1
votes

The third case has already been taken care of by the lines 12-14.

Have a look at following image which explains your case:

enter image description here

Feel free to ask any doubts