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

4
votes

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.

1
algorithmdata-structuresred-black-tree
What thoughts have you had about how that would look, and what the consequences would be? In terms of "research attitude", you've asked a great question -- but in terms of StackOverflow, you've shown much less effort than is usually required of question askers. I encourage you to try to detail what it would mean to "do some appropriate adjustment" and float a hypothesis about why that might be better or worse -- you will be teaching yourself about red-black trees by doing so and you'll get much more engaged answerers here. – Daniel Wagner
@DanielWagner, I think the only reason is, adding a Red node will not break any rules of Red-Black tree on black 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 is impossible. I could be wrong and your advice is appreciated. I will update my thoughts with post as well. – Lin Ma
@DanielWagner, thanks for the advice and vote up your comments. :) – Lin Ma

1 Answers

5
votes
  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.