从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获取右子树的最小值替换待删除节点的值，随后调用currentNode.right.remove(currentNode.value, currentNode)移除该最小值节点。为什么要把currentNode作为parentNode参数传入？按道理remove方法会自行查找待删除节点并更新父节点，不能传入null吗？

解答 #

核心原因是避免触发错误的根节点删除逻辑，同时确保父节点的指针被正确更新，具体分两点说明：

1. 防止错误的节点修改逻辑
   假设待删除节点是A，A的右子树最小值节点就是右子树的根节点B（也就是B没有左孩子）。如果调用currentNode.right.remove(..., null)，此时remove方法里的parentNode为null，找到目标节点B后，会进入parentNode === null的分支——这个分支是用来处理删除整个树的根节点的逻辑，它会把B的值替换成其右孩子的值（如果有的话），再调整B的左右指针。但我们的需求是删除B节点，让A的right指针直接指向B的右孩子，而不是修改B本身的内容，传null会导致树结构不符合预期。

   而传入currentNode（也就是A）作为parentNode时，remove方法找到B后，会进入parentNode.right === currentNode的分支，直接把A的right指针设置为B的左/右孩子（这里B的左孩子是null，所以就是B的右孩子），这才是正确的删除逻辑。

2. 减少不必要的遍历
   我们已经明确知道要删除的最小值节点在currentNode.right这个子树里，且currentNode是该子树的父节点。传入这个parentNode可以让remove方法在遍历查找目标节点时，直接跟踪正确的父节点关系，不用从头开始推导父节点，提升效率。

内容的提问来源于stack exchange，提问作者Bruno Oliveira