How to tell whether a red-black tree can have X black nodes and Y red nodes or not

Question

I have an exam next week in algorithms, and was given questions to prepare for it. One of these questions has me stumped though.

"Can we draw a red-black tree with 7 black nodes and 10 red nodes? why?"

It sounds like it could be answered quickly, but I can't get my mind around it.

The CRLS gives us the maximum height of a RB tree with n internal nodes: 2*lg(n+1).

I think the problem could be solved using this lemma alone, but am not sure.

Any tips?

Answer 1

Since this is exam preparation, I don't want to give you a direct answer, but I think what you need to consider is the properties that govern how you build a Red-Black Tree:

1. A node is either red or black.
2. The root is black. (This rule is sometimes omitted from other definitions. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
3. All leaves 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.

(Stole these from the wikipedia page: http://en.wikipedia.org/wiki/Red-black_tree)

Given the count of nodes you listed, can you meet all of these properties?

Answer 2

the answer is simple.

As we know that a red node can have only black parent.The max no. of nodes will be when each black node's both children are red and, hence, every black node has red parent. So, for 'n' black nodes '2n' red node are possible.

Think it this way:

1. put the first node(which is root) & make it black
2. make both its children red
3. make left and right children of both these red nodes black and for all these black nodes,
4. follow the same procedure as followed with root until black node count reaches the given value (in this case 7)

hope this helped you visualize the solution.

Answer 3

The answer critically depends on whether your RB tree uses black dummy nodes at the leaves, and if so, they are included in the count of seven black nodes. If not, consider a complete tree of seven black nodes

        *
       / \
      *   *
     /\   /\
    *  * *  *

You won't have much trouble adding ten red nodes.