二叉搜索树中节点的移除

Question

我的 BST 看起来像这样：我正在尝试删除节点 12（有 2 个子节点），我想知道我是否正确删除了它？

移除前

          12
        _/   \_
     5          18
  /     \     /     \
 =       =   15     19
 2       9   /  \     
            13   17

移除后：

          18
        _/   \_
     5          19
  /     \     /    
 =       =   15     
 2       9   /  \     
            13   17

我的实现是否正确？谢谢

删除后编辑更新：

          13
        _/   \_
     5          18
  /     \     /    \
 =       =   15     19
 2       9     \     
                17

Answer 1

举个简单的例子

考虑这棵树：

  A
 / \
B   C

要删除 A，请执行以下操作：

选择 B 或 C 作为其替代品，您将此节点提升以取代 A。
取另一个子节点（B或C）并将其挂接到第一个（B或C）
- 如果您选择 B 作为 A 的替代品，则需要将 C 挂接到 B 作为其新的最左侧子节点
- 如果您选择 C 作为 A 的替代品，则需要将 B 挂接到 C 作为其新的最右子节点

By "left/rightmost subnode" 我的意思是你需要向左或向右方向向下导航，只要你在那个方向有子节点，那么当你到达一个没有 left/right 子节点的节点时（根据您要去的方向），将 "other node" 作为该方向的新子节点挂接到它。

让我们考虑先选择 B，你会得到这样的结果：

如果你先选 C，你会得到这样的结果：

      C
     /
  ...
 /
B

所以回到你的树，它开始是这样的：

        12
      /    \
     5      18
    / \    /  \
   2   9  15   19
         /  \
        13   17

要删除 12，而您选择 18 来替换它，您首先提升 18：

     5      18
    / \    /  \
   2   9  15   19
         /  \
        13   17

然后，由于 18 对应于我前面示例中的 C，您需要将 5 挂接到 18 作为其最左边的子树，从而得到最终的树：

让我们看看如果我们选择 5 代替 12 会发生什么：

推广 5：

     5      18
    / \    /  \
   2   9  15   19
         /  \
        13   17

然后将18挂钩到5作为它新的最右子树：

两者都可以。关于 Wikipedia page 可能还有更多值得一读的信息。

Removal of Node in Binary Search Tree