1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Did you check the book's errata list? $\endgroup$ – David Richerby May 11 at 22:12
  • $\begingroup$ Yes, I didn't find it. I emailed the authors this question as well. $\endgroup$ – Melvin Roest May 11 at 22:14
3
$\begingroup$

In an email with one of the authors it became clear that the following pseudo-code rule applies.

(this is not an actual quote, but the format seems better for this)

Whenever there is an else clause. The first statement of that else clause will be on the same line as the else clause. This can be a variable assignment, an if-statement or other things.

If that was too abstract, the code from question should be interpreted as follows:

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                  // this is the difference compared to code in the question
        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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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