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 边最终都会有不同的黑色高度。

我错过了什么？

我发现维基百科对插入有很好的解释，但对删除的解释却很困惑。

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”，我们看到这是一个根，所以我们完成了!树是平衡的!