在二进制搜索树中删除？

Question

我正在阅读" 数据结构和算法:带注释的实例 "一书中使用的二叉树删除节点算法

在第34页,案例4(删除具有左右子树的节点),下面的书中描述的算法看起来不起作用,可能我可能是错的,有人可以帮助我,我错过了什么.

//Case 4
get largestValue from nodeToRemove.Left
FindParent(largestValue).Right <- 0
nodeToRemove.Value<-largestValue.Value

以下行如何从子树中删除最大值 FindParent(largestValue).Right <- 0

Answer 1

删除具有两个子节点的节点时,可以选择其有序后继节点或其有序前驱节点.在这种情况下,它找到左子树中的最大值(意味着其左子树的最右边的子节点),这意味着它正在查找节点的有序前导节点.

找到替换节点后,实际上不会删除要删除的节点.而是从后继节点获取值并将该值存储在要删除的节点中.然后,删除后继节点.这样做可以保留二进制搜索树属性,因为您可以确定所选节点的值低于原始节点左侧子树中所有子节点的值,并且大于值原始节点的右子树中的所有子节点.

编辑

在仔细阅读了你的问题之后,我想我已经找到了问题.

通常,除了delete函数之外,您还拥有一个replace替换相关节点的函数.我想你需要改变这行代码:

FindParent(largestValue).Right <- 0

至:

FindParent(largestValue).Right <- largestValue.Left

如果largestValue节点没有左子节点,则只需获取null或0.如果它确实有一个左子项,则该子项将成为该largestValue节点的替代项.所以你是对的; 代码没有考虑largestValue节点可能有左子节点的场景.

另一个编辑

由于您只发布了一个代码段,我不确定代码的上下文是什么.但是发布的片段似乎确实存在您建议的问题(替换错误的节点).通常,有三种情况,但我注意到你的片段中的评论说//Case 4(所以可能还有其他一些背景).

早些时候,我提到了delete通常附带的事实replace.因此,如果找到largestValue节点,则根据两个简单情况(没有子节点的节点和具有一个子节点的节点)将其删除.因此,如果您正在查看伪代码以删除具有两个子节点的节点,那么您将执行以下操作:

get largestValue from nodeToRemove.Left
nodeToRemove.Value <- largestValue.Value

//now replace largestValue with largestValue.Left    

if largestValue = largestValue.Parent.Left then   
   largestValue.Parent.Left <- largestValue.Left //is largestValue a left child?
else //largestValue must be a right child
   largestValue.Parent.Right <- largestValue.Left

if largestValue.Left is not null then
   largestValue.Left.Parent <- largestValue.Parent

我觉得奇怪的是,数据结构和算法书会遗漏这一部分,所以我倾向于认为这本书进一步将删除分成几个案例(因为有三个标准案例),以便更容易了解.

要证明上述代码有效,请考虑以下树:

  8
 / \
7   9

假设您要删除8.你试图找到largestValue从nodeToRemove.Left.这给了你,7因为左子树只有一个孩子.

然后你做:

nodeToRemove.Value <- largestValue.Value

意思是:

8.value <- 7.Value

要么

8.Value <- 7

所以现在你的树看起来像这样:

  7
 / \
7   9

您需要摆脱替换节点,因此您将替换largestValue为largestValue.Left(即null).所以首先你要找出什么样的孩子7:

if largestValue = largestValue.Parent.Left then

意思是:

if 7 = 7.Parent.Left then

要么:

if 7 = 8.Left then

既然7是8小孩,需要8.Left用7.Right(largestValue.Parent.Left <- largestValue.Left)代替.由于7没有孩子,7.Left是null.因此largestValue.Parent.Left被赋值为null(有效地删除了它的左子).所以这意味着你最终得到了以下树:

  7
   \
    9