从二叉搜索树中删除后子节点分配的原因？

Question

在学习BST删除机制的过程中，有一点没有理解。你能解释一下为什么每次调用 Delete(Node* p, int key) 时都有一个赋值 (p->rchild =, p->lchild =) 吗？实际上，我认为 Delete(Node* p, int key) 方法只是保持返回而没有任何变化，所以树不会改变。

当我在寻找解释时，我偶然发现了这句话：

We have to make assignments after deletion else we will end up having duplicate nodes.

如果你同意这个说法，能否请你解释一下？

Node* BST::Delete(Node *p, int key) {
    Node* q;
 
    if (p == nullptr){
        return nullptr;
    }
 
    if (p->lchild == nullptr && p->rchild == nullptr){
        if (p == root){
            root = nullptr;
        }
        delete p;
        return nullptr;
    }
 
    if (key < p->data){
        p->lchild = Delete(p->lchild, key);
    } else if (key > p->data){
        p->rchild = Delete(p->rchild, key);
    } else {
        if (Height(p->lchild) > Height(p->rchild)){
            q = InPre(p->lchild);
            p->data = q->data;
            p->lchild = Delete(p->lchild, q->data);
        } else {
            q = InSucc(p->rchild);
            p->data = q->data;
            p->rchild = Delete(p->rchild, q->data);
        }
    }
    return p;
}

Answer 1

why there is an assignment (p->rchild =, p->lchild =) each time the Delete(Node* p, int key) is called?

如果找到数据，那么目标就是拥有一棵少了一个节点的树。该算法将使用 value-swapping 机制来确保实际将被删除的节点始终是叶节点。一个叶子节点的删除包括两个动作：

从内存中删除；
更新其 parent 以便将引用此已删除节点的 child 指针设置为空指针。

由于算法向右递归到该叶节点，因此无法将空指针设置为其 parent，因为在此阶段没有对 parent 节点可用的引用。为此 caller 应该做一些事情，因为调用者 do 有对 parent.

的引用

所以当递归遍历到叶子节点时，需要传达给调用者这个节点应该被detach。它通过 returning 一个空指针来实现，协议是调用者（其当前节点 p 是 parent）应该将 returned 指针分配给相关的child 指针。这样，删除的节点就真正与树的其余部分分离了。

Actually, I thought that the Delete(Node* p, int key) method just keeps returning without any mutation so the tree doesn't change.

树肯定必须以某种方式更改才能从中删除节点。更改发生在 p->lchild 或 p->rchild

的赋值中

I stumbled into this sentence :

We have to make assignments after deletion else we will end up having duplicate nodes.

这是事实。让我们举一个例子树：

现在让我们看看调用 Delete(root, 3) 会发生什么。 p指向值为7的节点，我们通过递归调用向左走：

p->lchild = Delete(p->lchild, key);

在递归执行上下文中，我们得到一个新的p，它指向值为3的节点。这就是我们要查找的值，所以我们进入外部else堵塞。由于该节点下方子树的高度相等，我们进入内部 else 块。我们在那里分配：

q = InSucc(p->rchild);

q 将引用值为 4 的节点。现在发生了重复。我们将数据从 q 复制到 p。这归结为从树中删除值 3：

p->data = q->data;

但是现在树中的值 4 是原来的两倍。

所以算法下降到（右）child，现在寻求删除该子树中值为 4 的节点：

p->rchild = Delete(p->rchild, q->data);

在这个新的递归调用中，我们再次得到一个新的 p，它现在引用值为 5 的节点。我们向左移动——这个赋值稍后将发挥重要作用：

p->lchild = Delete(p->lchild, key);

这个最终的递归调用有一个新的 p，它引用值为 4 的节点——我们正在寻找的节点。

这一次我们在具有 delete 的 if 块中结束，因为该节点是叶节点。节点被释放，一个空指针被 returned 指向调用者。从这里我们开始回溯树。

所以向上一层，在值为 5 的节点，我们从递归调用（它是一个空指针）中得到 return 值并赋值给它：

p->lchild = Delete(p->lchild, key);

这项重要的任务将从树中分离重复节点（值为 4）。您可以看到，如果不进行此分配，仍然会引用具有重复值的该节点——即使它指向已释放的内存。

这棵树现在处于最终形状：

回溯仍将继续，回到根。也对一些 child 指针进行了赋值，但这些不会改变树，因为在所有这些情况下我们 returned return p;，这是调用者的原始值 child指针。

错误

如评论中所述，代码有一个错误。删除叶节点时，不会验证该节点是否确实具有要删除的值。因此，如果您使用树中不存在的值调用此方法，您将最终删除具有另一个值的叶节点。在上面的示例树中：如果您调用 Delete(root, 10)，将删除值为 9 的节点。

要更正此错误，请移动以下 if 块：

if (p->lchild == nullptr && p->rchild == nullptr){

... 在外部 else 块内，作为那里的第一个语句。

从二叉搜索树中删除后子节点分配的原因？

Reason of child node assignments after deletion from Binary Search Tree?

c++

algorithm

data-structures

tree

binary-search-tree

错误