时间限制： 1.0 秒

空间限制： 512 MB

题目背景

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

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

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

题目描述

已知一棵红黑树中有 $n$ 个黑节点（不包含外部节点），求其最少以及最多可以有多少红节点？

输入格式

从标准输入读入数据。

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

输出格式

输出到标准输出。

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

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

1

0
2

样例 1 解释

如图，在只有 1 个黑节点的情况下，最少是没有红节点，最多可以在其下方接上 2 个红节点。

2

-1
-1

样例 2 解释

显然，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$ 个黑节点的红黑树，其黑高度必然不超过 $\log_2(n+1)$。可以仔细琢磨一下，状态转移中的黑高度一维是否重要呢？

来源

826 考研初试 2025《数据结构》填空题