OutOfMemoryError：Javaヒープスペースアレイバイナリ検索ツリーにソートされた要素を追加する

Question

OutOfMemoryError：ソートされた要素の配列をバイナリ検索ツリーの配列の実装に追加するJavaヒープスペースを取得しました。ランダムなIntegerの配列を追加することはできますが、ソートされた配列を追加しようとするとこの問題が発生します。ツリーのルートは、ソートされた配列の最小または最大の要素に設定されているので、残りの要素を追加すると、私の記憶を食べる極端に不均衡なツリーができます。これに関する助けは大いに感謝しています。あなたは、このようなAVLや赤黒木として、あなたのツリーに均衡しているいけない場合

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at bst.ArrayBinarySearchTree.resize(ArrayBinarySearchTree.java:386) at bst.ArrayBinarySearchTree.addElement(ArrayBinarySearchTree.java:26) at bst.Experiment.main(Experiment.java:90)

public void addElement(T element) { 
    if(isEmpty()){ 
    count++; 
    array[1] = element; 
    }else{ 

     int current = 1; 
     boolean added = false; 

     while (!added) { 
      if(current > (array.length-(array.length*.9))){ 
        resize(); 
       } 
      if (element.compareTo(array[current]) < 0){ 
       if (array[current*2] == null) { 
        array[current*2]=element; 
        added = true; 
       } else 
        current = current*2; 
      } else{ 
       if (array[current*2+1] == null) { 
        array[current*2+1]=element; 
        added = true; 
       } else 
        current = current*2+1; 
      } 
     } //while 
    } 
    count++; 
} 

    private void resize(){ 
    T[] temp = (T[])(new Comparable[2*array.length-(array.length/4)]); 
    for(int i=0; i<array.length; i++) 
     temp[i] = array[i]; 
    array = temp; 
} 

Answer 1

だけでなく、あなたはアンバランスなツリーを取得します。バランシングせずにバイナリ検索ツリーを構築するだけの場合は、メモリ不足例外が発生する可能性があります。

まだメモリ不足の例外が発生しているかどうかを確認するには、小さいアレイで試すことをお勧めします。はいの場合、コードに欠陥があります。

私はbinary search tree in c#を持っています。それを見てください。通常、バイナリ検索ツリーを表すために配列を使用する代わりに、ノードを使いたいとします。私の知る限り、通常heap data structureのheap sortに使用されているテクニックを使用しています。