Why are newly inserted nodes are always colored red in red black tree insert operation?
<p>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.</p>

<p>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.  </p>