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

Question

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.

Answer 1

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 
}