Is this Red-Black tree insertion pseudocode from Introduction to Algorithms (CLRS) correct?

For the Red-black tree insertion fixup the book distinguishes between 6 cases, 3 of which are symmetric. The cases are (z is the node being inserted):

• Case 1: z's uncle is red
• Case 2: z's uncle is black and z is a right child
• Case 3: z's uncle is black and z is a left child

Case 2 is a subset of case 3, as we can transform Case 2 into 3 with a left rotation.

However in the book's pseudocode which you can see here or here they write as follows:

``````if uncle.color == red:
# Handle case
else if z == z.p.right:
# Handle case 2
# Handle case 3
``````

Shouldn't this be:

``````if uncle.color == red:
# Handle case
else:
if z == z.p.right:
# Handle case 2
# Handle case 3
``````

Am I missing something? Does the book use `else if` in a different way than say Python does? The C++ implementation provided here uses the second version as I expected.

The indentation in the code is important:

``````if uncle.color == red:
# Handle case
else if z == z.p.right:
# Handle case 2
# Handle case 3
``````

The syntax is a bit quirky, because they squished the `if` to appear on the same line as the `else`, but case 2 is indented further inward compared to the remaining case 3, indicating that they do not belong to the same group.

This is what I think the author intended:

``````if (uncle.color == red)
{
# Handle case
}
else
{
if (z == z.p.right)
{
# Handle case 2
}
# Handle case 3
}
``````
• Yeah after looking at it some more it makes sense. Still it's not immediately obvious, bad choice of optimizing for LOC vs. readability.
– Bar
Jan 12, 2016 at 16:07
• @RobertHarvey: the code was deliberately written such a contorted way to show where the blocks begin and end. Jan 12, 2016 at 20:42