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