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

Question

Hello everyone,

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?