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二叉搜索樹 - 插入實現

回答

相關問題