algorithm - 为什么此代码中需要这一行才能从 BST 中删除？

Question

我正在尝试了解有关二叉树的更多信息，并且遇到了一种关于如何找到后继节点的方法(当尝试删除节点时)，但我很难理解其中的一部分。这是代码。

    private Node getSuccessor(Node delNode){
    Node successorParent = delNode;
    Node successor = delNode;
    Node current = delNode.rightChild;

    while(current != null){
        successorParent = successor;
        successor = current;
        current = current.leftChild;
    } // end of if

    if(successor != delNode.rightChild){
        successorParent.leftChild = successor.rightChild;
        successor.rightChild = delNode.rightChild;
    }
    return successor;


}

我完全理解 while 循环以及其中发生的事情。我不明白的是 if 语句，特别是......

successor.rightChild = delNode.rightChild;

为什么要把delNode的右 child 赋值给后继节点的右 child ？为什么需要 if 语句？

Answer 1

此代码试图解释两种情况。第一个是删除节点 X，其后继 Y 是其直接右子节点:

X
 \
  Y
   \
    Z

在这种情况下，我们最终将用 Y 替换 X，因此该方法可以只返回 Y 并说“这是现在替换 X 的节点。”

另一方面，假设X的后继Y在其右子树的子树中:

X
 \
  A
 / \
Y   C
 \
  B

在这种情况下，我们不能盲目地将 X 替换为 Y，因为这样做会丢失节点 A 和子树 C 中的所有内容。因此在我们说“嘿树 - 将节点 X 替换为节点 Y”之前，我们重新排列树中的节点，以便它们看起来像这样:

X
 \
  Y
   \
    A
   / \
  B   C

现在，当我们用 Y 替换 X 时，我们没有丢失树中的任何其他节点。

顺便说一句，这里的形状是通过交换 X 和 Y，然后删除 X(在 Y 曾经所在的位置)而形成的，方法是让 Y 的前父树将 Y 的前右子树作为其左子树。追踪这些线，看看您是否能看出这是如何工作的。