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 回答