红黑树轮换后重新着色时遵循的规则

Question

我只是RB Tree的新手.我刚刚在旋转后对树进行重新着色时被绞死了.

让我们考虑以下情况: -

插入顺序: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

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

知道旋转规则和颜色翻转的来源,但不要记住它们.

实际上需要手动追踪红/黑树旋转或者必须编码它们是非常罕见的.在这些情况下,我建议做大多数人做的事情,即打开CLRS的副本并复制他们包含的任何伪代码.

在我看来,更有价值的是要了解这些规则从何而来,以及如何设法推导出这些规则.虽然这并不经常教,但红/黑树的原始规则是通过使用红/黑树和称为2-3-4树的相关数据结构之间的连接得出的.2-3-4树比红/黑树更容易理解,一旦你看到它们之间的连接,你实际上可以重新启动所有的旋转和颜色翻转,你需要修复一个红色/黑色的树飞行,没有太多困难.我已经整理了一组演讲幻灯片,概述了这些数据结构与如何使用它们之间的联系,如果您感兴趣,这可能是理解红/黑树如何工作的好方法.