algorithm - 如何判断红黑树是否可以有 X 个黑色节点和 Y 个红色节点

Question

下周我有一个算法考试，并被要求准备考试。其中一个问题让我很难过。

“我们可以画一棵有7个黑色节点和10个红色节点的红黑树吗？为什么？”

听起来可以很快回答，但我无法解决这个问题。

CRLS 为我们提供了具有 n 个内部节点的 RB 树的最大高度：2*lg(n+1)。

我认为这个问题可以单独使用这个引理来解决，但我不确定。

有小费吗？

Answer 1

由于这是考试准备，我不想给你一个直接的答案，但我认为你需要考虑的是控制你如何构建红黑树的属性：

1. 一个节点要么是红色的，要么是黑色的。
2. 根是黑色的。（此规则有时在其他定义中被省略。由于根始终可以从红色变为黑色，但不一定相反，此规则对分析几乎没有影响。）
3. 所有的叶子都是黑色的。
4. 每个红色节点的两个孩子都是黑色的。
5. 从给定节点到其任何后代叶子的每条简单路径都包含相同数量的黑色节点。

（从维基百科页面窃取这些：http ://en.wikipedia.org/wiki/Red-black_tree ）

鉴于您列出的节点数，您能否满足所有这些属性？

Answer 2

答案很简单。

正如我们所知，红色节点只能有黑色父节点。最大节点数。节点数将是当每个黑色节点的两个子节点都是红色时，因此每个黑色节点都有红色父节点。因此，对于“n”个黑色节点，“2n”个红色节点是可能的。

这样想：

1. 放置第一个节点（即根节点）并使其变黑
2. 让两个孩子都变红
3. 将这两个红色节点的左右子节点设为黑色，对于所有这些黑色节点，
4. 遵循与 root 相同的过程，直到黑色节点计数达到给定值（在本例中为 7）

希望这可以帮助您可视化解决方案。

Answer 3

答案主要取决于您的 RB 树是否在叶子上使用黑色虚拟节点，如果是，它们被包括在七个黑色节点的计数中。如果不是，请考虑一棵由七个黑色节点组成的完整树

        *
       / \
      *   *
     /\   /\
    *  * *  *

添加十个红色节点不会有太多麻烦。