P5566 [SDOI2008] Red-Black Tree

A red-black tree is a special kind of binary search tree, where each node is colored either red or black. If we treat the null pointers in a binary search tree as pointing to null nodes, then these null nodes are called the sentinel (leaf) nodes of the binary search tree. It is also specified that the height of all sentinel nodes is $-1$. A red-black tree is a colored binary search tree that satisfies the following “red-black properties”: 1. Each node is colored either red or black. 2. Each sentinel node is black. 3. The children of any red node are all black nodes. 4. On all paths from any node to any sentinel node among its descendants, the number of black nodes is the same. Starting from any node $x$ in a red-black tree (excluding node $x$ itself), the number of black nodes on any path to a sentinel node is called the black height of node $x$, denoted as $bh(x)$. The black height of a red-black tree is defined as the black height of its root. Given a positive integer $N$, design an algorithm to compute, among all red-black trees with $N$ nodes, the minimum and maximum possible numbers of red internal nodes.

Input a number $N$.

Output two lines. The first line is the minimum number of red internal nodes. The second line is the maximum number of red internal nodes.

Constraints: $N \leq 5000$ Translated by ChatGPT 5