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?
Cormen. Red-black trees. Why do we need to rotate the tree after fixing its properties?
algorithms;trees
After recoloring in (b), the following rule is still violated:children of a red node are black.Recoloring while preserving black height in step (b) introduces new double red nodes 2 and 7, which remains after step (c) and finally eliminated in step (d).