具有黑色高度 bh(t) 的 red-black-tree 最多有多少个红色节点？

Question

一个red-black-tree黑色高度bh(t)最多有多少个红色节点？

bh(t) = 任意简单路径上的黑色节点数

我们讲的红黑树是二叉搜索树

所有节点都有2个children（叶节点除外）
每个节点都是红色或黑色
根节点和所有叶节点都是黑色
一个红色节点的所有children都是黑色
一个黑色节点最多可以有一个红色节点children
从根到叶子的所有路径都有相同数量的黑色节点

我找不到答案。有人可以帮我吗？

Answer 1

我确实注意到这个定义比通常的定义更受限制：在标准定义中要求 5 不存在，红色节点可以是兄弟节点。但是考虑到这个额外的限制我们可以做如下分析：

唯一一棵 black-height 为 0 的树是空树。
唯一一棵 black-height 为 1 的树是单个黑色节点（根和叶）

第一个想到 black-height 为 2 的树是以下树：

                 b
                / \
               b   b

我们可以选择这两个叶子中的一个扩展成一个红色节点，有两个黑色子节点：

我们不能做更多了。没有办法注入第二个红色节点。这棵树的镜像是保持在您列出的约束范围内的唯一其他可能性，并且 black-height 为 2.

这个形状是递增到下一个 black-height 3（和更大）的关键。我将这棵树命名为T.

要生成一棵 black-height 为 3 的树，并具有尽可能多的红色节点，我们可以替换每个叶子（有 3 个）一个副本T。结果是这样的：

                 _____ b_____
                /            \
               R              b
             /   \           / \
           b       b        R   b
          / \     / \      / \
         R   b   R   b    b   b
        / \     / \
       b   b   b   b

同样，我们可以镜像不同的子树，但是无法在 black-height 为 3 的树中获得更多的红色节点。

现在考虑一下：在这个扩展中，我们用 T 替换了每个现有的叶子，并且由于 T 有一个红色节点，我们实际上添加与叶子相同数量的红色节点。由于 T 有 3 个叶子，我们将叶子的数量乘以 3，这将决定我们将在下一次扩展中注入多少棵 T 树...等等

这给了我们一个递归关系——我写r_h来表示黑色树中红色节点的最大数量身高h:

r₀ = 0
r₁ = 0
r₂ = 1
r_h = 1 + 3r_h-1

在直接公式中，最后一个等式变为：

r_h = ∑_{_i=1..h-2} 3^我

这样的和可以重写为以 3 为基数的 1 位数字的重复，因此我们可以得出：

r_h = (3^h-1 - 1) / 2

这个公式对于h=1和h=2也给出了正确的结果，所以我们只需要添加大小写h=0:

r₀ = 0
r_h = (3^h-1 - 1) / 2, 当 h > 0

这是一个 table 的前几个结果：

black height (h) | max number of red nodes (r[h])
-----------------+----------------------------------------
           0     |     0
           1     |     0
           2     |     1
           3     |     4
           4     |    13
           5     |    40
           6     |   121
           7     |   364
           8     |  1093
          ...    |   ...
           h     |  (3^(h-1) - 1) / 2

具有黑色高度 bh(t) 的 red-black-tree 最多有多少个红色节点？

How many red nodes does a red-black-tree with black height bh(t) have(at most)?

height

red-black-tree