有人能清晰地解释一下删除左倾红黑树的过程吗？

Question

我正在学习左倾红黑树，教授是罗伯特·塞奇威克

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

虽然我已经理解了2-3树和LLRB的插入，但我已经花费了两周共40小时，仍无法掌握LLRB的删除操作。

有没有人能真正向我解释一下LLRB的删除？

- Jackson Tale

---

@Thomas，很多关于RB或LLRB的讨论都只涉及插入操作，没有人真正谈论删除操作。 - Jackson Tale

Answer 1

好的，我会尝试这个，并且也许SO上的其他热心网友可以帮忙。你知道，一种认为红色节点是树中

1. 不平衡/新节点的指示器以及
2. 它们的不平衡程度。

这就是为什么所有新节点都是红色的原因。当节点（局部）平衡时，它们会进行颜色翻转，并将红色传递给父节点，现在父节点相对于其兄弟可能看起来不平衡。

作为一个例子，考虑从大到小添加节点的情况。您从节点Z开始，它是根节点并且为黑色。您添加一个名为Y的节点，它是红色的，并且是Z的左子节点。您添加了一个红X作为Z的子代，但是现在您有两个连续的红色节点，所以您向右旋转，重新着色，您拥有一个平衡的、全黑的（没有不平衡 /“新节点”！）以Y为根的树 [第一张图]。现在您按顺序添加W和V。起初它们都是红色的[第二张图]，但立即V / X / W向右旋转并翻转颜色，以便只有X是红色的[第三张图]。这很重要：X为红色表示Y的左子树不平衡了2个节点，换句话说，左子树中有两个新节点。因此，红色链接的高度是新的、潜在不平衡节点数的计数：红色子树中有2^height个新节点。

请注意，在添加节点时，红色总是向上传递的：在颜色翻转中，两个红色子节点变为黑色（=本地平衡），同时将其父节点染成红色。基本上，删除所做的就是反转这个过程。就像新节点是红色的一样，我们也总是想要删除红色节点。如果该节点不是红色，则希望首先将其变为红色。这可以通过颜色翻转来实现（顺便说一句，这就是第3页代码中颜色翻转实际上是颜色中性的原因）。因此，如果我们要删除的子节点是黑色的，则可以通过颜色翻转其父节点将其变为红色。现在保证该子节点为红色。

下一个要处理的问题是，当我们开始删除时，我们不知道要删除的目标节点是否为红色。一种策略是首先找出。但是，根据我对您第一个参考文献的阅读，选择在那里的策略是通过“推”一个红色节点到搜索节点前面，以确保删除的节点可以变为红色，而我们在向下搜索树寻找要删除的节点时。这可能会创建不必要的红色节点， fixUp()过程将在返回树时解决这些节点。 fixUp()大概维护着常规的LLRBT不变式：“没有连续的红色节点”和“没有右红色节点”。

不确定这是否有所帮助，或者我们需要更详细地检查代码。

- angelatlarge

---

非常有用。就像一个新节点是红色的一样，我们总是想要删除一个红色的节点。如果节点不是红色的，则我们希望先将其变为红色。这真的很鼓舞人心。 - Jackson Tale

我觉得你的旋转有问题。如果h.left和h.left.left都是红色的，我们在顶部节点上执行rotateToRight操作，在你展示的情况下，结果应该是V/W/X，然后W在颜色翻转之后变成红色。{实际上，你的子树VXW不符合二叉搜索树的条件} - hakunami

我也卡住了 - 我似乎从将红链接视为以黑链接开头的链的一部分中获得了一些收益。 因此，具有红色左侧的黑色链接表示长度为2的链 - 2个节点和3个链接，或3个节点。 具有红色左侧且其红色也在左侧的黑色链接表示长度为3的链 - 3个节点和4个链接，或4个节点。请注意，在向下移动链以进行deleteMin时测试的条件是当前头的后继者既不是红色的，也不是它的后继者是红色的 - 换句话说，它既不是当前头的3个节点之一，也不是它的开始。 - Alex Leibowitz

此外，我的许多困难都是因为我混淆了表示和被表示的内容：当递归地沿着左侧脊柱向下移动时，我们关注LLRB树的结构，但在评估递归中每个点要执行的操作时，我们的测试是基于该树所代表的内容（文本中描述的算法，即以2-3-4树为基础）。 - Alex Leibowitz

Answer 2

哈佛计算机科学教授对Sedgwich实现及其删除方法发表了有趣的评论。左倾红黑树被认为是有害的于2013年撰写（您引用的Sedgwich pdf日期为2008年）：

棘手的写作

Sedgewick的论文很棘手。截至2013年，插入部分将2-3-4树作为默认值，并将2-3树描述为一种变体。然而，删除实现仅适用于2-3树。如果您实现了插入的默认变体和唯一的删除变体，则您的树将无法工作。该文本未突出显示从2-3-4到2-3的转换：不友好。

我能找到的 Sedgwich 代码最新版本，其中包含一个 2-3 实现，日期为2014年4月。它在他的算法书网站上RedBlackBST.java。

- Kurt Krueckeberg

---

他的实现有问题，仅此而已。请检查deleteMin方法。 - Pavel

只是好奇，你是否真的看过科勒链接的Sedgewick的论文？我不明白一个大标题和周围反复说2-3的文字怎么就不能“突出”删除代码是用于2-3树的。Sedgewick甚至评论了修改2-3-4代码的问题。我不知道Kohler从哪里得到的2-3-4是主要树而2-3是变体的想法。Sedgewick从一开始就清楚地介绍了两种类型，没有一种被描述为“默认”。Kohler似乎对他的一些评论有意见。 - C S

Answer 3

按照下列策略删除不在叶节点中的LLRB树上的任意节点：

1. 将LLRB树转换为2-3-4树（我们不需要转换整个树，只需转换部分树）。
2. 用其继承者替换要删除的节点的值。
3. 删除其继承者。
4. 修复树（恢复平衡，请参见书籍“算法第四版”第435页和第436页）。

如果是叶节点中的值，则无需使用继承者替换该值，但我们仍然需要将当前树转换为2-3-4树以删除该值。

这个演示文稿的页面20https://algs4.cs.princeton.edu/lectures/keynote/33BalancedSearchTrees.pdf和书籍《算法 第四版》中的页面437是关键。它们展示了LLRB树如何转化为2-3树。在书籍《算法 第四版》的页面442https://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA442中，有一种树形变换算法。

例如，打开演示文稿的页面 54 https://www.cs.princeton.edu/~rs/talks/LLRB/08Dagstuhl/RedBlack.pdf。节点 H 有子节点 D 和 L。根据页面 442 上的算法，我们将这三个节点转换为一个 2-3-4 树的 4 节点。然后节点 D 的子节点 B 和 F 也被转换为一个 2-3-4 树的节点。然后节点 B 的子节点 A 和 C 也被转换为一个 2-3-4 树的节点。最后，我们需要删除节点 A。删除后需要恢复平衡。我们沿着树向上移动，并根据规则恢复树的平衡（参见书籍《算法 第四版》的页面 435、436）。如果你需要删除节点 D（页面 54 上的同一棵树），你需要进行相同的转换，并将节点 D 的值替换为节点 E 的值，并删除节点 E（因为它是节点 D 的后继节点）。

- Volodymyr