如何用2个孩子从BST树中删除节点？

Question

我Googled，阅读若干教程并在发布此问题之前观看几个BST节点删除算法的说明。出于某种原因，我找不到BST节点删除算法的完整说明。

我发现了4种算法删除与二进制搜索树的2个孩子的节点：
1）从右子树上找到最小的节点，并用我们要删除的节点替换它。
2）从左子树上找到最大的节点，并用我们要删除的节点替换它。
3）从右侧树上找到最深的最左边的节点，并用我们要删除的节点替换它。
4）从左子树中找到最右边的最右侧节点，并将其替换为我们要删除的节点。

显然，这些算法都没有适用于下一个用例（最有可能因为我缺少或不理解某事）。使用情况是从下一树中删除元素5：

对于第一算法，我们将选择元素6并将失去其右侧树。对于第二种算法，我们将选择元素4并将失去其左子树。对于第三算法，我们将选择元素7并且将违反BST规则。对于第4次算法，我们将选择元素3，该元素3也将违反BST规则。

这种用例的正确算法是什么？

Answer 1

您是对的，通常在BST中，节点有两个子节点的情况被降低到节点有一个孩子的情况。

考虑一个有两个孩子的节点。在BST中使用其前部（即左子树中最右侧节点）交换此节点，或者 - 使用后继（右子树中最左侧节点）交换。

交换

现在要删除的节点最多一个孩子（如果我们为前身前往它，它就不能有正确的孩子）。 如果它没有孩子我们删除节点，我们完成了。

如果节点具有单个子子，我们删除节点并将其替换为其子树。我们再次获得BST。

在您的榜样中我们要删除5并将其交换为其前身4.现在4位于root中，5个已留下儿童3.最后我们删除5并将其孩子放在其位置。现在3是正确的2。

ps。此方法有时称为“通过复制删除”，因为值将从一个节点复制到另一个节点。有些人不赞成这个过程有两个原因。第一个复制可能是昂贵的操作，第二个引用丢失（如果另一个数据结构指向具有特定值的节点）。相反，一个只会改变指针。