Understanding parent nodes when removing node from BST

huangapple go评论85阅读模式
英文:

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 &lt; currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.left;
} else if (value &gt; currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.right;
} else {
if (currentNode.left !== null &amp;&amp; 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.leftparentNode.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.

huangapple
  • 本文由 发表于 2023年8月9日 05:25:16
  • 转载请务必保留本文链接:https://go.coder-hub.com/76863292.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定