1
$\begingroup$

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.

enter image description here

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$
4
  • $\begingroup$ After recoloring in (b), the 3rd property may be violated? In the book the 3rd property says that every leaf is black (p. 308). Did you mean that property or another? $\endgroup$
    – Maksim Dmitriev
    Sep 15, 2015 at 5:42
  • $\begingroup$ @MaksimDmitriev No. it's the one i've given above. $\endgroup$
    – Terence Hang
    Sep 15, 2015 at 5:49
  • $\begingroup$ No. We fixed the number of black nodes and got (b). Each simple path from the root node to leaf nodes contains 2 black nodes, not counting black leaves themselves. In fact I know the right answer to my question. I just failed to see one thing in (b). If you find it, I'll accept your answer $\endgroup$
    – Maksim Dmitriev
    Sep 15, 2015 at 6:21
  • $\begingroup$ @MaksimDmitriev. err. sorry, made a mistake. the violated rule is still "children of a red node are black". i've edited my answer. $\endgroup$
    – Terence Hang
    Sep 15, 2015 at 6:36

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.