时间限制： 1.0 秒

空间限制： 512 MB

题目背景

红黑树是一种适度平衡的二叉搜索树。它具有以下 5 个属性：

• 所有节点的颜色为红色或者黑色；
• 根节点为黑色；
• 所有外部节点均视为黑色；
• 红色节点的两个子节点均为黑色；
• 从任意一个节点向下出发，到达所有外部节点的路径，都包含等量的黑色节点。

例如，下列三张图中，左图中的二叉树是红黑树，其余两图中的二叉树不是红黑树。

题目描述

已知一棵红黑树中有 $n$ 个内部节点，求其最少以及最多可以有多少红节点？

输入格式

从标准输入读入数据。

输入一个整数，表示 $n$。

输出格式

输出到标准输出。

输出两行，每行各一个整数。第一行为红节点的个数最小值，第二行为红节点的个数最大值。

特殊地，如果无解，则输出两行 $-1$ 即可。

3

0
2

样例 1 解释

显然，红节点最少的情况就是 3 个节点均为黑节点构成满二叉树，最多的情况就是 1 个黑节点下面接 2 个红节点构成满二叉树。

子任务

对于所有数据，$1\le n\le 50$。

提示 0

本题设置的数据范围相对宽松，但是也不是纯手算就能通过的。

此外，请注意本题与其他两个红黑树最多最少节点给定条件的区别。

提示 1

注意一下邓俊辉数据结构教材中给出的如下图示：

也就是说，对于题目中定义的红黑树，可以有以下的递推关系：

• 如果有 $2$ 个黑高度为 $h$ 的红黑树，则加上 $1$ 个黑节点作为父亲，构成的树是一个黑高度为 $h+1$ 的红黑树；
• 如果有 $3$ 个黑高度为 $h$ 的红黑树，则加上 $1$ 个黑节点和 $1$ 个红节点作为父亲，构成的树是一个黑高度为 $h+1$ 的红黑树；
• 如果有 $4$ 个黑高度为 $h$ 的红黑树，则加上 $1$ 个黑节点和 $2$ 个红节点作为父亲，构成的树是一个黑高度为 $h+1$ 的红黑树；

提示 2

本题的内部节点个数给定，因此在递推的过程中，我们可以设计如下状态：设 $f_{n,h}$ 为内部节点个数为 $n$，黑高度为 $h$ 的红黑树当中，最多/最少的红节点个数。然后根据提示 1 的递推关系设计状态转移。

提示 3

因为红黑树等价于 2,4 B-Tree，因此 $n$ 个内部节点的红黑树，其黑高度必然不超过 $2\log_2(n+1)$。可以仔细琢磨一下，状态转移中的黑高度一维是否重要呢？

提示 4

当然，你也可以采用其他的状态转移方式。比如说将根节点为红节点（除此之外满足其他 4 个条件）纳入状态转移的考虑当中，只不过最后输出的时候还要输出满足根节点为黑节点的结果。

来源

826 考研初试 2025《数据结构》填空题（拓展）