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

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

Answer 2

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 3

The wikipedia article, based on the same idea, explains it as follow:

In many of the presentations of tree data structures, it is possible for a node to have only one child, and leaf nodes contain data. It is possible to present red–black trees in this paradigm, but it changes several of the properties and complicates the algorithms. For this reason, this article uses "null leaves",

So clearly nothing prevents you to do it your way, but you have to take it in account in your algorithms, which make them significantly more complex. Perhaps this issue can be somewhat alleviated by using OOP, where leaves contain elements, but behave as nodes with empty leaves.

Anyway, it's a trade off: what you would gain in space (roughly two pointers set to NULL in C), you'd probably lose in code complexity, computation time, or in the object runtime representation (specialized methods for the leaves).

Answer 4

Black-height not uniform.

If you count the number of blacks nodes searching NIL nodes from root, 5-1-2-nil has three and 5-7-nil or 5-1-nil only two.

(rule: Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes)