例外をチェックした後にプログラムが例外をスローする

Question

私は何かが紛失しているはずです非常にこれは私の心を吹いているので簡単です！

私は、配列を使用して実装されたCompleteBinaryTreeを使用してヒープを実装しようとしています。このCompleteBinaryTreeはPosition<T>の配列であり、各Positionに要素が格納されています。私は、tがCompleteBinaryTreeの次の空き位置に挿入され、CompleteBinaryTreeが注文されるまでアップヒーププロセスが実行されるヒープのadd(T t)メソッドを記述しています。

private CompleteBinaryTree<T> tree = new CompleteBinaryTree<T>(); 
    private Position<T> entry = null; 

    public void add(T t) { 
     entry = tree.add(t); 

     if (entry.equals(tree.root())) { 
      return; 
     } 

     //continue to swap inserted element with its parent 
     //while it is smaller than its parent 
     while (entry.element().compareTo(tree.parent(entry).element()) < 0) { 
      Position<T> parent = tree.parent(entry); 
      Position<T> temp = entry; 
      entry = parent; 
      parent = temp; 
     } 
    } 

最初の要素はヒープに細かい追加されますが、私は2番目の要素を追加しようとすると、InvalidPositionExceptionはwhile()ラインでスローされます。ここでは方法があります。これはexeptionはCompleteBinaryTreeクラスの内部からスローされている場合：

public Position<T> parent(Position<T> p) { 
     if (p == root()) throw new InvalidPositionException(); 

     return array[((ArrayPosition) p).index/2]; 
    } 

そして、ここではCompleteBinaryTreeから使用される二つの他の方法です：

public Position<T> root() { 
     if (isEmpty()) throw new InvalidPositionException(); 
     return array[1]; 
    } 

    public Position<T> add(T t) { 
     if (last == array.length) { 
      // extend array 
      ArrayPosition[] temp = (ArrayPosition[]) new Object[array.length*2]; 
      for (int i=1; i < array.length; i++) { 
       temp[i] = array[i]; 
      } 
      array = temp; 
     } 

     array[last] = new ArrayPosition(last, t); 
     return array[last++]; 
    } 

私は、 p == root()ので、スローされた例外を取得していますどのように

私はまず、pが根であるかどうかをチェックします。

EDITここ

は、ヒープtoString()によって返されCompleteBinaryTree toString()、次のとおりです。

public String toString() { 
    StringBuffer buf = new StringBuffer(); 

    for (int i = 1; i < last; i++) { 
     buf.append(" ").append(array[i]); 
    } 

    return buf.toString();  
} 

Answer 1

どのように私は、（）のp ==ルートので、スローされた例外を取得しています私はまず、pが根であるかどうかをチェックします。

しかし、あなたはないチェックにそれがルートであるかどうかを確認するためにあらゆるtree.parent()議論を行います。そのメソッドの最初の呼び出しに渡された引数だけをチェックします。 whileループの本体が実行されるたびに、entryが新しい値に設定され、ループが繰り返されると、チェックされていない新しい値がtree.parent()に渡されます。実際には、entryの新しい値のそれぞれは、ツリー全体を子から親に、すなわちルートに向かって上に移動することになるので、前のものよりも根に近い。このプロシージャがルートに到達することがあり、ツリー内にすでに存在する要素が少なくなる可能性があります。これを解決する

一つの方法は、while状態にルートをチェック移動するために、次のようになります。その場合

while (!entry.equals(tree.root()) 
     && entry.element().compareTo(tree.parent(entry).element()) < 0) { 
    // ... 
} 

、もちろん、あなたが外で実行する現在の1回限りのチェックは必要ありません。ループ。