54912


２分探索木のアルゴリズム実装課題で悩んでいます。  
追加、探索までは実装でき、テストもokだったのですが、削除だけうまくいきません。  
実装したい削除メソッドの構造は、

  * (a),(b),(c)で場合分けして削除する  
(a)削除するkeyの節点が葉  
(b)削除するkeyの節点が１つのみ子を持つ  
(c)削除するkeyの節点が２つの子を持つ

  * 探索メソッドと同様削除する値を探索し、探索が失敗した場合エラーメッセージ

場合分けしたところまでは良いものの、実際に値を削除する方法がわかりません  
削除したいノード=nullをしても値は削除されません

[code]

    public class BinarySearchTree {
        private Node root = null; // 根
    
        private class Node {
            private int key; // key
            private Node left; // 左の子
            private Node right; // 右の子
    
            private Node(int key) {
                this.key = key;
                left = null;
                right = null;
            }
    
            public String toString() {
                return String.format("<%s(%d)%s>", (left == null ? "/" :
                    left), key, (right == null ? "/" : right));
            }
        }
    
        public void add(int x) {
            Node v = root; // 探索中のノードを指すカーソル
            Node p = null; // 探索中のノードの親を指すカーソル
            boolean isLeft = true; // ノードpの左の子を参照したならtrue, 右の子を参照したならfalse
            Node nn = new Node(x); // 新たに追加するkey値をもつノード
            while (v != null) { //葉に到達していないことを表す
                if (x < v.key) {
                    p = v;
                    isLeft = true;
                    v = v.left;
                }else{
                    p = v;
                    isLeft = false;
                    v = v.right;
                }
            }
            if (v == root) root = nn;
            else if (isLeft) p.left = nn;
            else p.right = nn;
        }
    
        //課題追加部分:探索アルゴリズム
        //探索が成功すれば真を、失敗すれば偽を返す
        public boolean search(int x){
            Node v = root; // 探索中のノードを指すカーソル
            boolean ret = false; //探索成功の可否の判定値
            while(v != null && !ret){ //１つ目の条件は葉に到達していないことを表す
                if(x<v.key) v = v.left; //keyが探索する値よりも大きい場合、左の子へ移動
                else if(x>v.key) v= v.right; //keyが探索する値よりも小さい場合、右の子へ移動
                else ret =true; //探索する値が見つかった時
            }
            return ret;
        }
    
        //質問部分！！！！
        //課題追加部分:削除アルゴリズム
        //削除するkeyの節点によって(a),(b),(c)で場合分けする
        public void delete(int x){
            Node v = root; 
            boolean ret = false; 
            while(v != null && !ret){ 
                if(x<v.key) v = v.left; 
                else if(x>v.key) v= v.right; 
                else {
                    ret = true;
                    if(v.left==null&&v.right==null){ //(a)削除するkeyの節点が葉
                        v = null;
                    }
                    else if(v.left==null||v.right==null){ //(b)削除するkeyの節点が１つのみ子を持つ
    
                    }
                    else{ //(c)削除するkeyの節点が２つの子を持つ
    
                    }
                }
            }
            if(ret) System.out.println( x + "を削除しました.");
            else System.out.println("削除したいkeyが見つかりません.");
        }
    
        public String toString() {
            return String.format("%s",(this.root==null ? "/" :this.root));
        }
    
        public static void main(String[] args) {
            // TODO 自動生成されたメソッド・スタブ
            BinarySearchTree bst = 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が存在しない場合
            */
        }
    
    }
    
[/code]

mainメソッド`bst.delete(3);`の実行結果

[![画像の説明をここに入力](https://i.stack.imgur.com/bOFxb.png)](https://i.stack.imgur.com/bOFxb.png)


CC BY-SA 4.0
2019-05-12T11:10:46.403
54910
2019-05-13T07:16:07.253
2019-05-13T07:16:07.253
3060
question
java アルゴリズム
2分探索木の削除アルゴリズム


木構造データで、「節点が削除される」というのは、その木のどの節点から辿っても到達できなくなるという事です。

[code]

       X
     +-+-+
     |   |
     L   R
    
[/code]

簡単な例で考えましょう。  
図は、Xは根(root)で二つの子(LとR)を持つ節点、LとRは葉という木です。

プログラムでは、この木が３つの節点(Nodeクラスのオブジェクト)X,L,Rから構成されて、以下のような参照関係を持ちます。

[code]

    X.left = L　'左の子
    X.right = R '右の子
    L.left = null  '葉なので子が無い
    L.right = null '葉なので子が無い
    R.left = null  '葉なので子が無い
    R.right = null '葉なので子が無い
    
[/code]

この木からRを削除するには、Rにnullを代入するのではなく、Xの右の子(X.right)をnullにします。  
そうすることで、Xは右の子を持たない節点になりますから、Rが削除された事になるのです。

p.s.  
X.right=null としても、Rという節点が残っているように思われるかもしれません。  
実際、計算機のメモリ上には一時的に残るのですが、どこからも参照されないメモリ領域はゴミ(garbage)という印が付けられ、後に再利用されます。


CC BY-SA 4.0
2019-05-12T12:50:12.860
54912
2019-05-12T12:50:12.860
217
54910
answer