插入后的红黑树结果是否唯一？

Question

假设我有一棵二叉搜索树，最初满足所有红黑树条件，并包含某个集合S中的每个整数s的一个节点。接下来，我想要一个新的节点；比如说a（它不在S中）。 在重新平衡后，这种添加的结果是唯一的吗？ 换句话说：插入一个节点后，是否只有一种方法来重新平衡红黑树？

我认为它们不是唯一的，尽管我没有证据（也没有什么信心）。我只是想知道是否有比我更有经验的人能够帮助我理解。

- Ryan

Answer 1

他们并不是唯一的。

一个简单的证明是进行一些微不足道的算法更改，比如检查我们是否可以改变根节点的颜色，并提供一个仍然有效的案例，例如：

    1-B
   /  \
 0-R  2-R

add(3):

    1-B
   /  \
 0-B  2-B
        \
        3-R

但是新算法同样可以产生...

    1-R
   /  \
 0-B  2-B
        \
        3-R

根节点的颜色不同，但这两棵树仍然是有效的红黑树。这可能看起来有点琐碎，但如果您想要一个不那么琐碎的证明，您可以将这个想法扩展到检查不止根节点。您可以检查 O(1) 层深度以进行非琐碎但有效的更改，这将生成具有相同运行时间的两个不同算法。例如，检查前10行是否完整且为黑色，并将奇数行更改为红色，将产生额外的常数工作（即O(1)），并生成一个新算法。我应该指出，这只是非唯一性的证明，而不是非唯一性数量的界限。也就是说，像这样的琐碎事情足以证明这一点，但它为在更基本方面不同的 RB 算法打开了大门。

- davin

---

很抱歉，我一直在阅读并试图理解它，但是遇到了困难。你的例子的关键是我们可以更改算法并显示两个算法都生成有效的红黑树吗？如果我们添加额外的限制，即根始终必须为黑色（尽管在黑高度方面并不重要），会怎样呢？ - Ryan

@Ryan，这就是为什么我解释说这个想法可以超越根节点。而且，是的，这个想法是我们可以生成两个算法，在某些情况下会产生两个不同的有效的RB树。 - davin

哦，我明白了——当你说O(1)层深度时，是相对于根节点还是刚添加的节点？（也许这并不重要）。如果我理解有误，请纠正我，但你的意思是：我可能有两个算法，唯一的区别在于一个进行了非平凡但有效的更改，仍然保持红黑树的完整性。也许像将第二层的两个节点都改为黑色（因为这不会改变任何叶子节点的黑高度）。因此，我证明了这些算法并不唯一。 - Ryan

@Ryan，相对于根节点的O(1)。你是正确的，那就是这个想法，尽管我在最后指出，这并不意味着RB算法的差异就此结束。仍然可能存在更一般的差异。 - davin

因此，请原谅我在这里的草率概括，但是，可以说任何红黑算法中插入/删除的不变量仅仅是满足4（或5）个红黑属性，而不管如何操作树来实现吗？也许我表达得不对（只是试图在这方面建立更多的直觉）。 - Ryan

@Ryan，确实，这将是一种有效的方式来分类所有RB算法，它具有灵活性，允许优化和变化。 - davin

Answer 2

不，有多个算法。

让我们从这两个命题开始：

• 有 4 个内部节点的红黑树数量为 3
• 有 5 个内部节点的红黑树数量为 8

现在，假设有一种唯一的算法可以将一个节点添加到具有 4 个内部节点的红黑树中。那么，由于该算法只会导致一种结果，因此应该只有 3 个带有 5 个内部节点的红黑树。

这是荒谬的，因为有 5 个内部节点的红黑树的数量是 8。

(参见鸽巢原理)

因此，存在多个“红黑”算法。

希望我理解了您的意思。

- Ricky Bobby

---

我喜欢这种方法，但是我需要再考虑一下（过多地抽象细节对我来说有些困惑）。 - Ryan

我现在明白你的意思了。然而，如果我们向4节点红黑树中添加一个随机节点，结果只能是具有5个内部节点的8个红黑树形式之一。但问题是：在固定a（我们将要添加的节点）的情况下，是否存在多个具有5个内部节点的解？ - Ryan

对于一个4节点树，最多有4个位置可以添加一个节点来创建一个5节点树。如果存在8个5节点树，则至少有一种方法可以添加一个具有超过2个可能的RB输出树的节点（鸽笼原理），因此存在一个回答您问题的'a'。但是您无法证明所有'a'都成立。实际上，Davin的证明只证明了一种情况，而不是所有添加的节点（请参见Davin证明中的第二条评论：“在某些情况下”）。 - Ricky Bobby

在一个4内部节点树中，不是有6个可能的位置可以添加一个节点吗？ - Ryan