假设我有一棵二叉搜索树,它最初满足所有红黑条件,并且对于某个集合S中的每个整数s都包含一个节点。接下来,我要新建一个节点;说a(不在S中)。
这种添加的结果在重新平衡后是否独一无二?
换句话说:插入节点后是否只有一种方法可以重新平衡红黑树?
我相信它们并不是独一无二的,尽管我没有提供任何证据(也没有多少信心)。我只是想知道是否有比我更博学的人会如此好心地启迪我?
假设我有一棵二叉搜索树,它最初满足所有红黑条件,并且对于某个集合S中的每个整数s都包含一个节点。接下来,我要新建一个节点;说a(不在S中)。
这种添加的结果在重新平衡后是否独一无二?
换句话说:插入节点后是否只有一种方法可以重新平衡红黑树?
我相信它们并不是独一无二的,尽管我没有提供任何证据(也没有多少信心)。我只是想知道是否有比我更博学的人会如此好心地启迪我?
它们不是唯一的。
一个简单的证明是进行微不足道的算法更改,例如检查我们是否可以更改根的颜色,并提供仍然有效的情况,例如:
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 算法打开了大门。
不,有多个算法。
让我们从这两个命题开始:
现在,想象有一个独特的算法将一个节点添加到一个 4 内部节点红黑树。那么应该只有 3 个具有 5 个内部节点的红黑树,因为该算法导致一个单一的结果。
这很荒谬,因为具有 5 个内部节点的红黑树的数量是 8。
(参见 鸽子洞原理)
因此有多种“红黑”算法
希望我明白你的意思。