java - BST 节点删除算法是如何工作的？

Question

我正在尝试遵循 "Data Structures and Algorithms" by Granville Barnett 中的 BST 算法，但我不明白下面描述的节点删除算法。

第 3.3 节(第 22 页)

Removing a node from a BST is fairly straightforward, with four cases to consider:

1. the value to remove is a leaf node; or
2. the value to remove has a right subtree, but no left subtree; or
3. the value to remove has a left subtree, but no right subtree; or
4. the value to remove has both a left and right subtree in which case we promote the largest value in the left subtree.

图 3.2(第 22 页)

    23
   /  \
  14   31
 /
7
 \
  9

• 情况 #1 指向节点 9。
• 案例 #2 指向节点 7。
• 情况 #3 指向节点 14。
• 情况 #4 指向节点 23。

我将上面的#4 文本解释为，当我们删除 23 时，我们会将 14 提升为根，并使 31 成为其右子节点:

  14
 /  \
7   31
 \
  9

...但是这本书的案例 #4 的算法(来自第 23 页)让我感到困惑(我已经用 Java 重写了它):

1 boolean remove(T value) {
2   // ...
3
4   // case #4
5   Node largestValueNode = nodeToRemove.left;
6   while (largestValueNode.right != null) {
7       // find the largest value in the left subtree of nodeToRemove
8       largestValueNode = largestValueNode.right;
9   }
10  
11  // delete the right child of largestValueNode's parent
12  findParent(largestValueNode.value).right = null;
13  nodeToRemove.value = largestValueNode.value;
14  
15  count--;
16  return true; // successful
17}

如果我遵循该算法，largestValueNode 是节点 14，因此其父节点是节点 23。 为什么该算法会取消父节点的右子节点？

为什么第 13 行将 largestValueNode 的值复制到要删除的节点中？

我预计第 11-13 行是:

11  if (largestValueNode != null)
12      largestValueNode.right = nodeToRemove.right;
13  nodeToRemove.right = null;

编辑:

书上的算法确实有bug。修复如下:

1 boolean remove(T value) {
2   // ...
3
4   // case #4
5   Node largestValueNode = nodeToRemove.left;
6   while (largestValueNode.right != null) {
7       // find the largest value in the left subtree of nodeToRemove
8       largestValueNode = largestValueNode.right;
9   }
10  
11  Node p = findParent(largestValueNode.value);
12  if (p != null) {
13      if (nodeToRemove == p)
14          nodeToRemove.left = largestValueNode.left;
15      else
16          p.right = largestValueNode.left;
17  }
18  nodeToRemove.value = largestValueNode.value;
19  
20  count--;
21  return true; // successful
22}

Answer 1

如果你这样做

11  if (largestValueNode != null)
12      largestValueNode.right = nodeToRemove.right;
13  nodeToRemove.right = null;

您没有考虑 14 可能有右 child 的情况。例如:

     23
    / \
   14  31
  / \
 7   15
  \
   9

删除 23 时的解决方案应该是

     15
    / \
   14  31
  / 
 7  
  \
   9

因此，您将 15 的原始父级 14 的右子级设置为 null。这就是第一个代码所做的事情。

编辑:处理您的评论

通过您的解决方案，您将获得

     23
    / 
   14  
  / \
 7   15
  \   \
   9   31

另外，原来的代码也是错误的；尝试这样的事情:

if(nodeToRemove == findParent(largestValueNode.value))
   nodeToRemove.left = largestValueNode.left
else
   findParent(largestValueNode.value).right = largestValueNode.left
nodeToRemove.value = largestValueNode.value

还要回答“为什么第13行将largestValueNode的值复制到要删除的节点中？”

我们正在删除 largestValueNode，在此之前我们将其值存储在 nodeToRemove