BST 删除节点方法 "cuts off" 树的其余部分

Question

我想编写一个从二叉搜索树中删除节点的方法。

这是我的方法：

public void remove(Node node)
 //Removes a given node and puts one of the nodes below it in its place until it reaches the end
 {
  
  if (node.left != null) //If the node to the left is not empty
  {
   node.value = node.left.value; //Moves up the left node to take its place
   remove(node.left); //Goes to the next node
   if (node.left.right == null && node.left.left == null)
    node.left = null; //Removes the last node at the end of the tree after moving it up
  }
  else if (node.right != null) 
  {
   node.value = node.right.value; //Moves up the left node to take its place
   remove(node.right); //Goes to the next node
   if (node.right.left == null && node.right.right == null)
    node.right = null; //Removes the last node at the end of the tree after moving it up
   
  } 
  
 }

问题是它只在某些情况下有效。

比方说我输入60、70、65。（根节点是50）树应该看起来像

假设我选择删除 60。一开始这似乎工作正常。但是，如果我然后运行我信任的搜索方法 returns 70 在它的任何指针处都没有节点。

我假设正在发生的事情是在 65 可以向上移动之前将 70 设置为空。由于 65 在技术上不再与树相连，因此搜索方法无法找到它。

所以像这样：

问题是，我不明白这是怎么发生的。特别是因为如果它的两个指针都指向空，它应该将节点设置为空，由于 if 语句

if (node.left.right == null && node.left.left == null)
                node.left = null;

和

if (node.right.left == null && node.right.right == null)
                node.right = null;

此外，如果第一个 if 语句不正确（如果 left != null），它不应该简单地继续到 "else"（并删除右边的）insted 吗？

非常欢迎任何建议或提示。

Answer 1

您的删除方法的逻辑存在严重缺陷。首先，你不是在移动节点而是在复制值，这已经是不正确的：因为任何节点都可以有两个 link，只复制左边或右边的 link 值，然后检查你是否在一片叶子上以最终将其移除是错误的：如果你不在一片叶子上怎么办？你让其他 link 落后了怎么办？在您的情况下，最终您将获得 70 右侧的值 65：不再是 BST。请记住，规则是对于任何节点 n，左子树中的所有节点必须小于 n，右子树中的所有节点必须大于 n。

这也是你找不到65的原因：不是因为70像你想的那样附加了两个空指针，而是因为你的搜索方法，当它到达70时，因为它大于 65，在节点 70 的 left 处搜索 65，并在那里找到一个 null。

这是在 BST 中删除节点的正确且经典的 Hibbard 算法：要删除节点 x，您必须将其替换为它的 后继节点。哪个是它的继任者？因为x有一个右child，它的后继是它右子树中key最小的节点。替换保留了树中的顺序，因为 x.key 和后继者的键之间没有键。我们分四步完成用其后继者替换 x 的任务：

保存一个link到t
设置 x 指向它的后继 min(t.right).
设置x的右边link（应该指向BST 包含大于 x.key) 到 deleteMin(t.right) 的所有键，则 link 到包含所有大于 x.key
的键的 BST 删除后。（要删除最小值，我们向左走，直到找到一个左侧为空 link 的节点，然后将 link 替换为右侧 link 的那个节点）
将 x 的左侧 link（为空）设置为 t.left（所有键小于删除的密钥及其后继密钥）。

BST 删除节点方法 "cuts off" 树的其余部分

BST remove node method "cuts off" rest of tree

java

tree

binary-search-tree