二进制搜索树的删除过程

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怎么办？

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

   6
  / \
 3   7

删除3不会改变树,但是给我们这个:

  6
   \
    7

如果我们删除3然后删除4怎么办？

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

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

  7
 /
6

产生的两棵树不一样,因此删除不是可交换的.

UPDATE

当你总是删除一个有2个孩子的节点时,我没有读到这个限制.我的解决方案是针对一般情况的.如果/当我能找到一个反例时,我会更新它.

另一个更新

我没有具体的证据,但我会冒险猜测:

在一般情况下,根据您是否有两个孩子,一个孩子或没有孩子,您可以不同地处理删除.在我提供的反例中,我首先删除一个包含两个子节点的节点,然后删除一个包含一个子节点的节点.之后,我删除一个没有子节点的节点,然后删除另一个有一个子节点的节点.

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

考虑两个节点A和B,其中A是B的祖先.然后,您可以进一步细化问题:

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

当您删除节点(假设为A)时,您将遍历右侧子树以查找最小元素.此节点将是叶节点,并且永远不能等于B(因为B有两个子节点,不能是叶节点).然后,您将使用此叶节点的值替换A的值.这意味着树的唯一结构变化是用叶节点的值替换A的值,以及叶节点的丢失.

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

所以问题进一步完善:

您是否可以保证无论删除顺序如何(当您总是删除有两个孩子的节点时),您将始终获得相同的替换节点？

答案(我认为)是肯定的.为什么？以下是一些观察:

假设您先删除后代节点,然后再删除祖先节点.删除后代节点时修改的子树不在祖先节点的右子节点的左子树中.这意味着此子树不受影响.这也意味着无论删除的顺序如何,都修改了两个不同的子树,因此操作是可交换的.
再说一次,假设您先删除后代节点,然后再删除祖先节点.当您删除其后继节点被修改的子树是在父节点的右孩子的左子树.但即使在这里,也没有重叠.原因是当您首先删除后代节点时,您会查看后代节点的右子节点的左子树.当您删除祖先节点时,您将永远不会沿着该子树向下,因为在您进入祖先节点的右子左侧子树后,您将始终向左移动.所以,再次,无论你删除什么,你首先修改不同的子树,所以看起来顺序无关紧要.
另一种情况是,如果首先删除祖先节点,并且发现最小节点是子节点的子节点.这意味着后代节点将以一个子节点结束,删除一个子节点是微不足道的.现在考虑在这种情况下,您首先删除了后代节点的情况.然后,您将使用其右子项替换子节点的值,然后删除正确的子项.然后,当您删除祖先节点时,您最终会找到相同的最小节点(旧的已删除节点的左子节点,也是替换节点的左子节点).无论哪种方式,你最终都得到相同的结构.

这不是一个严格的证据; 这些只是我所做的一些观察.无论如何,随意戳洞!