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