任何人都可以清楚地解释删除左倾 - 红 - 黑树吗？

Question

我学习Left-Lean-Red-Black tree,从Prof.Robert Sedgewick

http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

虽然我已经理解了insert这个2-3 tree和那个LLRB,但是我花了大约40个小时现在已经有2个星期了,我仍然无法删除LLRB.

谁能真正解释deletion的LLRB给我吗？

Answer 1

好的,我打算尝试这个,也许SO的其他优秀人才可以提供帮助.你知道如何将红色节点的一种思维方式作为指标

1. 树中存在不平衡/新节点的地方,和
2. 有多少不平衡.

这就是所有新节点都是红色的原因.当节点(本地)平衡时,它们经历颜色翻转,并且红色被传递到父节点,并且现在父节点相对于其兄弟节点可能看起来不平衡.

作为示例,请考虑将节点从较大的节点添加到较小节点的情况.你从节点Z开始,它现在是root并且是黑色的.您添加节点Y,它是红色并且是Z的左子节点.您将红色X添加为Z的子节点,但现在您有两个连续的红色,因此您向右旋转,重新着色,并且您具有平衡,全黑(没有不平衡/"新节点"!)树根植于Y [第一次绘图].现在按顺序添加W和V. 首先它们都是红色[第二个绘图],但是立即向右旋转V/X/W,并且颜色翻转,因此只有X是红色[第三个绘图].这很重要:X为红色表示Y的左子树不平衡2个节点,换句话说,左子树中有两个新节点.因此,红色链接的高度是新的,可能不平衡的节点的数量:红色子树中有2 ^个新节点的高度.

请注意,添加节点时,红色总是向上传递:在彩色翻转中,两个红色儿童变为黑色(=局部平衡),同时将父红色着色.基本上删除的作用是逆转这个过程.就像新节点是红色一样,我们也总是想要删除一个红色节点.如果节点不是红色,那么我们首先要将其设为红色.这可以通过彩色翻转来完成(顺便说一句,这就是为什么第3页的代码中的颜色翻转实际上是颜色中性的原因).因此,如果我们要删除的孩子是黑色的,我们可以通过颜色翻转其父级来使其变红.现在孩子保证是红色的.

下一个要处理的问题是,当我们开始删除时,我们不知道要删除的目标节点是否为红色.一种策略是首先找出答案.但是,根据我对你的第一个参考文献的阅读,那里选择的策略是确保删除的节点可以变为红色,通过在搜索节点前面"推"一个红色节点,因为我们正在树上搜索要删除的节点.这可能会创建不必要的红色节点,fixUp()程序将在返回树的路上解析.fixUp()可能维持通常的LLRBT不变量:"没有连续的红色节点"和"没有正确的红色节点".

不确定这是否有帮助,或者我们是否需要进行更详细的代码检查.