彩铃删除：删除一个子操作

Question

我正在尝试构建一个RBT，尤其是现在我正在尝试实现RBT的delete操作，这个操作相当复杂。我知道第一个想法是用它的后继节点替换我们要删除的节点，如果它有两个非叶子子节点，后继节点最多可能有一个非叶子子节点。然后删除总是减少到删除最多有一个子节点的情况（就像BST的删除操作一样）。你知道吗

在这个问题上，我试着遵循Wiki's article，但是在尝试理解所有的案例之后，我仍然很困惑。在本文中，它们用实节点表示空叶子节点，但是在我的例子中，我只是用None表示空叶子节点，所以这可能也是我困惑的一个原因。你知道吗

所以，从现在开始，假设我们已经用它的后继节点替换了我们的节点，最终如果它最初有两个非叶子子节点的话。你知道吗

我明白了

1. 如果一个节点n是红色的，我们可以简单地删除它而不必冒违反任何属性的风险。

2. 如果一个节点n是黑色的，情况就不同了。你知道吗

   2.1最简单的情况是，唯一可能的非叶子树为红色。在这种情况下，我们只需将n替换为其子级，并将子级的颜色更改为黑色。你知道吗

   2.2。困难的情况是n及其可能的子对象都是黑人。但是很明显而且令人惊讶的是，只有当n的两个子节点都是空叶节点时，这种情况才会发生，在我的例子中，它们都是None。为什么？因为我们知道n最多有一个子节点，如果该子节点不是空叶节点，并且我们知道它是黑色的，则包含它的子树上的黑色高度将大于仅包含空叶节点的子树的黑色高度。

---

如果到目前为止我所有的理由都是正确的，那么我会有一个问题。在Wiki的文章中，有以下功能：

void delete_one_child(struct node *n)
{
    /*
    * Precondition: n has at most one non-null child.
    */

    struct node *child = is_leaf(n->right) ? n->left : n->right;

    replace_node(n, child);

    if (n->color == BLACK) {
        if (child->color == RED)
            child->color = BLACK;
        else
            delete_case1(child);
    }

    free(n);
}

我试图理解这个函数到底要完成什么。因此，它用它的子代替换n，即为了删除n。所以，它检查n的颜色是否是黑色，因为如果是红色，我们只是在讨论上面讨论的第一种简单情况。如果它是黑色的，它的孩子是红色的，那么我们谈论的是2.1的情况。否则，我们将处理所有其他“复杂”的案例。你知道吗

我不明白的是代码下面的注释：

Note: If N is a null leaf and we do not want to represent null leaves as actual node objects, we can modify the algorithm by first calling delete_case1() on its parent (the node that we delete, n in the code above) and deleting it afterwards.

We do this if the parent is black (red is trivial), so it behaves in the same way as a null leaf (and is sometimes called a 'phantom' leaf).

And we can safely delete it at the end as n will remain a leaf after all operations, as shown above.

In addition, the sibling tests in cases 2 and 3 require updating as it is no longer true that the sibling will have children represented as objects.

1）我的理解是我需要遵循这个建议，但我没有完全理解它。在我的例子中，我首先需要调用delete_case1(n)（即在n上，我要删除的节点），并在所有调用“delete\u casesX”的末尾删除该节点，并且仅当n为黑色时才执行此操作，即仅在检查之后

if (n->color == BLACK) {
    // Should I call delete_case1() on n here
    // that is, delete_case1(n) ?

2）我的第二个问题是，我不完全理解为什么n应该像一个空叶一样工作。你知道吗

3）这里的N是什么？n还是它的孩子？你知道吗

4）显然n在所有操作之后都必须保持一片叶子，但为什么呢？（也许这个问题与问题2有关）。你知道吗

---

我已经实现了插入操作，它比删除操作简单得多。我想我也关注了Wiki的文章中的插入，当叶子只是空的或没有的时候，插入也能起作用。你知道吗

你能引导我理解如何通过跟随Wiki的文章来实现这个RBT吗？我知道这是一个非常复杂的问题，有一个更复杂的答案，但任何帮助都是感激的。如果有什么不清楚的，尽管问。你知道吗