Why don't we add a black node instead of a red node in Red Black tree insertion?

Question

In red black tree insertion, we always choose to add a new node as red so that we can avoid changing the black height of the tree. Why this is more desirable than adding a black node?

Answer 1

I think this is due to the rules of red black trees...

1. A node is either red or black.
2. The root is black.
3. All leaves (NIL) are black.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

An insertion is added at the bottom of the tree, replacing a leaf (black nil) node with a node with a value and 2 black nil children. Rule 5 stipulates that the count of black nodes must be the same on every path. If you added a black node, you would violate this rule. I will try to illustrate.

                       B(10)
             R(5)                    B(15) 
    B(1)              B(6)       B(NIL)   B(NIL)
B(NIL) B(NIL)    B(NIL) B(NIL)

You will notice that on every path there are 3 black nodes. If you were to attempt to insert a new node 16 under 15 as a black node (keep in mind you are adding 2 black nil nodes under the node you are adding), that path would become longer (4). It would be incorrect like this:

                       B(10)
             R(5)                     B(15) 
    B(1)              B(6)       B(NIL)     B(16)
B(NIL) B(NIL)    B(NIL) B(NIL)          B(NIL) B(NIL)

To keep all the rules satisfied, you need to insert a red node, and the count of black nodes on every path will remain equal.

                       B(10)
             R(5)                     B(15) 
    B(1)              B(6)       B(NIL)     R(16)
B(NIL) B(NIL)    B(NIL) B(NIL)          B(NIL) B(NIL)