Insert red ebony: why enter nodes in red when inserting?

Question

Red Black Tree Properties does not contain any rule for insert node color, as always we add red nodes.

If we insert the black color of the node, does it violate any properties (any rule of 4)?

Answer 1

Oops! Suppose you have one node in your tree:

5 (black) 

Now insert the new black node into the tree:

  5 (black) \ 9 (black) 

Now the invariant that each root-zero path in the tree has the same number of black nodes is broken, since the path from the root to the left has one black node, and the paths from the root to the right have two.

Hope this helps!

Answer 2

You seem to be asking two questions.

1) Why make red dots when pasting (in the header)?

2) Does the insert insert any properties as black?

You also seem to be mistaken that the answer “Yes” for 2) is an automatic justification for 1).

This is not true! Inserting a node in red may also violate one of the properties of the RB tree. For example, if you make a red node a child of another red node, you just broke the property that only black children can have red nodes.

The reason for its red color is that it is “easier” to set the child properties of the node (by rotating and redrawing the parents / grandparents) instead of trying to fix the path-length properties. Perhaps another reason is that the authors came up with.

You can also fix the tree by inserting a black node and not repainting red. Perhaps no one had thought of this yet.