对于二叉搜索树删除程序 [英] Deletion procedure for a Binary Search Tree

问题描述

考虑在BST删除过程中，当删除节点有两个孩子。比方说，我总是将其与节点持有其右子树的最小密钥进行更换。

Consider the deletion procedure on a BST, when the node to delete has two children. Let's say i always replace it with the node holding the minimum key in its right subtree.

现在的问题是：这是程序交换？也就是说，删除x和然后y具有相同的结果不是删除第一y和则x？

The question is: is this procedure commutative? That is, deleting x and then y has the same result than deleting first y and then x?

我想答案是否定的，但我不能找到一个反例，也没有找出任何合法的理由。

I think the answer is no, but i can't find a counterexample, nor figure out any valid reasoning.

编辑：

也许我得再清楚不过了。

Maybe i've got to be clearer.

考虑移植（节点X，节点Y）程序：它代替x与Y（和它的子树）。 所以，如果我想删除一个节点（例如x），其中有两个孩子我与节点持有其右子树最小键替换它：

Consider the transplant(node x, node y) procedure: it replace x with y (and its subtree). So, if i want to delete a node (say x) which has two children i replace it with the node holding the minimum key in its right subtree:

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)

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

The question was how to prove the procedure above is not commutative.

推荐答案

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

Deletion (in general) is not commutative. Here is a counterexample:

    4
   / \
  3   7
     /
    6

如果我们删除4，然后3？

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

When we delete 4, we get 6 as the new root:

   6
  / \
 3   7

删除3不会变树，但给了我们这样的：

Deleting 3 doesn't change the tree, but gives us this:

  6
   \
    7

如果我们删除3，然后4？

当我们删除3的树没有改变：

When we delete 3 the tree doesn't change:

 4
  \
   7
  /
 6

然而，当我们现在可以删除4，新根变成7：

However, when we now delete 4, the new root becomes 7:

  7
 /
6

两个所得树是不一样的，因此删除是不可交换的。

The two resulting trees are not the same, therefore deletion is not commutative.

更新

我没看过的限制，这是当你总是删除一个节点与2名儿童。我的解决方案是对于一般情况。我会更新，如果/当我能找到一个反例。

I didn't read the restriction that this is when you always delete a node with 2 children. My solution is for the general case. I'll update it if/when I can find a counter-example.

另一个更新

我没有具体证据，但我要大胆地猜测：

I don't have concrete proof, but I'm going to hazard a guess:

在一般情况下，不同的处理的基础上是否有两个孩子，一个孩子，或没有孩子缺失。在反例我提供的，我首先删除有两个孩子，然后有一个孩子一个节点一个节点。在那之后，我删除了，没有孩子，然后用一个孩子的另一个节点一个节点。

In the general case, you handle deletions differently based on whether you have two children, one child, or no children. In the counter-example I provided, I first delete a node with two children and then a node with one child. After that, I delete a node with no children and then another node with one child.

在只删除节点有两个孩子的特殊情况下，要考虑在两个节点都在同一子树（因为如果他们在不同的子树是不会有问题的情况下，你可以确保基于缺失的顺序上的整体结构也不会改变）。你真正需要证明是删除节点在同一子树，其中每个节点有两个孩子，事情的顺序是否。

In the special case of only deleting nodes with two children, you want to consider the case where both nodes are in the same sub-tree (since it wouldn't matter if they are in different sub-trees; you can be sure that the overall structure won't change based on the order of deletion). What you really need to prove is whether the order of deletion of nodes in the same sub-tree, where each node has two children, matters.

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

Consider two nodes A and B where A is an ancestor of B. Then you can further refine the question to be:

时，当你正在考虑从二叉搜索树，有一个祖先，后裔的相互关系（这将意味着他们在同一个子树）？

Is deletion commutative when you are considering the deletion of two nodes from a Binary Search Tree which have a ancestor-descendant relationship to each other (this would imply that they are in the same sub-tree)?

当你删除一个节点（假设A），你遍历右子树查找最小元素。此节点将是叶节点，从来没有等于B（因为B有两个孩子，并且不能是叶节点）。然后，将与该叶节点的值替换A的值。这意味着，只有结构变化到树是替换A的值与所述叶节点的值，以及所述叶节点的损失。

