I am reading about red-black trees in Introduction to Algorithms, Second Edition by Cormen. Pages 316, 317.
I don't understand why we need to rotate the given tree. See (c) and (d) in the attached picture.
The author says that the following properties of a red-black tree can be violated after a new node has been inserted:
- the root is black;
- children of a red node are black.
The second property is restored in (b). The first property wasn't violated because we didn't insert the tree root. So why do we need to perform any other actions after recoloring?