给定一个有 n 个节点的红黑树，在任何根到叶路径上的红色节点的最大数量是多少？
Given a red-black tree on n nodes, what is the maximum number of red nodes on any root to leaf path?
这是一道测验题。我不确定我的回答是否正确。请帮帮我。
假设高度是h，因为没有两个连续的节点（当我们在树上往上）可以是红色的，那么红色节点的最大数量不是h/2吗？ (h = log n)
不知何故，我觉得这不是正确答案。
任何 help/input 将不胜感激！
非常感谢您！
** 编辑 ** 这个答案假定高度的定义是从根到叶的最长路径中的节点数（例如，在 lecture notes here 中使用），包括 "virtual"黑色叶节点。更常见的定义是计算边数，不包括叶节点。根据这个定义，答案是 round(h/2)，如果将叶节点包含在高度 round_down(h/2) 中。 ** 编辑结束**
如果按照Wikipedia中根节点为黑色的规则，那么正确答案是小于h/2的最大整数。这是因为根和叶是黑色的，而中间的一半节点（四舍五入）可以是红色的。 IE。 round((h-2)/2)
你也可以通过考虑一些不同高度的小红黑树来找到规律。
案例h=1根是黑色->0个红色节点
案例'h=2'根是黑色叶子是黑色-> 0个红色节点
案例h=3根是黑色，第二层可以是红色，叶子必须是黑色-> 最多1个红色节点
案例h=4根是黑色，第二层可以是红色，第三层必须是黑色，叶子必须是黑色-> 最多1个红色节点
Case h=5 black, red, black, red, black -> 最多 2 个红色节点。
h作为n的函数比较棘手，但可以证明h <= 2 log (n+1)，保证了对数搜索时间。有关证明，请参见 Searching and Search Trees II (page 11)。证明是基于红黑树的规则保证从x开始的子树至少包含2^(bh(x)) - 1个内部节点，其中bh(x)是黑高-个数从根到叶的路径中的黑色节点。这是归纳法证明的。然后注意到最多一半的节点是黑色的（我们说的是子树，所以根可以是红色的）bh(x) >= h/2。现在使用这些结果我们得到 n >= 2^bh(x) - 1 >= 2^(h/2) -1。求解 h，我们得到答案 h <= 2 log(n+1)。
由于题目是测验，所以说h与log(n)成正比，甚至大约log(n)就足够了。
让我们先看看需要多少个节点（最小化n）来创建一个有1个红色节点（*是黑色）的路径：
*
/ \
* R
/ \
* *
所以当需要1个红色节点时，n必须至少为5。它有 3 个叶节点和 2 个内部节点。删除任何节点都需要删除红色节点并保持在 the rules.
内
如果我们想扩展这棵树以获得具有 2 个红色节点的路径，我们可以应用以下两个步骤：
- 所有叶子都得到两个黑色children
- right-most叶子（刚刚添加的）变成红色节点，得到2个黑色children。
美元符号是与之前的树相比添加的黑色节点：
*
/ \
* R
/| / \
$ $ * *
/| / \
$ $ $ R
/ \
$ $
我们选择将红色节点放在右侧的路径；这个选择不影响结论。请注意，在其他更短的路径中添加红色节点没有帮助，因为这只会增加节点数量，而不会增加红色节点最多的路径。
叶子节点 (L) 的数量在步骤 1 中加倍，而叶子节点成为内部节点 (I)。
第二步将内部节点数和叶子数都增加1。更正式地说，我们可以找到这些公式，其中索引r表示红色节点数：
L1 = 3
我1 = 2
Lr+1 = 2Lr + 1
Ir+1 = Ir + Lr + 1
输入一个table增加r:
r | L | I | n=L+I
----+-----+-----+-------
1 | 3 | 2 | 5
2 | 7 | 6 | 13
3 | 15 | 14 | 29
4 | 31 | 30 | 61
... | ... | ... | ...
我们可以看出以下是正确的：
Lr = 2r+1 - 1
Ir = 2r+1 - 2
等等：
nr = 2r+2 - 3
所以我们有一个公式可以知道具有 r 个红色节点的路径所需的最少节点数。我们需要一个不同的关系：给定 n.
时 r 的最大值
由上可得：
r = ⌊ log2(n+3) ⌋ - 2
这是一道测验题。我不确定我的回答是否正确。请帮帮我。
假设高度是h，因为没有两个连续的节点（当我们在树上往上）可以是红色的，那么红色节点的最大数量不是h/2吗？ (h = log n)
不知何故，我觉得这不是正确答案。
任何 help/input 将不胜感激！
非常感谢您！
** 编辑 ** 这个答案假定高度的定义是从根到叶的最长路径中的节点数（例如，在 lecture notes here 中使用），包括 "virtual"黑色叶节点。更常见的定义是计算边数，不包括叶节点。根据这个定义，答案是 round(h/2)，如果将叶节点包含在高度 round_down(h/2) 中。 ** 编辑结束**
如果按照Wikipedia中根节点为黑色的规则，那么正确答案是小于h/2的最大整数。这是因为根和叶是黑色的，而中间的一半节点（四舍五入）可以是红色的。 IE。 round((h-2)/2)
你也可以通过考虑一些不同高度的小红黑树来找到规律。
案例h=1根是黑色->0个红色节点
案例'h=2'根是黑色叶子是黑色-> 0个红色节点
案例h=3根是黑色，第二层可以是红色，叶子必须是黑色-> 最多1个红色节点
案例h=4根是黑色，第二层可以是红色，第三层必须是黑色，叶子必须是黑色-> 最多1个红色节点
Case h=5 black, red, black, red, black -> 最多 2 个红色节点。
h作为n的函数比较棘手，但可以证明h <= 2 log (n+1)，保证了对数搜索时间。有关证明，请参见 Searching and Search Trees II (page 11)。证明是基于红黑树的规则保证从x开始的子树至少包含2^(bh(x)) - 1个内部节点，其中bh(x)是黑高-个数从根到叶的路径中的黑色节点。这是归纳法证明的。然后注意到最多一半的节点是黑色的（我们说的是子树，所以根可以是红色的）bh(x) >= h/2。现在使用这些结果我们得到 n >= 2^bh(x) - 1 >= 2^(h/2) -1。求解 h，我们得到答案 h <= 2 log(n+1)。
由于题目是测验，所以说h与log(n)成正比，甚至大约log(n)就足够了。
让我们先看看需要多少个节点（最小化n）来创建一个有1个红色节点（*是黑色）的路径：
*
/ \
* R
/ \
* *
所以当需要1个红色节点时，n必须至少为5。它有 3 个叶节点和 2 个内部节点。删除任何节点都需要删除红色节点并保持在 the rules.
内如果我们想扩展这棵树以获得具有 2 个红色节点的路径，我们可以应用以下两个步骤：
- 所有叶子都得到两个黑色children
- right-most叶子（刚刚添加的）变成红色节点，得到2个黑色children。
美元符号是与之前的树相比添加的黑色节点：
*
/ \
* R
/| / \
$ $ * *
/| / \
$ $ $ R
/ \
$ $
我们选择将红色节点放在右侧的路径；这个选择不影响结论。请注意，在其他更短的路径中添加红色节点没有帮助，因为这只会增加节点数量，而不会增加红色节点最多的路径。
叶子节点 (L) 的数量在步骤 1 中加倍，而叶子节点成为内部节点 (I)。 第二步将内部节点数和叶子数都增加1。更正式地说，我们可以找到这些公式，其中索引r表示红色节点数：
L1 = 3
我1 = 2
Lr+1 = 2Lr + 1
Ir+1 = Ir + Lr + 1
输入一个table增加r:
r | L | I | n=L+I
----+-----+-----+-------
1 | 3 | 2 | 5
2 | 7 | 6 | 13
3 | 15 | 14 | 29
4 | 31 | 30 | 61
... | ... | ... | ...
我们可以看出以下是正确的：
Lr = 2r+1 - 1
Ir = 2r+1 - 2
等等：
nr = 2r+2 - 3
所以我们有一个公式可以知道具有 r 个红色节点的路径所需的最少节点数。我们需要一个不同的关系：给定 n.
时 r 的最大值由上可得：
r = ⌊ log2(n+3) ⌋ - 2