一棵黑色高度为bh(t)的红黑树(最多)有多少个红色节点

具有黑色高度bh(t(的红黑树(最多(有多少个红色节点？

bh(t(=它是任何简单路径上的黑色节点数

我们讲座中的一棵红黑树是一棵具有的二进制搜索树

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

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

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

唯一黑色高度为0的树是空树
唯一一棵黑色高度为1的树是一个黑色节点(根和叶(

脑海中第一棵黑色高度为2的树如下：

b
/ 
b   b

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

b
/ 
R   b
/ 
b   b

我们不能做得更多。没有办法注入第二个红色节点。此树的镜像是唯一一种保持在您列出的约束内的可能性，并且具有2的黑色高度。

这个形状是增加到下一个黑色高度3(或更大(的关键。我将把这个树称为T。

要生成一个黑色高度为3、具有尽可能多的红色节点的树，我们可以用T的副本替换每片叶子(有3片(。结果是：

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

同样，我们可以镜像不同的子树，但无法在黑色高度为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-23_i}}

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

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

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

r₀=0
当h>0

这是一个包含前几个结果的表：

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

相关内容

最新更新

热门标签：