algorithm - 在红黑树中旋转后重新着色时要遵循的规则

Question

我只是 RB 树的新手。我只是在旋转后为树重新着色而被绞死。

让我们考虑以下情况:-

插入顺序:34,32,56,30,31

            34 (B)

        32 (B)      56 (B)

    30 (R)

        31 (R)

在上面的例子中，31插入到30的父级时发生颜色冲突，并且高度不稳定。

所以对于树 32、30、31，我们进行左右旋转，这与在 AVL 树中所做的相同。

直到这次轮换，我觉得还好。

但是旋转之后，树会变成这样，

            34 (B)

        31 (R)      56 (B)

    30 (R)      32 (B)

所以在这里，红-红冲突发生在 31 和 30。左子树的黑色也受到影响。

请问，我必须应用哪些公式/条件步骤来纠正这个着色和黑度问题。

提前致谢。

Answer 1

我已经教授算法和数据结构几年了，我对红/黑树的诚实建议如下:

Know where the rotation rules and color flips come from, but don't memorize them.

实际需要手动跟踪红/黑树旋转或必须对其进行编码的情况极为罕见。在这些情况下，我建议做大多数人所做的事情，即打开 CLRS 的副本。并复制它们包含的任何伪代码。

在我看来，更有值(value)的是首先了解这些规则的来源以及人们如何设法推导出这些规则。虽然这并不经常被教导，但红/黑树的原始规则是通过使用红/黑树与称为 2-3-4 tree 的相关数据结构之间的连接而得出的。 . 2-3-4 树比红/黑树更容易理解，一旦你看到它们之间的联系，你实际上可以重新推导所有旋转和颜色翻转，你需要修复红/黑树-the-the-fly，没有太多困难。我已经放在一起了a set of lecture slides outlining the connection between these data structures and how to use it ，如果您有兴趣，这可能是了解红/黑树工作原理的好方法。