When you delete a node (let's say A), you traverse the right sub-tree to find the minimum element. This node will be a leaf node and can never be equal to B (because B has two children and cannot be a leaf node). You would then replace the value of A with the value of this leaf-node. What this means is that the only structural change to the tree is the replacement of A's value with the value of the leaf-node, and the loss of the leaf-node.

相同的过程涉及的B.即，在更换节点的值，并更换一个叶节点。因此，在一般情况下，当你删除一个节点有两个孩子，的唯一的结构性变化是要删除的节点的值的变化，并删除叶节点的谁是你正在使用的值作为替代的

The same process is involved for B. That is, you replace the value of the node and replace a leaf-node. So in general, when you delete a node with two children, the only structural change is the change in value of the node you are deleting, and the deletion of the leaf node who's value you are using as replacement.

所以，问题是进一步细化：

So the question is further refined:

你能保证你总是会得到缺失的顺序（当你总是删除有两个孩子的节点）？

Can you guarantee that you will always get the same replacement node regardless of the order of deletion (when you are always deleting a node with two children)?

答案（我认为）是肯定的。为什么？这里有几点看法：

The answer (I think) is yes. Why? Here are a few observations:

• 比方说，你删除的后代节点，第一和祖先节点第二。当你删除的后代节点已修改子树的没有的在父节点的右孩子的左子树。这意味着该子树不受影响。什么，这也意味着是无论缺失的顺序的，两个不同的子树被修改，因此该操作是可交换的。
• 同样，假设您删除第一个后代节点和祖先节点第二。当你删除的后代节点被修改的子树的是的在父节点的右孩子的左子树。但即使在这里，不存在重叠。当你第一次删除的后代节点，你看看后代节点的右键的孩子的左子树的原因。当你再删除祖先节点，你会的永远的走这子树，因为你的总是的是想向左输入的祖先节点的右孩子的左后子树。如此反复，无论你先删除您要修改不同的子树，所以会出现为了什么并不重要的。
• 在另一种情况是，如果你先删除祖先节点，你会发现，最低点是后代的子节点。这意味着后代节点将结束与一个孩子，并删除一个孩子实在是微不足道。现在考虑在这种情况下，首先删除的后裔节点的情况。然后，你将取代后代节点的值与它的右子，然后删除右孩子。然后，当你删除的祖先节点，你最终找到的一样的最低点（旧删除节点的左子，这也是更换节点的左子）。无论哪种方式，你最终具有相同的结构。

• Let's say you delete the descendant node first and the ancestor node second. The sub-tree that was modified when you deleted the descendant node is not in the left sub-tree of the ancestor node's right child. This means that this sub-tree remains unaffected. What this also means is regardless of the order of deletion, two different sub-trees are modified and therefore the operation is commutative.
• Again, let's say you delete the descendant node first and the ancestor node second. The sub-tree that was modified when you deleted the descendant node is in the left sub-tree of the ancestor node's right child. But even here, there is no overlap. The reason is when you delete the descendant node first, you look at the left sub-tree of the descendant node's right child. When you then delete the ancestor node, you will never go down that sub-tree since you will always be going towards the left after you enter the ancestor node's right-child's left sub-tree. So again, regardless of what you delete first you are modifying different sub-trees and so it appears order doesn't matter.
• Another case is if you delete the ancestor node first and you find that the minimum node is a child of the descendant node. This means that the descendant node will end up with one child, and deleting the one child is trivial. Now consider the case where in this scenario, you deleted the descendant node first. Then you would replace the value of the descendant node with its right child and then delete the right child. Then when you delete the ancestor node, you end up finding the same minimum node (the old deleted node's left child, which is also the replaced node's left child). Either way, you end up with the same structure.

这是不是一个严格的证明;这些都只是一些意见我做了。通过一切手段，随意万佛洞！

This is not a rigorous proof; these are just some observations I've made. By all means, feel free to poke holes!

这篇关于对于二叉搜索树删除程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！