如何做到这一点BST节点删除算法的工作？这一点、节点、算法、工作

2023-09-11 05:58:16 作者：风起时我会想你

我想通过遵循数据结构与算法的BST算法威巴尼特的，但我不明白的节点删除算法其描述如下：

第3.3节（第22页）

从BST中删除一个节点是相当简单的，有四个问题需要注意：

的值以除去是叶节点;或的值删除有右子树，但没有左子树;或的值删除有左子树，但没有右子树;或的值删除既有左，右子树在这种情况下，我们推动的左子树的最大值。

图3.2（第22页）

案例＃1点到节点9。案例＃2指向节点7。案例＃3点到节点14。案例＃4点到节点23。

我除$ P $磅以上＃4文字的意思是，当我们删除23，我们提倡14根，使31日的右子：

  14
 / \
7月31日
 \
  9

......但是这本书的算法（从第23页。）的情况下，＃4 bamboozles我（我在这里改写它在Java中）：

  1布尔删除（T值）{
2 // ...
3
4 //案例＃4
5节点largestValueNode = nodeToRemove.left;
6，而（largestValueNode.right！= NULL）{
7 //找到nodeToRemove的左子树的最大值
8 largestValueNode = largestValueNode.right;
9}
10
11 //删除largestValueNode的父权子
12 findParent（largestValueNode.value）.right = NULL;
13 nodeToRemove.value = largestValueNode.value;
14
15 count--;
16回归真实; //成功
17}

如果我按照算法， largestValueNode 是节点14，所以它的父节点23 为什么算法抵消父权子？

为什么13号线将 largestValueNode 的值到节点被删除？

我会一直期待线11-13为：

  11，如果（largestValueNode！= NULL）
12 largestValueNode.right = nodeToRemove.right;
13 nodeToRemove.right = NULL;

编辑：

这本书的算法确实有一个bug。解决方法是如下：

  1布尔删除（T值）{
2 // ...
3
4 //案例＃4
5节点largestValueNode = nodeToRemove.left;
6，而（largestValueNode.right！= NULL）{
7 //找到nodeToRemove的左子树的最大值
8 largestValueNode = largestValueNode.right;
9}
10
11节点p = findParent（largestValueNode.value）;
12，如果（P！= NULL）{
如果13（nodeToRemove == P）
14 nodeToRemove.left = largestValueNode.left;
15其他
16 p.right = largestValueNode.left;
17}
18 nodeToRemove.value = largestValueNode.value;
19
20 count--;
21回归真实; //成功
22}

解决方案

如果你这样做

  11，如果（largestValueNode！= NULL）
12 largestValueNode.right = nodeToRemove.right;
13 nodeToRemove.right = NULL;

你不考虑的情况下，其中 14 可能有一个正确的孩子。例如：

您是溶液中取出时， 23 应

所以，你设置的右子15 的原母公司， 14 为null。这是第一个code在做什么。

编辑：解决您的评论

使用您的解决方案，您将获得

此外，原来的code也是错误的;尝试是这样的：

 如果（nodeToRemove == findParent（largestValueNode.value））
   nodeToRemove.left = largestValueNode.left
其他
   findParent（largestValueNode.value）.right = largestValueNode.left
nodeToRemove.value = largestValueNode.value

另外回答，为什么13号线复制largestValueNode的值到要删除的节点？

我们正在删除 largestValueNode ，之前我们要存储它在价值 nodeToRemove

I'm trying to follow the BST algorithm in "Data Structures and Algorithms" by Granville Barnett, but I don't understand the node-deletion algorithm it describes below.

Section 3.3 (p. 22)

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

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

Figure 3.2 (p. 22)

Case #1 points to node 9. Case #2 points to node 7. Case #3 points to node 14. Case #4 points to node 23.

I interpret the text above for #4 to mean that when we remove 23, we promote 14 to root and make 31 its right child:

...but the book's algorithm (from p. 23) for case #4 bamboozles me (I've rewritten it here in 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}

If I follow the algorithm, the largestValueNode is node 14, so its parent is node 23. Why does the algorithm nullify the right child of the parent?

Why does line 13 copy the largestValueNode's value into the node to be deleted?

I would've expected lines 11-13 to be:

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

EDIT:

The book's algorithm indeed has a bug. The fix is below:

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}

解决方案

if you do this

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

you're not considering the case where 14 might have a right child. For example:

You're solution when removing 23 should be

So you're setting the right child of 15's original parent, 14 to null. This is what the first code is doing.

Edit: Addressing your comment

With your solution, you'll get

Also, the original code is also wrong; try something like this:

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

Also to answer, "Why does line 13 copy the largestValueNode's value into the node to be deleted?"

We're deleting largestValueNode, before which we're storing it's value in the nodeToRemove