删除二叉树中节点的方法

Question

我正在阅读一本书，该书解释了如何从二元搜索树中删除节点，基本上如果我们有这棵树：

       10
      /  \
     4    100
    / \
   1   8
      / \
     6   9
      \
       7

我们想删除节点4，书上说我应该：

1. 在其右子树（即6）中找到4的继任者
2. 交换4和6
3. 从右子树中删除6
4. 将4的左侧子树（在本例中仅为1）附加到新节点6

因此我们得到

       10
      /  \
     6    100
    / \
   1   8
      / \
     7   9

然而，我想到了另一种方法来做到这一点：

1. 找到4个右子树的最小元素（即6）
2. 将4的左子树附加到6（它不会有左子树）
3. 将父元素（10）附加到4的右侧元素（8）。如果算法是递归的，我们可以返回8

因此我们得到

       10
      /  \
     8    100
    / \
   6   9
  / \
 1   7

现在我想问：我看到我的解决方案产生了（至少在这种情况下）一个稍微不平衡的树。

我为什么要用我的书而不是我自己的书呢？似乎我的解决方案更容易实现（至少从我的角度来看），但如果我错了，我更希望其他人指出。

Answer 1

当您的树不平衡时，遍历树的时间会增加，因此您会失去使用BST的一些好处。

Answer 2

这两种方法的代码都特别复杂。

您的方法通常会产生一个不太平衡的树，因为您正在获取子树（1的子树）并将其（可能）向下移动很远。

按照他们的方法，7的子树向上移动1个节点，其他子树不移动。

可能只是因为他们没有考虑过你的方法，或者，如果他们考虑过，他们可能会选择自己的方法，因为树越不平衡，对它的查询性能就越差。

虽然这一讨论并不特别重要，因为基本的二元搜索树在实践中很少使用-而是使用自平衡树（由于试图维护某些属性以保持树的平衡，因此可以对此提出更有力的论点）。