algorithm - 为什么每次插入左倾红黑树后都需要将根着色为黑色？

Question

在 Sedgewick 的左倾红黑树（在他的论文或他的算法书中介绍）中，对标准 BST 的一个修改是在每次插入后将根节点涂成黑色，root.color = BLACK参见insert(Key, Value).

我明白这在语义上是必要的，因为根节点永远不应该是 3 节点/4 节点的左子节点。但是，我不明白为什么在实践中这是必要的，因为似乎从未检查过根节点的颜色。谁能指出我在这里缺少什么？

标签： algorithmdata-structuresbinary-search-treered-black-tree

Answer 1

检查代码后，我得出了与您相同的结论，即从未实际使用过根颜色。

因此，我进行了一些测试以尝试确认这一点，在此过程中，我发现该论文中提供的代码中实际上存在一堆小错误：对从未定义的方法的调用，对从未声明的变量的赋值，不必要的重复昂贵的方法调用，未使用的对象引用（=指针）等等。

当然，这些都不是一个非常严重的问题，因为它们都不需要太多的努力来解决；但我认为你的问题只有在代码完美或接近完美的情况下才真正有意义，而事实并非如此。鉴于代码有几十个编译错误和几个不涉及红黑语义的明显非最佳位，我认为争论它是否真的需要设置根节点颜色是没有意义的语义预期的方式。

但是对于它的价值，我的测试表明根颜色确实无关紧要。我写了一个验证方法来验证适当的不变量（没有红色的非根节点有一个红色的孩子，并且所有的叶子节点都有相同的黑色深度），我发现无论我是否注释掉这些行，这些都被保留了将根颜色设置为黑色。（当然，这仅对我测试的案例进行了演示，但仍然足以让我对结论更有信心。具体来说，我的案例涉及按顺序、反向或随机添加键 1 到 1000 - 打乱顺序，然后按顺序、反向顺序或随机打乱顺序删除它们。我在每次插入或删除后验证了不变量。）