Java二叉搜索树 - 插入实现

我有这个问题，实现了二叉搜索树插入。现在我已经用递归方法和迭代来尝试它了。到目前为止，我得到的方式是“最好还好”，因为对于树大小= 31609和树高= 35，插入大约需要100秒，并且它应该在大约一秒钟内降低WAAAAAAY。有人可以给我一个暗示我可能做错了什么吗？Java二叉搜索树 - 插入实现

这里是什么，我已经设法到目前为止做的（无插入式两份），代码：

void insert(int val){ 
    if(this.elem < val){ 
     if(this.right != null){ 
      this.right.insert(val); 
     } 
     else{ 
      nodes++; 
      this.right = new Node(val); 
     } 
    } 
    else if(this.elem > val){ 
     if(this.left != null){ 
      this.left.insert(val); 
     } 
     else{ 
      nodes++; 
      this.left = new Node(val); 

     } 
    } 
    else { 
     return; 
    } 
}

来源

2015-05-13 drBet

我怀疑这个问题位于插入本身。你能提供关于构造函数的信息吗？ –

构造函数是非常基本的：private Node（int elem）{this.elem = elem;} – drBet

和'nodes ++'是什么意思？你在每个节点上存储树的大小吗？ –

如果您在使用插入线270定义的功能，很长一段时间实际上是可以解释的。

看这一段代码：

public void insert(int val) { 

     if (root == null) { 
      nodes++; 
      root = new Node(val); 
     } else if (!root.exists(val)) { 
      root.insert(val); 
     } 

    }

这个调用一个函数存在（），其被定义如下：

boolean exists(int val) { 
      return val == this.elem 
        || (val < this.elem ? (this.left != null && this.left.exists(val)) 
          : (this.right != null && this.right.exists(val))); 
     }

和你看到这一段代码，可以很容易弄清楚，也许每次你调用这个函数，你的代码都会递归地遍历整个树！所以如果你插入100K次，你的代码在最坏情况下运行在O（n^2 * logn）时间，所以100秒实际上是一个很好的运行时间！

我认为你所要做的就是修改你的exists（）函数。

来源

2015-05-18 15:15:59

Java二叉搜索树 - 插入实现

回答

相关问题