質問: new BinarySearchTree(); System.out.println(bst); System.out.println("50,31,81,15,41,62,92,3,28,33,53,74,85を順に追加:"); bst.add(50); System.out.println(bst); bst.add(31); System.out.println(bst); bst.add(81); System.out.println(bst); bst.add(15); System.out.println(bst); bst.add(41); System.out.println(bst); bst.add(62); System.out.println(bst); bst.add(92); System.out.println(bst); bst.add(3); System.out.println(bst); bst.add(28); System.out.println(bst); bst.add(33); System.out.println(bst); bst.add(53); System.out.println(bst); bst.add(74); System.out.println(bst); bst.add(85); System.out.println(bst); //追加課題部分テスト:探索アルゴリズム System.out.println("3の探索結果:" + bst.search(3)); //探索成功 System.out.println("11の探索結果:" + bst.search(11)); //探索失敗 //追加課題部分テスト:削除アルゴリズム bst.delete(3); //(a)の場合 System.out.println(bst); /* bst.delete(5); //(b)の場合 System.out.println(bst); bst.delete(81); //(c)の場合 System.out.println(bst); bst.delete(91); //削除するkeyが存在しない場合 */ } } ``` mainメソッド`bst.delete(3);`の実行結果 ![画像の説明をここに入力](https://i.stack.imgur.com/bOFxb.png)
回答: 木構造データで、「節点が削除される」というのは、その木のどの節点から辿っても到達できなくなるという事です。 ``` X +-+-+ | | L R ``` 簡単な例で考えましょう。 図は、Xは根(root)で二つの子(LとR)を持つ節点、LとRは葉という木です。 プログラムでは、この木が3つの節点(Nodeクラスのオブジェクト)X,L,Rから構成されて、以下のような参照関係を持ちます。 ``` X.left = L '左の子 X.right = R '右の子 L.left = null '葉なので子が無い L.right = null '葉なので子が無い R.left = null '葉なので子が無い R.right = null '葉なので子が無い ``` この木からRを削除するには、Rにnullを代入するのではなく、Xの右の子(X.right)をnullにします。 そうすることで、Xは右の子を持たない節点になりますから、Rが削除された事になるのです。 p.s. X.right=null としても、Rという節点が残っているように思われるかもしれません。 実際、計算機のメモリ上には一時的に残るのですが、どこからも参照されないメモリ領域はゴミ(garbage)という印が付けられ、後に再利用されます。