代码之家 › 专栏 › 技术社区 › Bruno Oliveira

从BST中删除节点时了解父节点

binary-search-tree algorithm javascript

Bruno Oliveira · 技术社区 · 2 年前

我正试图从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 ?

2 回复 | 直到 2 年前

trincot 2 年前

该算法跟踪 parentNode 当它穿过树下降时 parentNode.left 或 parentNode.right 属性到 null 无论何时 currentNode 原来是要删除的节点。

现在,当你打电话 remove 同样,在您描述的情况下,您还需要传递 返回节点 ,因为这可能 currentNode.right 是一个没有左子节点的节点,因此是需要删除的节点。要进行删除,其父节点需要 right 要设置为的属性 无效的 ,因此需要参考它。

如果你能通过 无效的 对于该参数,在 currentNode.right 有一个左边的孩子——你会往下走,就这样坐着 返回节点 适当地。但对于没有留下孩子的情况那个需要删除的节点,因此我们需要知道它的父节点。

Barmar 2 年前

parentNode 当被移除的节点是子树的根时需要。在这种情况下,必须更新父节点中相应的子链接,以指向要删除的节点的相应子节点。

什么时候 parentNode === null ,这意味着要删除整个BST中最顶端的节点,因此没有父节点要更新。在移除树中间的节点时,不能使用该代码路径。