8

假设我有一棵二叉搜索树，它最初满足所有红黑条件，并且对于某个集合S中的每个整数s都包含一个节点。接下来，我要新建一个节点；说a（不在S中）。

这种添加的结果在重新平衡后是否独一无二？

换句话说：插入节点后是否只有一种方法可以重新平衡红黑树？

我相信它们并不是独一无二的，尽管我没有提供任何证据（也没有多少信心）。我只是想知道是否有比我更博学的人会如此好心地启迪我？

4

2 回答 2

8

它们不是唯一的。

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

    1-B
   /  \
 0-R  2-R

add(3):

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

但是新算法可以很容易地产生

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

根是不同的颜色，但当然树都是有效的 RB 树。

这可能看起来有点微不足道，但您可以扩展这个想法（如果您想要一个不那么微不足道的证明）以检查不仅仅是根。您可以深入检查 O(1) 级别以进行不重要但有效的更改，这将生成具有相同运行时间的两种不同算法。

例如，检查前 10 行是否已满且为黑色，并将奇数行更改为红色，将产生额外的常数工作（即 O(1)）和新算法。

我应该注意，这只是非唯一性的证明，而不是非唯一性数量的限制。即，像这样微不足道的事情足以证明这一点，但它为在更基本的方式上有所不同的 RB 算法打开了大门。

于 2011-07-19T17:18:52.933 回答
2

不，有多个算法。

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

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

现在，想象有一个独特的算法将一个节点添加到一个 4 内部节点红黑树。那么应该只有 3 个具有 5 个内部节点的红黑树，因为该算法导致一个单一的结果。

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

（参见 鸽子洞原理）

因此有多种“红黑”算法

希望我明白你的意思。

于 2011-07-19T17:15:38.973 回答