c - 二叉搜索树中节点的删除

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，请执行以下操作:

1. 选择 B 或 C 作为其替代节点，您将提升该节点以取代 A。
2. 将另一个子节点(B 或 C)挂接到第一个子节点(B 或 C)上
   • 如果您选择 B 作为 A 的替代品，则需要将 C 挂接到 B 作为其新的最左侧子节点
   • 如果您选择 C ​​作为 A 的替代品，则需要将 B 挂接到 C 作为其新的最右侧子节点

“最左/最右子节点”我的意思是，只要在该方向上有子节点，您就需要向左或右方向向下导航，然后当您到达没有左/右子节点的节点时(根据你要去哪个方向)，将“其他节点”挂入其中作为该方向的新子节点。

让我们首先考虑选择 B，你最终会得到这样的结果:

   B
    \
     ...
        \
         C

如果你先选择 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 作为其最左边的子树，从而得到最终的树:

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

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

促销5:

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

然后将 18 挂接到 5 作为其新的最右边子树:

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

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