BST删除节点方法“切断”树的其余部分

Question

我想写一个从二叉搜索树中删除节点的html" target="_blank">方法。

这是我的方法：

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）树应该看起来像

   50
  /  \
     60
    /   \
        70
       /  \
      65

假设我选择移除60个。一开始这似乎很管用。然而，如果我运行我信任的搜索方法，返回70在任何一个指针上都没有节点。

我假设70被设置为空，然后65才能被提升。由于65在技术上不再与树相连，搜索方法无法找到它。

所以像这样的事情：

   50
  /  \
     70
    /   \

       /  \
      65

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

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语句不是true（if left！=null），它不应该继续执行所指示的“else”（并删除右边的那一个）吗？

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

Answer 1

你移除方法的逻辑有很大缺陷。首先，你不是在移动节点，而是在复制值，这已经是不正确的：因为任何节点都可以有两个链接，只复制左边或右边的链接值，然后检查你是否在某个叶上，最终删除它是错误的：如果你不在某个叶上呢？你背后的另一个环节呢？在你的例子中，最后70的右边是65：不再是BST。记住，规则是，对于任何节点n，左子树中的所有节点都必须小于n，右子树中的所有节点都必须大于n。

这也是你找不到65的原因：这不是因为70有两个空指针，像你想象的那样，而是因为你的搜索方法，当它到达70时，因为它比65大，在节点70的左边搜索65，在那里它找到一个空。

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

>

保存到t中要删除的节点的链接

将x设置为指向其后续的min（右t）。

将x的右链接（应该指向包含大于x.key的所有键的BST）设置为deleteMin（t.right），删除后指向包含大于x.key的所有键的BST的链接
。（要删除最小值，我们向左走，直到找到一个左链接为空的节点，然后用右链接替换到该节点的链接）

将x的左链接（为空）设置为t.left（所有小于已删除键及其后继键的键）。