时间限制： 1.0 秒

空间限制： 512 MB

题目背景

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

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

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

题目描述

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

输入格式

从标准输入读入数据。

本题包含多组测试数据。

输入的第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

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

输出格式

输出到标准输出。

对于每组测试数据：

输出一行一个整数。为黑节点（不包含外部节点）的个数最小值。

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

2
1
2

1
1

样例 1 解释

显然 1 个红节点或者 2 个红节点都可以只接在 1 个黑节点后面。

子任务

对于所有数据，$1\le T\le 10,~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，因此 $m$ 个黑节点的红黑树，其黑高度必然不超过 $\log_2(m+1)$。又由于是在给定红节点个数下求最少黑节点，黑高度也不会很高。可以仔细琢磨一下，状态转移中的黑高度一维是否重要呢？

提示 4

为什么不问最多的黑节点个数呢？因为很显然是无穷大的呀~

来源

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