我正在try 删除二叉搜索树中的根 node .

Remove(1)给出正确的输出,但它不会改变树本身.

因此,如果我在调用bst.Remove(1)之后判断bst,则输出不同.为什么会这样呢?

如果我运行bst=bst.left||bst.right;,我会得到正确的输出,这让我相信我的函数没有改变原始树.

remove(key) {
   return this.removeImpl(key, this);
  }

  removeImpl(key, node){  
    
      if (node != null) {
      if (key < node.value) {
        // Key might be in the left subtree.
        node.left = this.removeImpl(key, node.left);
      } else if (key > node.value) {
        node.right = this.removeImpl(key, node.right);
      } else {
        // Node found. 
        // Let's see if it has two children.
        
        
        if (node.left && node.right) {
          // Replace current node with 
          // predecessor data
          
          node.value = this.minimum(node.right);
          node.right = this.removeImpl(node.value, node.right);
        } else {
          // Only 1 child.
          // Let's return the child that's valid.
          
          node = node.left || node.right; //node to be removed becomes it's right or left child
    
        }
      }
    }
    return node;
  }

var bst=new BST(1);
bst.insert(2);
bst.insert(3);
bst.insert(4);

bst.remove(1);

推荐答案

bst.remove(1)给出了正确的输出,但它不会改变树本身.

这是有意的.你所说的"树本身",实际上是根 node .您的代码没有单独类形式的树的概念--根 node 的树(只)是implied.由于 node 的删除不是已删除 node 的Mutations ,而是其他引用的Mutations ,并且您对该根 node 的唯一引用是bst变量,因此您需要从assignmentbst.在树的最后一个 node 被删除的极端情况下,您会期望bst变成null,因此同样需要assignmentbst.因为这个bst变量不是某个类实例的属性,所以您需要在主代码中"自己"管理这个赋值.

以下是分析这种情况的另一种方式:

removeImpl功能relies on the callerreturned node 连接到正确的位置.你可以看到,removeImpl每拨打recursive个电话,就会发生这种情况.例如:

  node.left = this.removeImpl(key, node.left);
  node.right = this.removeImpl(key, node.right);

所以我们可以说caller基因Mutations 了这棵树.如果removeImpl本身是(递归调用的)调用方,则它自己执行变异,但removeImplinitial调用方(即remove)也会这样做:

return this.removeImpl(key, this);

在这里,我们看到对返回的 node 执行某些操作的责任被级联到remove的调用方.调用者应该应用这一原则,这就是您当前的代码所缺少的.我们在这里看到了remove的呼唤:

bst.remove(1)

但该调用ignores是返回 node .remove不应该是这样称呼的.应该这样称呼它:

bst = bst.remove(1)

对于该更改,代码一致地使用由removeremoveImpl方法返回的 node 来捕获更改.

两级制

以上内容可能看起来过于冗长.如果您想让bst.remove(1)来做这项工作,而不需要给bst赋值,那么您应该考虑一个两类系统,而不是您当前的单类实现.

然后将当前的BST类重命名为Node,并创建第二个类,该类将成为容器类,并且可以命名为BST.当您将BST重命名为Node时,不要忘记在创建 node 时也使用该名称(如在insert方法中,new BST应变为new Node).

然后添加:

class BST {
    constructor() {
        self.root = null; // Now the root is a property, not a global variable
    }
    insert(key) {
        if (self.root == null) self.root = new Node(key);
        else self.root.insert(key);
    }
    remove(key) {
        if (self.root) {
            // Now we mutate the container instance:
            self.root = self.root.remove(key);
        }
    }
}

var bst = new BST();
for (let value of [1, 2, 3, 4]) bst.insert(value);
bst.remove(1);

Javascript相关问答推荐

构造HTML表单以使用表单数据创建对象数组

数字时钟在JavaScript中不动态更新

无法访问Vue 3深度监视器中对象数组的特定对象值'

在带有背景图像和圆形的div中添加长方体阴影时的重影线

React.Development.js和未捕获的ReferenceError:未定义useState

在css中放置所需 colored颜色 以填充图像的透明区域

VSCode中出现随机行

如何使本地html页面在重新加载时保持当前可隐藏部分的打开状态?

输入的值的类型脚本array.排序()

通过跳过某些元素的对象进行映射

我怎样才能得到一个数组的名字在另一个数组?

Angel Auth Guard-用户只有在未登录时才能访问登录页面,只有在登录时才能访问其他页面

使用Library chart.js在一个带有两个y轴的图表中绘制两个数据集

使用props 将VUE 3组件导入JS文件

将匿名函数附加到链接的onClick属性

JS/css:将数字输入的S函数和可调整大小的元素S函数绑定在一起

如何从图表中映射一组图表-js使用REACT

元素类型无效:应为字符串(对于内置组件)或类/函数(对于复合组件),但GET:Object.在Reaction项目中

我正在用JS编码一个链表,而我编写的一个Prepreend函数并没有按照我的预期工作

如何 Select 名称正在更改的DOM元素