二分木探索の実装の削除メソッドについて

Question

二分木探索の実装の削除メソッドでわからないところがあります。
こちらの実装についてです。
http://d.hatena.ne.jp/g940425/20101211/1292088124

以下に示しますコードは二分木探索の実装です。

public class BinarySearchTree<T> {
    public int key;
    public T value;
    public BinarySearchTree<T> left;
    public BinarySearchTree<T> right;
    public BinarySearchTree<T> parent;

    //コンストラクタ：木を作成
    BinarySearchTree(){
        this.value = null;
        this.key = 0;
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    //コンストラクタ：ノードを作成
    BinarySearchTree(int key,T value,BinarySearchTree<T> p){
        this.value = value;
        this.key = key;
        this.left = null;
        this.right = null;
        this.parent = p;
    }

    //木に挿入
    public void insert(int key,T value){
        if(this.parent == null && this.value == null){
            //根が空の場合
            this.value = value;
            this.key = key;
            return;
        }else if(this.key > key){
            //左に挿入
            if(this.left == null){
                //左に子がない
                this.left = new BinarySearchTree<T>(key,value,this);
            }else {
                //左に部分木あり
                this.left.insert(key,value);
            }
        }else if(this.key < key){
            //右に挿入
            if(this.right == null){
                //右に子がない
                this.right = new BinarySearchTree<T>(key,value,this);
            }else {
                //右に部分木あり
                this.right.insert(key,value);
            }
        }else{
            //既存のキーの場合：上書きする
            this.value = value;
        }
        return;
    }

    //キーを指定して検索
    public BinarySearchTree<T> search(int key){
        if(this.key == key && this.value != null)return this;
        if(this.key > key && this.left != null)return this.left.search(key);
        if(this.key < key && this.right != null)return this.right.search(key);
        return null;
    }

    //最小の値を削除
//木から切り取るだけなので、この関数から返ったノードへのアドレスを呼び出し側で受けることで削除したノードへのアクセスが可能
//なお、削除操作での使用を想定しているため、削除ノードが根だった場合を考慮していない
    public BinarySearchTree<T> extractMin(){
        if(this.left == null){
            //左に子を持たない場合：これが最小ノードなので、削除
            if(this.right == null){
                //孤立した（子がない）場合：削除ノードを切り離す
                if(this.parent.left == this){
                    this.parent.left = null;
                }else {
                    this.parent.right = null;
                }
            }else{
                //右に子を持つ場合：このノードの代わりに右の子を親の子とする
                if(this.parent.left == this){
                    this.parent.left = this.right;
                }else {
                    this.parent.right = this.right;
                }
                this.right.parent = this.parent;
            }
            return this;
        }else{
            //左に子を持つ場合：左の部分木の最小ノードを取り除く
            return this.left.extractMin();
        }
    }

メソッドextractMin()についてなのですが、

if(this.parent.left == this){
                    this.parent.left = null;
                }else {
                    this.parent.right = null;

の部分でelseとあるのですが、このelseがどういう状況なのかイメージできません。
このメソッドでは根の削除は考慮していません。
また、一番左にあるノードに到達した時に、

(!this.parent.left == this)

という条件が成り立つのでしょうか？
ここで詰まっています。
わかる方、ご助力ください。

Answer 1

以下でやろうとしているのは、親から自分へのリンク切り離す作業です。
自分を削除することは決定しています。

２分木なので、自分は、自分の親にとって左の子か、右の子か、どちらでしかありえません。
親の左の子＝＝自分ならば、親の左の子はないものとする。
それいがいなら親の右の子はないものとする。（＝親の左の子が自分じゃないなら、自分は親の右の子のはずだから）

if(this.parent.left == this){
    this.parent.left = null;
}else {
    this.parent.right = null;
}

また、一番左にあるノードに到達した時に、(!this.parent.left == this)という条件が成り立つのでしょうか？

細かいですけど(this.parent.left != this)こうか(!(this.parent.left == this))ですね。

この最小を削除する段階において、自分が親にとって右の子であった場合、
自分が最小でないことが確定して矛盾するのでないと思います。
elseブロック側も同じですかね。

Comments

[退会済みユーザー]

回答ありがとうございます。
そうすると、以下のコードの方が良いのですかね？
if(this.left == null){
//左に子を持たない場合：これが最小ノードなので、削除
if(this.right == null){
//孤立した（子がない）場合：削除ノードを切り離す
this.parent.left = null;
}else{
//右に子を持つ場合：このノードの代わりに右の子を親の子とする
this.parent.left = this.right;
this.right.parent = this.parent;
}
return this;
}else{
//左に子を持つ場合：左の部分木の最小ノードを取り除く
return this.left.extractMin();
この方が分かりやすくて、いいと思うのですが。

[flied_onion]

分かりやすさというのはいろんな見方があるのでそう一言では言えないです。

ここの（最小の削除）コードの最適化だけならそうかもしれませんが、パターンとして自ノードの切り離しだけを考えれば親ノードの双方と自分を比べれば他の条件での削除も似た形になって、同様の処理をしていることに気づきやすいメリットがあります（削除処理のメソッド化などにもつながる）。元のコードも「最小」という条件抜きで、切り離しや入れ替えのパターンをコードに書いただけじゃないですかね。

変更するなら、私なら矛盾する条件にはいったらthrowさせることを検討します。
自分の考えが間違っている可能性や他の部分コードが間違ってそこに入る可能性もあるので。
比較をなくすならコードコメントの修正はします。

[退会済みユーザー]

回答ありがとうございました。