再帰的挿入時にバイナリ検索ツリーが再構築されますか？

Question

bstの通常の再帰コードでは、ツリーの左と右の要素はすべての再帰呼び出し（In t.left =とt.right =）で設定されます。 これはツリーを再構築していませんか？

以前のノードへの参照を保存してから、値に応じて新しいノードを左または右に追加したり、ここに何か不足していませんか？ありがとう！

 public Elem insert (Elem t, int toInsert) 
     { 
     if (t == null) 
      return new Elem(toInsert,null,null); 
     else { 
      if (toInsert < t.value) 
      t.left = insert(t.left, toInsert); 
      else 
      t.right = insert(t.right,toInsert); 
      return t; 
     } 
    } 

新しい要素を1つ挿入すると、コードはすべての要素またはサブツリーを左右に割り当てます。私の質問は、これがオーバーヘッドではないということですか？リンクされたリストに挿入するには、最後のノードに移動してリンクを実行するだけです。ここでは、各挿入時にツリー全体のリンケージを実行します。これを避けるための選択肢はありますか？

Answer 1

これは、ツリーを再構成するのではなく、ツリー内の葉（ヌルスポット）に到達するための再帰呼び出しでツリー内を移動し、そこに新しい要素を追加できるようにします。例えば、（3を横断しながら、私たちがどこにいる*は意味）、

6 
/\ 
    4 8 

このBSTを考慮し、あなたがinsert(element 6, 5)と呼ばれるとしましょう。

*6 
/\ 
    4 8 

方法は、最初にif文をスキップし、方法PARAMTERにおける現在の要素に関連し5の値をチェックするために進むことになります。 5が6よりも小さいので、次の行が実行されます。t.left = insert(t.left, toInsert)（これをelem6.left = insert（要素4,5）とみなします）。

6 
/\ 
*4 8 

今、私たちはinsertの第二のメソッド呼び出し、この時間insert(element 4, 5)にしています。最初のif文がもう一度スキップされ、4が5と比較されます。5が4より大きいので、次の行が実行されます。t.right = insert(t.right,toInsert)（これをelem4.right = insert（null、5）とみなします）。

6 
/\ 
    4 8 
    \ 
    * 

は、今、私たちは、最初のif文が実際に実行されると型Elemの新しいオブジェクトが返されるように、この時点insert(null, 5)が呼び出され、「挿入」の第三のメソッド呼び出しにしています。別名、この行が実行されます、return new Elem(toInsert,null,null)（これを返すnew Elem（5、null、null）と考えてください）。

6 
/\ 
    4 8 
    \ 
    * 

この時点で、呼び出しスタックは3回の呼び出しに達した後に減少し始めます。この行に戻ると、t.right = insert(t.right,toInsert)ではなく、insert(t.right, toInsert)の代わりに、new Elem(5, null, null)になりました。要素5は要素4の右側に割り当てられます。その後、残りのメソッドが実行され、return tで終了します。この場合、tはそれがだから今要素の左要素4だ、素子4

6 
/\ 
*4 8 
    \ 
    5 

戻るこのラインに

（コールスタックを下る）、t.left = insert(t.left, toInsert)代わりのinsert(t.left, toInsert)、方法を通過Elemです次に、残りのメソッドが実行され、return tで終了します。この場合のtは、メソッド6要素6を渡したElemです。要素5の挿入が完了しました。

*6 
/\ 
    4 8 
    \ 
    5