algorithm - 谁能解释清楚Left-Lean-Red-Black树的删除？

Question

我正在学习 Left-Lean-Red-Black 树，来自 Prof.Robert Sedgewick

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

虽然我开始理解2-3 树 的insert 和LLRB，但我现在总共花了大约 40 个小时2 周了，我仍然无法删除 LLRB。

谁能真正向我解释 LLRB 的删除？

Answer 1

好的，我要试试这个，也许 SO 的其他好人可以帮忙。你知道红色节点的一种思考方式是作为

的指标

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

这就是为什么所有新节点都是红色的。当节点(局部)平衡时，它们会进行颜色翻转，红色会传递给父节点，现在父节点可能看起来与其兄弟节点不平衡。

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

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

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

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