Inserting into red black tree

Question

I am taking an algorithms course and in my course slides, there is an example of insertion into a red-black tree:

My question is, why don't we let "2" be a leaf node here? It looks like if we let it be a leaf node, then no condition of a red black tree is violated. What am I missing here?

Answer 1

The Problem is not with the position of 2 the the second tree of your image but the color of different nodes. Here is the explanation:

1st Rule of insertion in Red-Black tree is: the newly inserted node has to be always Red. You fall in case 3 insertion where both the father and uncle of node 2 is Red. So they are needed to be recolored to Black, and the grandfather will become Red but as the grandfather is root so it will become Black again.

So the new tree (after inserting 2) should be like this (r and b indicate color, .b is Nil node):

       5b
     /    \     
    1b     7b
  /   \    / \
 .b    2r .b  .b
       / \
      .b  .b

And why we always need to insert red node in RBT, you may ask? Answer is, 1st we know every NIL nodes are always Black in RBT, 2nd we have rule 5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. Now if we insert a black node at the end the tree will violate this rule, just put 2b in above tree instead of 2r and keep color of 1 and 7 red, then count black node from root to any Nil node, you will see some path have 2 back nodes and some path have 3 black nodes.

Answer 2

All the leaves of a Red Black tree have to be NIL Check property 3