二進制搜索樹和AVL樹問題

我正在爲二進制搜索樹和AVL樹進行分配。

我有問題，當我嘗試1000000個元素添加到二叉搜索樹，但我能值對添加鍵 - >到AVL樹。（沒有與AVLTree沒問題）
二進制搜索樹和AVL樹問題

如果我平衡二叉搜索樹，與AVL樹沒有什麼區別？（如果我平衡二叉搜索樹，它變成AVLTree有什麼意義？）

我在插入15,000個元素後從二進制搜索樹中收到錯誤：線程「主要「java.lang.StackOverflowError

項目定義：
使用這些測試和爲樸素二元搜索樹創建的代碼，比較 AVL樹和樸素二元搜索樹的性能，搜索，插入和刪除的時間爲，並在長序列上對樹平衡進行比較。你應該在你的樹上運行多達1000000個元素的測試。

public class BinaryTreeExample { 

    public static void main(String[] args) { 
     new BinaryTreeExample().run(); 
    } 

    static class Node 

    { 

     Node left; 
     Node right; 
     int value; 

     public Node(int value) { 
      this.value = value; 
     } 
    } 

    public void run() { 
     Node rootnode = new Node(25); 

     insert3(rootnode, 50_000); 

     for (int i = 0; i < 150_000; i++) 
      insert3(rootnode, i); 
     System.out.println("Bittaaa"); 
     // System.out.println(getNodesCount(rootnode)); 

    } 

    protected int getNodesCount(Node root) { 

     if (root != null) { 
      int counter = 1; 
      counter += getNodesCount(root.left); 
      counter += getNodesCount(root.right); 
      return counter; 
     } else 
      return 0; 

    } 

    void insert3(Node node, int value) { 
     if (value < node.value) { 
      if (node.left == null) 
       node.left = new Node(value); 
      else 
       insert3(node.left, value); 
     } else { 
      if (node.right == null) 
       node.right = new Node(value); 
      else 
       insert3(node.right, value); 
     } 
    } 


    public void printInOrder(Node node) { 
     if (node != null) { 
      printInOrder(node.left); 
      System.out.println(" Traversed " + node.value); 
      printInOrder(node.right); 
     } 
    } 
}

來源

2014-01-15 Ertuğrul Çetin

你需要在這裏提供一些代碼。 –

這與你剛剛問過的這個問題非常相似（http://stackoverflow.com/questions/21139851/cant-add-1-000-000-elements-to-binary-search-tree-in-java），除了更多的困惑。那裏的答案和評論確實解決了這個問題的很大一部分。 – Dukeling

你在那裏的插入功能根本就不是迭代的。 [這是一個迭代插入函數]（http://stackoverflow.com/a/8384366/1711796）（它是C＃，但我非常肯定代碼看起來相同，除了預期的名稱更改，在這種情況下）。 – Dukeling

StackOverflowError來自您實現insert遞歸的事實。在這種情況下，如果你添加元素1,2,3,....,15000你的樹會有水平15000，你的遞歸會溢出你的堆棧。執行它的命令，你不會得到StackOverflowError。它應該是類似於

void insert (Node node, int value) { 
    while (true) { 
     if (value < node.value) { 
      if (node.left == null){ 
       node.left = new Node(value); 
       break; 
      } 
      else 
       node = node.left; 
     } 
     else { 
      if (node.right == null){ 
       node.right = new Node(value); 
       break; 
      } 
      else 
       node = node.right; 
     } 
    } 
}

但是整個方法並不是最優的。上面的行爲不是您期望從BST獲得的行爲。你想有水平log(15000)而不是15000。你將通過使用平衡結構來實現這一點。它仍然是BST樹，但額外的限制是水平爲O（log n）。所以一旦你完成了BST，肯定試試AVL :)

來源

2014-01-15 16:31:25

我改變了插入方法類型遞歸迭代，但問題仍然存在 –

你可以發佈你的迭代'插入'？ –

二進制搜索樹和AVL樹問題

回答

相關問題