Why are newly inserted nodes are always colored red in red black tree insert operation?

Question

Wondering why for red black tree insert, we mark the new node as Red first, then do some adjustment? Why not mark it as Black and do some appropriate adjustment? Thanks.

I think the only reason is, adding a Red node will not break any rules of Red-Black tree on black node related rules (e.g. path from root to leaf contains the same number of black nodes), which only needs to adjust any violation of red rules (i.e. cannot be consecutive two red nodes for parent/child), which makes code simple. I do not think add a black node and adjust violations on number of black nodes (on different path) is impossible. In short, adding red node other than black is only for the purpose of code simplicity, no other reasons. If I am wrong, please feel free to correct me.

Answer 1

1. Inserting a red node is less likely to violate the red-black rules than inserting a black one. This is because, if the new red node is attached to a black one, no rule is broken. It doesn’t create a situation in which there are two red nodes together which breaks rule of red parent black children, and it doesn’t change the black height(number of black nodes from root to leaf) in any of the paths.

2. Of course, if you attach a new red node to a red node, the rule of red parent-black children will be violated. However, with any luck this will happen only half the time. Whereas, if you add a new black node, it would always change the black height for its path, violating the black height rule.

3. Also, it’s easier to fix violations of red parent-black children rule than black height rule.

Source: Data Structures & Algorithms in Java Second Edition - Robert Lafore page 437.