On Red Black Tree rotation, is the black height of all nodes preserved?

Question

I was asked this question in an exam, but I'm not really convinced with the answer from the teacher, and I would like to ask what do you think about it.

A rotation on a red-black tree...

1. preserves the black height of all nodes.
2. preserves in-order ordering.

Which above the above statements are true:

    A. (1) alone
    B. (2) alone
    C. Both (1) and (2)
    D. Neither (1) nor (2).

The teacher claims a rotation doesn't preserve the black height, and the answer is B: it preserves in-order ordering only. However, I strongly believe that it preserves the black height of all nodes and the answer is C, not B.

Am I right or is my teacher right?

Answer 1

Your teacher is right. On Wikipedia we find an example of a rotation at "insert case 5":

The left side is a simple variant, and the right side a more elaborate case.

The second row shows the result of a rotation. It is clear that as the black root moved to the right subtree, the nodes in the left subtree lose a black node on their paths, and so there is a black violation.

Note that after such a rotation there often is a way to change the color of one or more nodes to resolve the black violation. This is what is pictured in the bottom row of the image. But this action is not part of the rotation.

Answer 2

I agree with your Professor. I don't agree with you on the black height is preserved for all nodes, because the rotations (as well as node recolourations are part of group of operations designed to restore red-black properties)

Typically

Red-Black Tree Insertion violates the property of not having 2 red nodes in succession. Red-Black Tree Deletion violates the property of all black tree heights from the root are the same.

So any fixups are done on nodes in the direction of the root of the tree and there may be O((log2(h /2)) recolourations and up to 2 rotations for Inserts O(log2(h)) recolourations and up to 3 rotations for Deletes

It is only final part of the fixup that restores the full set of invariants for a Red-Black tree and any on-the-way partial fixups may still leave the tree needing further fixups until the offending violations are resolved.

Answer 3

This is the image received

Many thanks for the replies. By looking at the material provided it becomes easier to understand and conclude that's not part of the rotation, however, by looking at the picture attached, you can't really say that the black height isn't preserved on rotation, and that's what we had as the base. I believe the issue was with the material provided, which wasn't clear as you can see. But I do see why the balancing of color is not included on rotation.

Anyhow, the balance condition is maintained during insertions and deletions.