如何判断一棵红黑树是否可以有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. 遵循与根节点跟随的相同过程，直到黑节点计数达到给定值（在本例中为7）

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

Answer 3

答案关键取决于您的RB树是否在树叶上使用了黑色虚拟节点，如果是这样，它们包含在七个黑色节点的计数中。如果没有，请考虑一个包含七个黑色节点的完整树

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

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