在二叉搜索树中删除？
我正在阅读《数据结构和算法》一书中使用的二叉树删除节点算法：带示例的注释参考
第 34 页，案例 4（删除同时具有左右子树的节点），遵循书中描述的算法看起来不起作用，可能我可能是错的有人可以帮助我吗？我失踪了。
//Case 4
get largestValue from nodeToRemove.Left
FindParent(largestValue).Right <- 0
nodeToRemove.Value<-largestValue.Value
下面这行如何从子树中删除最大值 FindParent(largestValue).Right <- 0
I am reading through the binary tree delete node algorithm used in the book Data Structures and Algorithms: Annotated Reference with Examples
on page 34 , case 4(Delete node which has both right and left sub trees), following algorithm described in the book looks doesn't work, probably I may be wrong could someone help me what I am missing.
//Case 4
get largestValue from nodeToRemove.Left
FindParent(largestValue).Right <- 0
nodeToRemove.Value<-largestValue.Value
How does the following line deletes the largest value from sub tree FindParent(largestValue).Right <- 0
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
删除具有两个子节点的节点时，可以选择其有序后继节点或有序前驱节点。在这种情况下，它正在查找左子树中的最大值（意味着其左子树的最右边的子节点），这意味着它正在查找该节点的有序前驱节点。
一旦找到替换节点，您实际上并没有删除要删除的节点。相反，您从后继节点获取值并将该值存储在要删除的节点中。然后，删除后继节点。这样做可以保留二叉搜索树属性，因为您可以确定所选节点的值低于原始节点左子树中所有子节点的值，并且大于该值原始节点的右子树中的所有子节点。
编辑
再读一点你的问题后，我想我已经找到了问题所在。
通常，除了
delete函数之外，您还可以使用replace函数来替换有问题的节点。我认为您需要将这行代码更改为：
如果
largestValue节点没有左子节点，您只需得到null或0.如果它确实有左子节点，则该子节点将替换largestValue节点。所以你是对的；该代码没有考虑largestValue节点可能有左子节点的情况。另一个编辑
由于您只发布了一个片段，我不确定代码的上下文是什么。但发布的代码片段似乎确实存在您建议的问题（替换错误的节点）。通常，有三种情况，但我注意到您的代码片段中的注释是
//Case 4（所以可能还有其他上下文）。早些时候，我提到了
删除通常伴随着替换这一事实。因此，如果找到了 LargestValue 节点，则根据两种简单情况（没有子节点的节点和有一个子节点的节点）将其删除。因此，如果您正在查看伪代码来删除具有两个子节点的节点，这就是您要做的：我觉得很奇怪，数据结构和算法书会省略这一部分，所以我倾向于认为本书将删除进一步分成了几个案例（因为有三个标准案例），以便于理解。
为了证明上述代码有效，请考虑以下树：
假设您要删除
8。您尝试从nodeToRemove.Left查找largestValue。这将为您提供7，因为左子树只有一个子树。然后你会这样做：
这意味着：
或者
现在你的树看起来像这样：
你需要删除替换节点，所以你要用
largestValue.Left替换largestValuecode>（为null）。所以首先你要找出7是什么类型的孩子：这意味着：
或者：
由于
7是8的左孩子，需要替换8.Left与7.Right(largestValue.Parent.Left <-largestValue.Left)。由于7没有子级，因此7.Left为 null。因此，largestValue.Parent.Left被分配为 null（这实际上删除了其左子节点）。所以这意味着您最终会得到以下树：When deleting a node with two children, you can either choose its in-order successor node or its in-order predecessor node. In this case it's finding the the largest value in the left sub-tree (meaning the right-most child of its left sub-tree), which means that it is finding the node's in-order predecessor node.
Once you find the replacement node, you don't actually delete the node to be deleted. Instead you take the value from the successor node and store that value in the node you want to delete. Then, you delete the successor node. In doing so you preserve the binary search-tree property since you can be sure that the node you selected will have a value that is lower than the values of all the children in the original node's left sub-tree, and greater that than the values of all the children in the original node's right sub-tree.
EDIT
After reading your question a little more, I think I have found the problem.
Typically what you have in addition to the
deletefunction is areplacefunction that replaces the node in question. I think you need to change this line of code:to:
If the
largestValuenode doesn't have a left child, you simply getnullor0. If it does have a left child, that child becomes a replacement for thelargestValuenode. So you're right; the code doesn't take into account the scenario that thelargestValuenode might have a left child.Another EDIT
Since you've only posted a snippet, I'm not sure what the context of the code is. But the snippet as posted does seem to have the problem you suggest (replacing the wrong node). Usually, there are three cases, but I notice that the comment in your snippet says
//Case 4(so maybe there is some other context).Earlier, I alluded to the fact that
deleteusually comes with areplace. So if you find thelargestValuenode, you delete it according to the two simple cases (node with no children, and node with one child). So if you're looking at pseudo-code to delete a node with two children, this is what you'll do:I find it strange that a Data Structures And Algorithms book would leave out this part, so I am inclined to think that the book has further split up the deletion into a few more cases (since there are three standard cases) to make it easier to understand.
To prove that the above code works, consider the following tree:
Let's say that you want to delete
8. You try to findlargestValuefromnodeToRemove.Left. This gives you7since the left sub-tree only has one child.Then you do:
Which means:
or
So now your tree looks like this:
You need to get rid of the replacement node and so you're going to replace
largestValuewithlargestValue.Left(which isnull). So first you find out what kind of child7is:Which means:
or:
Since
7is8's left child, need to replace8.Leftwith7.Right(largestValue.Parent.Left <- largestValue.Left). Since7has no children,7.Leftis null. SolargestValue.Parent.Leftgets assigned to null (which effectively removes its left child). So this means that you end up with the following tree:这个想法是简单地从左侧最大的节点中取出值并将其移动到要删除的节点，即根本不删除该节点，只需替换它的内容。然后，用移入“已删除”节点的值删除该节点。这保持了树的排序，每个节点的值都大于它的所有左子节点并且小于它的所有右子节点。
The idea is to simply take the value from the largest node on the left hand side and move it to the node that is being deleted, i.e., don't delete the node at all, just replace it's contents. Then you prune out the node with the value you moved into the "deleted" node. This maintains the tree ordering with every node's value larger than all of it's left children and smaller than all of it's right children.
我认为您可能需要澄清什么不起作用。
我将尝试解释二叉树中删除的概念，以防有帮助。
假设树中的一个节点有两个要删除的子节点。
在下面的树中，假设您要删除节点 b
a
/ \
b c
/ \ / \
d e f g
当我们删除一个节点时，我们需要重新附加它的依赖节点。
IE。当我们删除 b 时，我们需要重新附加节点 d 和 e。
我们知道左节点的值小于右节点的值，并且父节点的值介于左节点和右节点之间。在这种情况下，d＜1。 b 且 b ＜ e.这是二叉树定义的一部分。
稍微不太明显的是 e <一个。所以这意味着我们可以用 e 代替 b 。现在我们已经重新连接了 e，我们需要重新连接 d。
如前所述 d < e 因此我们可以将 e 作为 e 的左节点。
删除现已完成。
（顺便说一句，以这种方式在树上移动节点并重新排列依赖节点的过程称为升级节点。您还可以升级节点而不删除其他节点。）
a
/ \
d c
\ / \
e f g
请注意，删除节点 b 还有另一个完全合法的结果。
如果我们选择提升节点 d 而不是节点 e，树将如下所示。
a
/ \
c
/ / \
d f 克
I think you may need to clarify what doesn't work.
I will try and explain the concept of deletion in a binary tree in case this helps.
Lets assume that you have a node in the tree that has two child nodes that you wish to delete.
in the tree below lets say that you want to delete node b
a
/ \
b c
/ \ / \
d e f g
When we delete a node we need to reattach its dependant nodes.
ie. When we delete b we need to reattach nodes d and e.
We know that the left nodes are less than the right nodes in value and that the parent nodes are between the left and right node s in value. In this case d < b and b < e. This is part of the definition of a binary tree.
What is slightly less obvious is that e < a. So this means that we can replace b with e. Now we have reattached e we need to reattach d.
As stated before d < e so we can attach e as the left node of e.
The deletion is now complete.
( btw The process of moving a node up the tree and rearranging the dependant nodes in this fashion is known as promoting a node. You can also promote a node without deleting other nodes.)
a
/ \
d c
\ / \
e f g
Note that there is another perfectly legitimate outcome of deleteing node b.
If we chose to promote node d instead of node e the tree would look like this.
a
/ \
e c
/ / \
d f g
如果我理解伪代码，它在一般情况下可以工作，但在“左子树中的一个节点”情况下会失败。不错的收获。
它有效地将要删除的node_to_remove替换为其左子树中的largest_value（也将旧的largest_value节点清空）。
请注意，在 BST 中，node_to_remove 的左子树都将小于 node_to_remove。 node_to_remove 的右子树都将大于node_to_remove。因此，如果您取左子树中最大的节点，它将保留不变式。
如果这是“子树情况下的一个节点”，它将破坏右子树。 Lame :(
正如 Vivin 指出的那样，它也无法重新附加largestNode 的左子节点。
If I understand the pseudo-code, it works in the general case, but fails in the "one node in the left subtree" case. Nice catch.
It effectively replaces the node_to_remove with largest_value from it's left subtree (also nulls the old largest_value node).
Note that in a BST, the left subtree of node_to_remove will be all be smaller than node_to_remove. The right subtree of node_to_remove will all be larger than node_to_remove. So if you take the largest node in the left subtree, it will preserve the invariant.
If this is a "one node in the subtree case", it'll destroy the right subtree instead. Lame :(
As Vivin points out, it also fails to reattach left children of largestNode.
当您查看维基百科对算法这一部分的看法时，可能会更有意义:
请注意，给定的算法选择按顺序的前驱节点。
编辑：似乎缺少 R（使用维基百科的术语）有一个孩子的可能性。递归删除可能效果更好。
It may make more sense when you look at the Wikipedia's take on that part of the algorithm:
Note that the given algorithm chooses the in-order predecessor node.
Edit: what appears to be missing the possibility that R (to use Wikipedia's terminology) has one child. A recursive delete might work better.