algorithm - 二叉搜索树的删除过程

Question

当要删除的节点有两个子节点时，请考虑BST上的删除过程。假设我总是用在其右子树中拥有最小键的节点替换它。

问题是:此过程是可交换的吗？也就是说，先删除x然后删除y的结果与先删除y然后删除x的结果相同。

我认为答案是否定的，但我找不到反例，也找不到任何有效的理由。

编辑:

也许我必须变得更加清楚。

考虑transplant(node x, node y)过程:它将x替换为y(及其子树)。
因此，如果我要删除具有两个子节点的节点(例如x)，则将其替换为在其右侧子树中拥有最小键的节点:

y = minimum(x.right)
transplant(y, y.right) // extracts the minimum (it doesn't have left child)
y.right = x.right
y.left = x.left
transplant(x,y)

问题是如何证明上述程序不是可交换的。

Answer 1

删除(通常)不是可交换的。这是一个反例:

    4
   / \
  3   7
     /
    6

如果我们先删除4再删除3，该怎么办？

当我们删除4时，我们得到6作为新的根:

   6
  / \
 3   7

删除3不会更改树，但可以给我们以下内容:

  6
   \
    7

如果我们先删除3然后再删除4，该怎么办？

当我们删除3时，树不会改变:

 4
  \
   7
  /
 6

但是，当我们现在删除4时，新的根将变为7:

  7
 /
6

生成的两个树不相同，因此删除不是可交换的。

更新

当您始终删除具有2个子节点的节点时，我没有读过限制。我的解决方案适用于一般情况。如果/当我可以找到反例时，我将对其进行更新。

另一个更新

我没有具体的证据，但是我要冒险猜一下:

在一般情况下，根据您有两个 child ，一个 child 或没有 child ，对删除操作的处理方式有所不同。在我提供的反例中，我首先删除一个有两个 child 的节点，然后删除一个有一个 child 的节点。之后，我删除一个没有子节点的节点，然后再删除一个有子节点的节点。

在仅删除具有两个子节点的节点的特殊情况下，您要考虑两个节点都在同一子树中的情况(因为它们是否在不同的子树中无关紧要；您可以确保整体结构不会根据删除顺序而改变)。您真正需要证明的是，每个节点有两个子节点的同一子树中节点的删除顺序是否重要。

考虑两个节点A和B，其中A是B的祖先。然后您可以进一步将问题简化为:

当您考虑从二叉搜索树中删除两个具有祖先后代关系的节点时，删除是否是可交换的(这意味着它们位于同一子树中)？

删除节点(假设为A)时，遍历右侧的子树以找到最小的元素。该节点将是叶节点，并且永远不能等于B(因为B有两个子节点，并且不能是叶节点)。然后，您将A的值替换为此叶节点的值。这意味着对树的唯一结构更改是用叶节点的值替换A的值，并损失叶节点。

B涉及相同的过程。也就是说，您替换节点的值并替换叶节点。因此，通常，当删除具有两个子节点的节点时，唯一的结构更改是要删除的节点的值更改，以及删除要用作替换值的叶子节点的值。

因此，这个问题得到了进一步完善:

您能否保证无论删除顺序如何(当您始终删除具有两个子节点的节点时)都将始终获得相同的替换节点？

答案(我认为)是。为什么？以下是一些观察结果:

假设您先删除后代节点，然后再删除祖先节点。删除后代节点时修改的子树不在祖先节点的右子节点的左子树中。这意味着该子树保持不受影响。这也意味着无论删除顺序如何，两个不同的子树都被修改，因此操作是可交换的。

再次，假设您先删除后代节点，然后再删除祖先节点。删除后代节点时修改的子树位于祖先节点的右子节点的左子树中。但是即使在这里，也没有重叠。原因是，当您首先删除后代节点时，您会查看后代节点的右子节点的左子树。然后，当您删除祖先节点时，您将永远不会掉落该子树，因为在您输入祖先节点的右子节点的左子树后，您将始终向左走。同样，无论您首先删除什么，都在修改不同的子树，因此显示顺序无关紧要。

另一种情况是，如果您首先删除祖先节点，并且发现最小节点是后代节点的子节点。这意味着后代节点将以一个子代结束，删除一个子代是微不足道的。现在考虑在这种情况下首先删除后代节点的情况。然后，将后代节点的值替换为其正确的子代，然后删除正确的子代。然后，当您删除祖先节点时，最终会找到相同的最小节点(旧的已删除节点的左子节点，也就是被替换节点的左子节点)。无论哪种方式，您最终都具有相同的结构。

这不是严格的证明；这些只是我所做的一些观察。一定要戳孔!