删除BST中的多个节点会更改生成的树？

Question

如果我需要删除BST中的多个节点，生成的树会不同地改变删除顺序？正常的左右顺序将被保留，但我不确定树结构。

这是一个“phisolophical”问题，我需要一个dimostration或反例。

Answer 1

为了证明删除的顺序对最终树没有影响，证明任何两个删除操作都是通行的（也就是说，如果它们的顺序相反，它们具有相同的效果）是必要且足够的。

删除节点的效果仅限于该节点及其所在的子树。所以如果两个节点是分开的（即两个节点都不在另一个之下），那么它们的删除就会通过。因此，唯一感兴趣的案例在另一个子树中有一个节点。

不失一般性，假设我们使用的规则是，当我们删除一个有两个孩子的节点时，我们用它的后继替换它。如果B在A的左子树中，那么删除就会通过，因为A的删除对A的左子树没有影响，并且B的删除没有效果 A的左子树。所以唯一的情况是B在A的右子树中。

当A被删除时，对A的右子树的效果与A的后继者已被删除的效果相同。假设B是而不是 A的继任者;我们将调用A的继承者C.删除A包括从右子树中删除C和用C（通勤）替换A，所以如果B和C的删除通过，那么删除A和B通勤。通过归纳，如果任何一对删除不通勤，那么删除A和B（其中B是A的后继者）不通勤。

但是删除A及其继承人通过检查通勤。证明完毕

Answer 2

Deleting 1 and 2 in different order results in two different trees反例： 删除1和2的顺序导致不同的BST。 因为当你首先要删除2时，你必须在它的 右子树中找到下一个元素，即3，并用2替换，但是当你首先删除1然后你想删除2时，现在它已经有了只有一个孩子，只是它的孩子取代它，即4。 因此导致两棵不同的树。