8

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.

1 Answer 1

11

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 
}
2
  • 1
    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.
    – Rufflewind
    Jan 12, 2016 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.