二叉搜索树的删除过程

Question

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

问题是：这个过程可交换吗？也就是说，先删除 x 再删除 y 与先删除 y 再删除 x 的结果相同吗？

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

编辑：

也许我必须更清楚。

考虑一下移植（节点x，节点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 个子节点的节点。我的解决方案适用于一般情况。如果/当我能找到反例时，我会更新它。

另一更新

我没有具体的证据，但我会冒险猜测：

在一般情况下，根据您是否有两个孩子、一个孩子或没有孩子，您会以不同的方式处理删除。在我提供的反例中，我首先删除一个具有两个子节点的节点，然后删除一个具有一个子节点的节点。之后，我删除一个没有子节点的节点，然后删除另一个有一个子节点的节点。

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

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

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

当你删除一个节点（假设是A）时，你会遍历右子树来找到最小元素。该节点将是叶节点，并且永远不能等于 B（因为 B 有两个子节点，不能是叶节点）。然后，您可以将 A 的值替换为该叶节点的值。这意味着树的唯一结构变化是用叶节点的值替换 A 的值，以及叶节点的丢失。

B 也涉及相同的过程。即，替换节点的值并替换叶节点。因此，一般来说，当您删除具有两个子节点的节点时，唯一的结构变化是您要删除的节点的值发生变化，以及删除您用作替换的叶节点的值 。

所以问题进一步细化：

你能保证无论删除顺序如何（当你总是删除有两个子节点的节点时），你总是会得到相同的替换节点吗？

答案（我认为）是肯定的。为什么？以下是一些观察结果：

• 假设您首先删除后代节点，然后删除祖先节点。删除后代节点时修改的子树不在祖先节点右子节点的左子树中。这意味着该子树不受影响。这也意味着无论删除的顺序如何，都会修改两个不同的子树，因此该操作是可交换的。
• 同样，假设您首先删除后代节点，然后删除祖先节点。删除后代节点时修改的子树位于祖先节点右子节点的左子树中。但即使在这里，也没有重叠。原因是当您首先删除后代节点时，您会查看后代节点的右子节点的左子树。然后，当您删除祖先节点时，您将永远不会沿着该子树走下去，因为在您进入祖先节点的右子节点的左侧后，您总是向左走子树。同样，无论您首先删除什么，您都会修改不同的子树，因此顺序似乎并不重要。
• 另一种情况是，如果先删除祖先节点，然后发现最小节点是后代节点的子节点。这意味着后代节点最终将有一个子节点，并且删除一个子节点是微不足道的。现在考虑这种情况，在这种情况下，您首先删除了后代节点。然后，您将用其右子节点替换后代节点的值，然后删除右子节点。然后，当您删除祖先节点时，您最终会找到相同最小节点（旧删除节点的左子节点，也是被替换节点的左子节点）。无论哪种方式，您最终都会得到相同的结构。

这不是一个严格的证明；这些只是我的一些观察。无论如何，请随意戳洞！

Answer 2

在我看来，Vivin 的答案中显示的反例是非交换性的唯一情况，并且确实通过只能删除具有两个子节点的限制来消除它。

但如果我们放弃维文的前提之一，即我们应该尽可能少地遍历右子树以找到任何可接受的后继者，那么它也可以被消除。相反，如果我们总是将右子树中的最小节点提升为后继，无论它的位置有多远，那么即使我们放宽删除少于两个子节点的限制，Vivin 的结果

    7
   /
  6

is never reached if we start at

    4
   / \
  3   7
     /
    6

相反，我们首先删除 3（没有后继），然后删除 4（有 6 作为后继），得到

    6
     \
      7

这与删除顺序相反是一样的。

那么删除将是可交换的，并且我认为它总是可交换的，给定我所命名的前提（后继者始终是已删除节点的右子树中的最小节点）。

我没有正式的证明可以提供，只是列举一些情况：

1. 如果要删除的两个节点位于不同的子树中，则删除一个节点不会影响另一个节点。只有当它们处于同一路径时，删除的顺序才有可能影响结果。

   因此，只有当祖先节点及其后代节点之一都被删除时，才会对交换性产生任何影响。那么，它们的垂直关系如何影响交换性呢？

2. 后代位于祖先的左子树中。这种情况不会影响交换性，因为后继者来自右子树，根本不会影响左子树。

3. 祖先的右子树中的后代。如果祖先的后继者始终是右子树中最小的节点，则删除顺序不能改变后继者的选择，无论删除哪个后代在祖先之前或之后。即使祖先的后继者结果是也将被删除的后代节点，该后代也将被替换为它的下一个最大节点，并且该后代不能有自己的左子树剩余需要处理。因此，删除祖先和任何右子树后代将始终是可交换的。

Answer 3

我认为当节点有 2 个子节点时，有两种同样可行的方法来删除它：
跳到情况 4...

情况1：删除3（叶节点）

 2         3

 / \    -->  / \

1  3       1

情况 2：删除 2（左子节点）

 2         3

 / \    -->  / \

1  3       1

情况 3：删除 2（右子节点）

 2         2

 / \    -->  / \

1  3         3

________________________________________________________________________________

情况4：删除2个（左右子节点）

 2        2         3

 / \    --> / \    或 / \      

1  3     1            &n公共服务提供商;3

两者都有效并且有不同的结果树:)
_____________________________________________________________

正如此处解释的算法：http： //www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-delete.html
<代码>
删除具有 2 个子节点的节点：
1) 将（待删除）节点替换为其有序前驱或有序后继
2）然后删除中序前驱或中序后继

Answer 4

我在这里回应 Vivin 的第二次更新。

我认为这是对问题的一个很好的改写：

当你是时，删除是否可交换
考虑删除两个节点
来自二叉搜索树，其中有
祖先与后代的关系
彼此（这意味着他们
位于同一子树中）？

但下面这句大胆的话并不正确：

当你删除一个节点时（假设是A），
你遍历右子树到
找到最小元素。 该节点
将是一个叶节点并且永远不能等于B

因为A的右子树中的最小元素可以有一个右子节点。所以，它不是一片叶子。
我们将 A 右子树中的最小元素称为 successor(A)。
现在，B 确实不能成为successor(A)，但它可以位于其右子树中。所以，这是一团糟。

我试着总结一下。

假设：

1. A和B各有两个孩子。
2. A和B在同一子树中。

其他内容我们可以从假设中推断出：

1. B不是后继者(A)，A也不是后继者(B)。

现在，鉴于此，我认为有 4 种不同的情况（像往常一样，让 A 成为 B 的祖先）：

1. B 位于 A 的左子树中
2. B 是 successor(A)
3. successor(A) 是 B B 的祖先，
4. 和 successor(A) 没有任何关系。 （它们位于不同的A的子树中）

我认为（但当然我无法证明）情况1、2和4并不重要。
因此，只有在successor(A)是B的祖先的情况下，删除过程才不能是可交换的。或者可以吗？

我传球:)

问候。