英文:
Understanding parent nodes when removing node from BST
问题
我正在尝试从二叉搜索树(BST)中删除一个节点,实际上我已经让代码正常工作了,但其中有一部分我不理解。这是我的代码:
class BST {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
remove(value, parentNode = null) {
let currentNode = this;
while (currentNode !== null) {
if (value < currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.left;
} else if (value > currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.right;
} else {
if (currentNode.left !== null && currentNode.right !== null) {
currentNode.value = currentNode.right.getMinValue();
currentNode.right.remove(currentNode.value, currentNode);
} else if (parentNode === null) {
if (currentNode.left !== null) {
currentNode.value = currentNode.left.value;
currentNode.right = currentNode.left.right;
currentNode.left = currentNode.left.left;
} else if (currentNode.right !== null) {
currentNode.value = currentNode.right.value;
currentNode.left = currentNode.right.left;
currentNode.right = currentNode.right.right;
}
} else if (parentNode.left === currentNode) {
parentNode.left = currentNode.left !== null ? currentNode.left : currentNode.right;
} else if (parentNode.right === currentNode) {
parentNode.right = currentNode.left !== null ? currentNode.left : currentNode.right;
}
break;
}
}
return this;
}
getMinValue() {
let currentNode = this;
while (currentNode.left !== null) {
currentNode = currentNode.left;
}
return currentNode.value;
}
}
我在需要删除具有两个子节点的节点的边缘情况下使用了getMinValue
方法。我使用该方法将当前节点(我要删除的节点)的值替换为该节点右子树中的最小值。然后,我调用remove
方法从右子树中删除同一个节点。
我不理解的是以下这行代码:
currentNode.right.remove(currentNode.value, currentNode);
我知道这行代码是在删除用作基准节点替代的节点,但我不明白为什么我必须将currentNode
作为parentNode
参数传递。难道remove
方法不需要先找到需要删除的节点,从而改变parentNode
的值吗?为什么我不能将该参数设为null
?
英文:
I am trying to remove a node from a BST and I actually got the code to work but there is one part of it I do not understand. This is my code:
class BST {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
remove(value, parentNode = null) {
let currentNode = this;
while (currentNode !== null) {
if (value < currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.left;
} else if (value > currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.right;
} else {
if (currentNode.left !== null && currentNode.right !== null) {
currentNode.value = currentNode.right.getMinValue();
currentNode.right.remove(currentNode.value, currentNode);
} else if (parentNode === null) {
if (currentNode.left !== null) {
currentNode.value = currentNode.left.value;
currentNode.right = currentNode.left.right;
currentNode.left = currentNode.left.left;
} else if (currentNode.right !== null) {
currentNode.value = currentNode.right.value;
currentNode.left = currentNode.right.left;
currentNode.right = currentNode.right.right;
}
} else if (parentNode.left === currentNode) {
parentNode.left = currentNode.left !== null ? currentNode.left : currentNode.right;
} else if (parentNode.right === currentNode) {
parentNode.right = currentNode.left !== null ? currentNode.left : currentNode.right;
}
break;
}
}
return this;
}
getMinValue() {
let currentNode = this;
while (currentNode.left !== null) {
currentNode = currentNode.left;
}
return currentNode.value;
}
}
I use the getMinValue
method for the edge case where I have to remove a node with two children nodes. I use that method to replace the current node's value (the one that I'm removing) with the lowest value from the right subtree of that node. I then call the remove
method to remove that same node from the right subtree.
What I don't understand is the following line:
currentNode.right.remove(currentNode.value, currentNode);
I know that this line is removing the node that was used as a replacement for the base node but I don't understand why I have to pass the currentNode
as the parentNode argument.
Won't the remove method have to find the node that needs to be removed first and hence change the parentNode
value anyways? Why can't I just make that argument null
?
答案1
得分: 1
这个算法在遍历树的过程中通过跟踪parentNode
来设置parentNode.left
或parentNode.right
属性为null
,以便在currentNode
被删除时进行操作。
现在,当你在描述的情况下再次调用remove
时,你还需要传递一个parentNode
的引用,因为可能是currentNode.right
是一个没有左子节点的节点,因此需要被删除。为了进行删除操作,它的父节点需要将其right
属性设置为null
,因此需要一个对其的引用。
如果你将该参数设置为null
,在currentNode.right
有左子节点的情况下,它将正常工作--你会继续向下遍历并相应地设置parentNode
。但对于没有左子节点的情况,就需要删除那个节点,因此我们需要知道它的父节点。
英文:
This algorithm keeps track of parentNode
as it descends through the tree so that it can set the parentNode.left
or parentNode.right
property to null
whenever currentNode
turns out to be the node to be removed.
Now when you call remove
again in the case you describe, you also need to pass on a reference for parentNode
, as it might be that this currentNode.right
is a node without left child, and thus is the one that needs to be removed. For that removal to happen, its parent node needs its right
property to be set to null
, and so a reference to it is needed.
If you would pass null
for that parameter it would work fine in cases where currentNode.right
has a left child -- you would descend further down and so set parentNode
appropriately. But for the case where it doesn't have a left child, it is that node that needs to be removed, and so we need to know its parent.
答案2
得分: 0
parentNode
在删除的节点是子树的根节点时是必需的。在这种情况下,需要更新父节点中相应的子链接,使其指向被删除节点的相应子节点。
当 parentNode === null
时,意味着你正在删除整个二叉搜索树中的最顶层节点,所以没有父节点需要更新。当你删除树中间的节点时,不能使用这段代码路径。
英文:
parentNode
is needed when the node being removed is the root of the subtree. In this case, the appropriate child link in the parent has to be updated to point to the corresponding child of the node being removed.
When parentNode === null
, it means you're removing the top-most node in the entire BST, so there's no parent to update. You can't use that code path when you're removing a node in the middle of the tree.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论