这段代码为什么需要从BST中删除？

我想了解更多关于二叉树的知识，并且我遇到了关于如何找到后继节点（当试图删除节点时）的方法，但我很难理解它的一部分。这是代码。这段代码为什么需要从BST中删除？

private Node getSuccessor(Node delNode){ 
    Node successorParent = delNode; 
    Node successor = delNode; 
    Node current = delNode.rightChild; 

    while(current != null){ 
     successorParent = successor; 
     successor = current; 
     current = current.leftChild; 
    } // end of if 

    if(successor != delNode.rightChild){ 
     successorParent.leftChild = successor.rightChild; 
     successor.rightChild = delNode.rightChild; 
    } 
    return successor; 


}

我完全理解了while循环以及那里的内容。我不明白的是if语句，特别是...

successor.rightChild = delNode.rightChild;

我为什么要将delNode的右侧子项分配给后继节点的右侧子项？为什么if语句是必要的？

来源

2017-08-12 Rocky Singh

你自己想出这个最简单的方法就是运行代码并观察两者之间的区别。 – Carcigenicate

说实话，没有仔细阅读核心*，这看起来不像任何普通的“在二叉树中找到任何东西”的实现，因为它**修改了树。然而，一个splay树通过将查询的节点移动到树顶部来修改树，但是问题中的代码还不足以实现这一点。 –

@Carcigenicate这是真的！我会尽力做到这一点。 –

getSuccessor（）所做的是找到delNode的后继者，该节点的最小值大于delNode，即delNode下右侧子树中最左侧的节点。然后它将它从正确的子树中移除，并将右侧子树连接到后继的右侧。

有条件的原因是，如果后继者是delNode的正确子节点，它已经在右侧子树的顶部，并且不需要从子树中移出并移动到顶部的。

在接下来的步骤中，delNode将被删除，后继将附加到delNode的父节点，并且delNode下的左侧子树将被附加到继承者的左侧。所有这些的影响是将delNote替换为其后继者。（这种方法不是从二叉树中删除一个节点的最直接的方法，你可以简单地将右子树连接到delNode的父节点，左子树连在后继节点上，但是这个更复杂的方法有不增加树的高度的优点，因为每个节点保持在相同的深度，或者移动靠近根。）

这里是一个我们要删除节点3的例子：我们发现它的后继者是4，我们从右边的子树中移除4并将它放在子树的顶部，然后我们用后继者4替换节点3，并将左边的子树连接到它：

 9            9 
    /\           /\ 
    3 ...      4     4 ... 
/\        \    /\ 
    2 6    6    6    2 6 
//\   /\   /\   //\ 
1 4 7   4 7   5 7   1 5 7 
    \ \   \ \    \     \ 
     5 8   5 8    8     8

（你会去除该节点后发现，每一个节点是在同一深度它之前，或已移近根，所以树的高度并没有增加。）

现在考虑一个例子，我们再次删除节点3，但我们发现它的后继节点4已经在右侧子树的顶部;这意味着我们可以通过后继4立即更换节点3和左子树附加到它，而不必首先移动节点4到右子树的顶部：

 8         8 
    /\        /\ 
    3 ...       4 ... 
/\        /\ 
    2 4    4    2 6 
/ \    \   //\ 
1  6    6   1 5 7 
    /\   /\   
     5 7   5 7

来源

2017-08-12 22:47:15 m69

有两种情况，此代码试图解释。第一种情况是你删除一个节点X，其继任者Y是其直接右孩子：

在这种情况下，我们最终要为Y来代替X，因此该方法可以只返回Y和说“这里是现在取代X的节点。“

在另一方面，假设X的继任者Y是在其右子树的子树：

X 
\ 
    A 
/\ 
Y C 
\ 
    B

在这种情况下，我们不能盲目地，其中Y代替X，因为这样做会失去节点A和其中所有的树C.所以才说：“哎树 - 去与节点Y代替节点X，”我们重新排列树中的节点，使它们看起来就像这样：

X 
\ 
    Y 
    \ 
    A 
/\ 
    B C

现在，当我们用Y替换X时，我们并没有丢失树中的任何其他节点。

顺便提一句，这里的形状是通过交换X和Y，然后通过使Y的前父母将Y的前右子树作为其左子元素来删除X（它在Y中的位置）来形成的。通过这些线追踪，看看你是否能看到这是如何工作的。

来源

2017-08-12 23:02:19 templatetypedef

这段代码为什么需要从BST中删除？

回答

相关问题