黑色高度为 k 的红黑树中的最小内部节点数为 2 k -1，即下图中的一个：
黑色高度为 k 的内部节点的最大数量为 2 2k -1，如果黑色高度为 2，则应为 2 4 - 1 = 15。但是，请考虑以下图像：
内部节点数为7。我做错了什么？
问问题
21305 次
8 回答
11
（我已经完全重写了这个答案，因为正如评论者所指出的，它最初是不正确的。）
我认为通过使用红黑树和 2-3-4 树之间的等距来考虑这个问题可能会有所帮助。具体来说，黑色高度为h的红黑树对应高度为h的2-3-4树，其中每个红色节点对应多键节点中的一个键。
这种联系使我们更容易进行一些巧妙的观察。首先，底层的任何 2-3-4 树节点都对应一个黑色节点，没有红色子节点、一个红色子节点或两个红色子节点。这些是红黑树中唯一可以成为叶节点的节点。如果我们想最大化树中的总节点数，我们想让 2-3-4 树只有 4 个节点，它（在等距下）映射到一个红/黑树，其中每个黑色节点有两个红色的孩子。一个有趣的效果是它使树层的颜色在黑色和红色之间交替，顶层（包含根）是黑色的。
本质上，这归结为计算高度为 2h - 1 的完整二叉树中的内部节点数（2h 层在黑色和红色之间交替）。这等于高度为 2h - 2 的完整二叉树中的节点数（因为如果你拔掉所有的叶子，你会得到一棵高度比你开始时低 1 的完整树）。计算结果为 2 2h - 1 - 1，这与给你的数字不同（我现在确信这是不正确的），但与你得到的数字相匹配。
于 2013-10-13T21:17:13.523 回答
7
如果不是这个公式不起作用，您需要计算树中的黑色 NIL 叶子。根不能是违反红黑树属性之一的 RED。
于 2014-10-26T01:54:18.283 回答
3
问题是您误解了黑色高度。红黑树中节点的黑色高度是从当前节点到叶子的黑色节点数，不包括当前节点。（这在每条路线中都是相同的值）。因此，如果您只为每个红色节点添加两个黑色叶子，您将得到一棵黑色高度为 2 和 15 个内部节点的红黑树。
（同样在红黑树中，每个红色节点都有两个黑色子节点，因此红色节点不能是叶子。）
于 2015-03-25T21:06:35.570 回答
1
在阅读了上面的讨论之后，如果我添加具有红色属性的根，我添加的第二个节点将再次变为红色，这将是红色违规，并且在节点重组后，我假设我们再次到达根黑色和红色子！我们可能无法获得 (2^2k)-1 个最大内部节点。我在这里错过了什么吗，最近才开始研究 rbt ......
于 2013-10-15T06:17:13.673 回答
0
似乎您还没有考虑过“黑叶”（黑色节点）——上一层每个红色节点的 2 个 NIL 节点。如果您将 NIL 节点视为叶子，则最后一级的红色节点现在被计为内部节点，总计 15 个。
于 2014-06-01T03:53:01.753 回答
0
这里给出的树实际上有 15 个内部节点。缺少最后一层红色节点的 NIL 黑色子节点，它们实际上称为外部节点（没有密钥的节点）。树的黑高为 2。黑高为 k 的树的最大内部节点数的实际表达式为 4^(k)-1。在这种情况下，结果是 15。
于 2015-06-14T09:19:07.453 回答
0
在红黑树中，外部节点[空节点]始终为黑色，但在您对第二棵树的问题中，您没有提到外部节点，因此您的计数为 7，但如果您提到外部节点 [空节点] 然后计算内部节点，您可以看到结果是 15。
于 2016-10-19T00:58:12.713 回答
-1
不确定我是否理解这个问题。对于所有层（除了最后一层）都具有最大项目数的任何二叉树，我们将有 2^(k-1)-1 个内部节点，其中 k 是层数。在第二张图片中，您有 4 层，因此内部节点数为 2^(4-1)-1=7
于 2013-10-13T21:15:16.923 回答