Red-Black Tree Red Node Count

A red–black tree is a kind of binary search tree in which each node is colored either red or black. In this problem we assume that all external (null) pointers are regarded as pointing to external nodes which are black and have a height of ( -1 ). A red–black tree is a colored binary search tree satisfying the following properties:

1. Every node is colored either red or black;
2. Every external (null) node is black;
3. The children of any red node are black;
4. For every node, all paths from that node to its descendant external nodes contain the same number of black nodes.

For any node ( x ) (not including ( x ) itself) the number of black nodes on any path from ( x ) to an external node is called the black–height of ( x ), denoted by ( bh(x) ). The black–height of the red–black tree is defined as the black–height of its root.

Given a positive integer ( N ) (which will always be odd, because red–black trees are full binary trees), design an algorithm to compute the minimum and maximum number of red internal nodes among all red–black trees with ( N ) internal nodes. (Note that an internal node is any node in the tree, and the external nodes are the null pointers which are always black.)

It is easy to see that the minimum number of red nodes is ( 0 ) (obtained by coloring all nodes black). The challenge is to maximize the number of red nodes while still meeting all the red–black properties.

A valid red–black tree may have a red root (since the property forcing a black root is not assumed here) so you should consider both possibilities.

A hint to solve the problem: use dynamic programming over the number of nodes and possible black–heights. Define a function ( dp(n, c) ) that returns, for a tree of ( n ) nodes with root color ( c ) (where ( c = 0 ) means black and ( c = 1 ) means red), a mapping from possible black–heights to the maximum red node count achievable. For a single–node tree (i.e. ( n = 1 )), if the node is black then the mapping is {1: 0} (black–height = 1 and 0 red nodes), while if it is red the mapping is {0: 1}. For a tree with ( n \ge 3 ) (note ( n ) will always be odd) you partition the ( n-1 ) remaining nodes between the left and right subtrees. When the current node is black the black–height increases by one – and the children may be either color; when the current node is red, its children must be black (by property 3) and the black–height remains the same. Combine the solutions from the two subtrees (only those pairs with the same black–height can form a valid red–black tree) and take the maximum red node count. Finally, the answer will be ( 0 ) for the minimum red nodes and the maximum red count taken over both color choices for the root.

Your task is to output two integers separated by a space: the minimum red count (which is always ( 0 )) and the maximum red count for the given ( N ).

inputFormat

A single line containing a positive odd integer ( N ) representing the number of internal nodes in the red–black tree.

outputFormat

Output two space–separated integers: the minimum and the maximum number of red internal nodes among all valid red–black trees with ( N ) nodes.

sample

1

0 1