9

考虑 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)

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

4

4 回答 4

19

删除（通常）不是可交换的。这是一个反例：

    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 也涉及相同的过程。也就是说，您替换节点的值并替换叶节点。所以一般来说，当你删除一个有两个子节点的节点时，唯一的结构变化是你正在删除的节点的值的变化，以及你正在用作替换值的叶节点的删除。

于是问题进一步细化：

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

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

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

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

于 2010-06-07T17:32:02.513 回答
2

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

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

    7
   /
  6
如果我们开始于

    4
   / \
  3 7
     /
    6

相反，我们将首先删除 3（没有后继），然后删除 4（后继 6），产生 

    6
     \
      7

这与删除顺序相反。

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

我没有提供正式的证据，只是列举了一些案例：

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

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

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

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

于 2011-04-06T18:34:42.320 回答
1

我认为有两种同样可行的方法来删除一个节点，当它有 2 个孩子时：
SKIP TO CASE 4...

Case 1: delete 3 (Leaf node)
 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 3
两者都可以工作并且有不同的结果树:) ______________________________________________________________________
算法在这里解释：http://www .mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-delete.html Deleting a node with 2 children nodes: 1) Replace the (to-delete) node with its in-order predecessor or in-order successor 2) Then delete the in-order predecessor or in-order successor

于 2016-10-10T01:02:58.117 回答
0

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

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

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

但下面这句粗体字是不正确的：

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

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

我试着总结一下。

假设：

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

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

  1. B 不是successor(A)，A 也不是successor(B)。

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

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

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

我传球：）

问候。

于 2010-06-11T17:45:09.823 回答