Is this Red-Black tree insertion pseudocode from Introduction to Algorithms (CLRS) correct?
https://softwareengineering.stackexchange.com/questions/307195
-
11-12-2020 - |
Pergunta
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.
Solução
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
}