algorithm - 从全黑红黑树中删除节点

Question

我正在阅读 Wikipedia explanation of red black tree removal process .

有一件简单的事情我无法理解。

例子:我有一个全黑的 RBTree

                     3(B)
                 /          \
                /            \
               1(B)          5(B)
             /     \        /    \
            /       \      /      \
           0(B)     2(B) 4(B)     6(B)

维基百科指出，如果您要删除一个有 2 个叶子节点的节点，并且兄弟节点也是一个有 2 个叶节点的节点，那么我们可以简单地删除该节点并重新着色父节点和兄弟节点。

假设在上面的树中我想删除 0。那么重新着色 1 或 2 没有任何帮助，因为无论你做什么，两个子树(1 边)和 5 边最终具有不同的黑色高度。

我错过了什么？

我发现维基百科对insert的解释很好，但是delete的解释很困惑。

Answer 1

删除树中的节点“0”实际上是最复杂的情​​况。让我们关注description from wikipedia一步一步:

We use the label M to denote the node to be deleted; C will denote a selected child of M, which we will also call "its child". If M does have a non-leaf child, call that its child, C; otherwise, choose either leaf as its child, C.

因此，在这种情况下，M 是您的节点“0”，它将被删除，C 是它的任何 NIL 子节点(叶子，它们始终为 NIL)。提醒一下，您的原始树 - 遵循您美丽的 ascii 艺术是:

                     3(B)
                 /          \
                /            \
               1(B)          5(B)
             /     \        /    \
            /       \      /      \
           0(B)     2(B) 4(B)     6(B)

所以 M 是“0”，注意这里没有画 C(NIL 叶子)。维基百科如下:

The complex case is when both M and C are black (this is our case).... In the diagrams below, we will also use P for N's new parent (M's old parent), SL for S's left child, and SR for S's right child.

因此，P为“1”，S为“2”，所有节点均为黑色。然后你按照案例描述。您跳过案例 1，因为“0”不是根。您跳过案例 2，因为“2”不是红色。情况 3 匹配:

Case 3: P, S, and S's children are black. In this case, we simply repaint S red. The result is that all paths passing through S, which are precisely those paths not passing through N, have one less black node. Because deleting N's original parent made all paths passing through N have one less black node, this evens things up. However, all paths through P now have one fewer black node than paths that do not pass through P, so property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is still violated. To correct this, we perform the rebalancing procedure on P, starting at case 1.

所以此时，您删除“0”，并重新将 S = “2”涂成红色:

                     3(B)
                 /          \
                /            \
               1(B)          5(B)
                   \        /    \
                    \      /      \
                    2(R) 4(B)     6(B)

然后，根据描述，您转到案例 1，但这次将其父节点 P(=“1”)替换为 N。但是 N =“1”不是根节点，因此您跳转到案例 2。 S = "5"不是红色，所以我们再次跳转到案例 3。在这里，我们将 S = "5"重新涂成红色:

                     3(B)
                 /          \
                /            \
               1(B)          5(R)
                   \        /    \
                    \      /      \
                    2(R) 4(B)     6(B)

然后我们必须再次跳到案例 1，这次将 P = "3"替换为 N。 N = "3"我们看到这是一个根，所以我们完成了!树是平衡的!