algorithm - 从二叉搜索树中删除是对称的吗？

Question

如果我删除节点 x，然后删除节点 y，或者删除 y 和 x，删除后我将保留相同的二叉搜索树吗？

我试了几个例子，我认为这是真的。

但是我怎样才能证明这一点呢？

Answer 1

这是假的。考虑树

  4
 / \
1   5
 \
  2
   \
    3 ,

其中 4 和 5 按某种顺序删除。如果顺序是5然后4，结果是

1
 \
  2
   \
    3 .

如果顺序是4然后5，结果可能是

  3
 /
1
 \
  2 ,

假设，当我们要删除一个有两个 child 的节点时，我们会用它的有序前任节点的值替换它的值并删除前任节点。 (我还假设零和一个子节点的标准删除过程。)

虽然我是手工找到这个例子的，但我经常求助于计算机的帮助。