19

我正在学习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

虽然我了解了insertthe2-3 tree和 the LLRB，但我已经花了大约 40 个小时的时间持续了 2 周，但我仍然无法删除 LLRB。

谁能真正向我解释deletion一下LLRB？

4

3 回答 3

13

好的，我要试试这个，也许 SO 的其他好人可以提供帮助。您知道如何将红色节点视为指标的一种方式

  1. 树中有不平衡/新节点的地方，以及
  2. 有多少不平衡。

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

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

在此处输入图像描述

请注意，在添加节点时，红色总是向上传递：在颜色翻转中，两个红色子节点变为黑色（=局部平衡），同时将其父节点着色为红色。本质上，删除的作用是反转这个过程。就像一个新节点是红色的一样，我们也总是想删除一个红色节点。如果节点不是红色的，那么我们想先把它变成红色。这可以通过颜色翻转来完成（顺便说一下，这就是为什么第 3 页代码中的颜色翻转实际上是颜色中性的）。所以如果我们要删除的孩子是黑色的，我们可以通过颜色翻转它的父母让它变成红色。现在保证孩子红了。

下一个要处理的问题是，当我们开始删除时，我们不知道要删除的目标节点是否为红色。一种策略是先找出答案。但是，根据我对您的第一个参考资料的阅读，那里选择的策略是确保删除的节点可以变为红色，方法是在我们向下搜索树时将红色节点“推”到搜索节点前面要删除的节点。这可能会创建不必要的红色节点，fixUp()程序将在备份树的过程中解决这些节点。fixUp()大概保持通常的 LLRBT 不变量：“没有连续的红色节点”和“没有正确的红色节点”。

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

于 2013-03-17T03:30:35.973 回答
1

有一个关于 Sedgwich 实现的有趣评论，特别是哈佛 Comp Sci 教授的删除方法。 被认为有害的左倾红黑树写于 2013 年（您上面引用的 Sedgwich pdf 日期为 2008 年）：

棘手的写作

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

我能找到的包含 2-3 实现的 Sedgwich 代码的最新版本是 2014 年4 月。它在他的算法书籍网站RedBlackBST.java上

于 2014-07-23T01:00:35.577 回答
0

按照下一个策略删除 LLRB 树中不在叶子中的任意节点：

  1. 将 LLRB 树转换为 2-3-4 树（我们不需要转换整棵树，只需转换树的一部分）。
  2. 替换其后继节点（我们要删除的节点）的值。
  3. 删除其继任者。
  4. 435修复树（恢复平衡，请参阅页面上的“算法第 4 版”一书436）。

如果叶子中有一个值，那么我们不需要使用后继树来替换这个值，但是我们仍然需要将当前树转换为 2-3-4 树来删除这个值。

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

例如，打开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。删除后我们需要恢复平衡。我们向上移动通过树并恢复树的平衡（根据规则，请参阅页面上的“算法第 4 版”一书435）436。如果需要删除节点D（页面上的同一棵树54）。您需要相同的转换，需要将节点 D 的值替换为节点 E 的值并删除节点 E（因为它是 D 的继承者）。

于 2020-09-16T10:20:51.000 回答