Introduction To Algorithms 3rd Edition MIT Press: Red Black Tree insertion error in pseudo-code?

I'm implementing the algorithm on page 316 of the book Introduction to Algorithms. When I look at the pseudo-code, I feel that there is something wrong between line 10 to 14. I feel it's missing a check. There is a YouTube video explaining this whole function (and it includes the pseudo-code plus line numbers): https://youtu.be/5IBxA-bZZH8?t=323

The thing is, I think that //case 2 needs its own check. The else if z == z.p.right is both meant for //case 2 and //case 3. However, the code from //case 2 shouldn't always fire. It should only fire when there is a triangle formation according to the YouTube video. In my implementation it always fires, even when it's a line.

So I feel the pseudo-code is wrong, it's also weird that it has an indentation, but I see no extra check.

Am I missing something?

Maybe superfluous, but I also typed the pseudo code given from the book here:

RB-INSERT-FIXUP(T, z)
while  z.p.color == RED
if  z.p == z.p.p.left
y = z.p.p.right

if y.color == RED
z.p.color = BLACK   // case 1
y.color = BLACK     // case 1
z.p.p.color = RED   // case 1
z = z.p.p           // case 1

else if z == z.p.right
z = z.p           // case 2
LEFT-ROTATE(T, z) // case 2
z.p.color = BLACK   // case 3
z.p.p.color = RED   // case 3
RIGHT-ROTATE(T, z.p.p) // case 3

else (same as then clause with "right and "left" exchanged)

T.root.color = BLACK

• Did you check the book's errata list? – David Richerby May 11 '19 at 22:12
• Yes, I didn't find it. I emailed the authors this question as well. – Melvin Roest May 11 '19 at 22:14

In an email with one of the authors it became clear that the following pseudo-code rule applies.

(this is not an actual quote, but the format seems better for this)

Whenever there is an else clause. The first statement of that else clause will be on the same line as the else clause. This can be a variable assignment, an if-statement or other things.

If that was too abstract, the code from question should be interpreted as follows:

RB-INSERT-FIXUP(T, z)
while  z.p.color == RED
if  z.p == z.p.p.left
y = z.p.p.right

if y.color == RED
z.p.color = BLACK   // case 1
y.color = BLACK     // case 1
z.p.p.color = RED   // case 1
z = z.p.p           // case 1

else                  // this is the difference compared to code in the question
if z == z.p.right
z = z.p           // case 2
LEFT-ROTATE(T, z) // case 2
z.p.color = BLACK   // case 3
z.p.p.color = RED   // case 3
RIGHT-ROTATE(T, z.p.p) // case 3

else (same as then clause with "right and "left" exchanged)

T.root.color = BLACK