Java プログラミングスキル - データ構造とアルゴリズム「バイナリソートツリー」

[[390181]]

基本的な紹介

バイナリソート (検索) ツリー: バイナリソートツリー内のリーフ以外のノードの場合、左のノードの値は現在のノードの値よりも小さく、右のノードの値は現在のノードの値よりも大きくする必要があります。

**特記事項: **同一の値がある場合、ノードは左の子ノードまたは右の子ノードに配置できます。

たとえば、データ {7,3,10,12,5,1,9} の場合、対応するバイナリソートツリーは次のようになります。

バイナリソートツリーのノードを削除する

バイナリソートツリーの削除はより複雑です。次の図に示すように、考慮すべき状況が 3 つあります。

1. リーフノードを削除します（例：2、5、9、12）

最初に削除するノード targetNode を見つける必要があります
targetNode の親ノード parentNode を検索します (親ノードが存在するかどうかを考慮します)
targetNode が parentNode の左の子か右の子かを判断する
前の対応する削除によれば、左の子ノード => parent.left = null、右の子ノード => parent.right = null;

2. サブツリーが1つだけのノードを削除します（例：1）

最初に削除するノード targetNode を見つける必要があります
targetNode の親ノード parentNode を検索します (親ノードが存在するかどうかを考慮します)
ターゲットノードの子が左の子か右の子かを判断する
targetNode が parentNode の左の子か右の子かを判断する
targetNode が parentNode の左の子である場合:

targetNode の子ノードが左の子ノードである場合、parentNode.left = targetNode.left となります。targetNode の子ノードが右の子ノードである場合、parentNode.left = targetNode.right となります。
targetNode が parentNode の右の子である場合: targetNode の子が左の子である場合、parentNode.right = targetNode.left targetNode の子が右の子である場合、parentNode.right = targetNode.right

3. 2つのサブツリーを持つノードを削除します（例：7、3、10）

最初に削除するノード targetNode を見つける必要があります
targetNode の親ノード parentNode を検索します (親ノードが存在するかどうかを考慮します)
targetNode の右サブツリーから最小のノードを見つけ、一時変数を使用して右サブツリーの最小ノードの値を temp に保存し、右サブツリーの最小ノードを削除します。その後、targetNode.value = temp; を実行し、左サブツリーから見つけた場合は、左サブツリーの最大値を置き換えます。

コード例:

パッケージ com.xie.bst; 
 
パブリッククラスBinarySortTreeDemo {
公共 静的void main(String[] args) {
 int [] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        バイナリソートツリーを新規作成します。
 ( int i : arr )の場合{
            バイナリソートツリーに追加(新しいノード(i)) ;
        }
        System.out.println ( "バイナリソートツリーの順序付きトラバーサル~" );
        バイナリソートツリーの順序を固定します。 
 
        System.out.println ( "リーフノードの削除をテストする" ) ;
        バイナリソートツリー.delNode(10);
        System.out.println ( "ノードを削除した後" ) ;
        バイナリソートツリーの順序を固定します。
    }
 } 
 
クラス BinarySortTree {
    プライベートノードルート; 
 
    //削除するノードの親ノードを見つける
パブリックノードsearchParent(ノードノード) {
        ルートがnullの場合
root.searchParent(ノード)を返します。
        }それ以外{
戻る ヌル;
        }
    } 
 
    // 削除するノードを見つける
パブリックノード検索( int値){
        ルートがnullの場合
戻る ヌル;
        }それ以外{
 root.search(値)を返します。
        }
    } 
 
    /**
     * ノードをルートとする二分ソート木の最小値を見つけ、ノードをルートノードとする二分ソート木の最小ノードを削除します。
     *
     * @param node 入力ノード（バイナリソートツリーのルートノードとして）
     * @returnルートノードとしてノードを持つバイナリソートツリーの最小ノード値を返します
     */
公共  int delRightTreeMin(ノードノード) {
        ノードターゲット = ノード;
        //左のノードを見つけるためにループする
        while ( target.left != null ) {
            ターゲット = target.left ;
        }
        //最小のノードを削除
        delNode(ターゲット値);
ターゲット値を返します。
    } 
 
    /**
     * ノードをルートとする二分ソート木の最大値を見つけ、ノードをルートノードとする二分ソート木の最大ノードを削除します。
     *
     * @param node 入力ノード（バイナリソートツリーのルートノードとして）
     * @returnルートノードとしてノードを持つバイナリソートツリーの最大ノード値を返します
     */
公共  int delLeftTreeMax(ノードノード) {
        ノードターゲット = ノード;
        while ( target.right != null ) {
            ターゲット = target.right ;
        } 
 
        // 最大のノードを削除する
        delNode(ターゲット値);
ターゲット値を返します。
    } 
 
    //ノードを削除する
パブリックvoid delNode( int値) {
        ルートがnullの場合
戻る;
        }それ以外{
            ノード targetNode = search(値);
            ターゲットノードがnullの場合
戻る;
            }
            ターゲットノード == ルートの場合 {
                ルート = null ;
戻る;
            }
            ノード parentNode = searchParent(targetNode); 
 
            targetNode.left == nullかつ targetNode.right == nullの場合{
                //削除するノードがリーフノードの場合
                （親ノードの左がnull で、親ノードの左が targetNode の値の場合）{
                    親ノード.left = null ;
                }
                （親ノードの右がnull != nullかつ親ノードの右がtargetNode の値 == の場合）{
                    親ノード.right = null ;
                }
            }それ以外の場合( targetNode.left ! = null && targetNode.right ! = null ) {
                //削除するノードが2つのサブツリーを持つノードの場合
int minValue = delRightTreeMin ( targetNode.right );
                ターゲットノードの値 = minValue;
                // 上位コードと下位コードを削除しても効果は同じです
                // int maxValue = delLeftTreeMax ( targetNode.left );
                //targetNode.value = maxValue;
            }それ以外{
                //削除するノードには左の子ノードのみがあります
                （ targetNode.left != null ）の場合{
                    親ノードがnullの場合
                        親ノードの左辺がターゲットノードの場合
                            親ノードの左=ターゲットノードの左 ;
                        }それ以外{
                            親ノードの右=ターゲットノードの左 ;
                        }
                    }それ以外{
                        //親ノードが空の場合は、ルートの位置を変更します
                        ルート= targetNode.left ;
                    }
                } else {//削除するノードには右の子ノードのみがある
                    親ノードがnullの場合
                        親ノードの左辺がターゲットノードの場合
                            親ノードの左=ターゲットノードの右;
                        }それ以外{
                            親ノードの右=ターゲットノードの右;
                        }
                    }それ以外{
                        //親ノードが空の場合は、ルートの位置を変更します
                        ルート = targetNode.right ;
                    } 
 
                }
            }
        }
    } 
 
    //ノードを追加
パブリックvoid add (Node ノード) {
        ルートがnullの場合
            ルート = ノード;
        }それ以外{
            root.add (ノード);
        }
    } 
 
    // 順序通りの走査
パブリックvoid infixOrder() {
        ルートがnullの場合
            ルートの順序を固定します。
        }それ以外{
            System.out.println ( "バイナリソートが空なので走査できません" );
        }
    } 
 
 } 
 
クラスノード{
 int値;
    ノード左;
    ノード右; 
 
パブリックノード( int値){
        this.value = 値;
    } 
 
    /**
     * 削除するノードの親ノードを見つける
     *
     * @param node 削除するノード
     * @return削除するノードの親ノード
     */
パブリックノードsearchParent(ノードノード) {
        //現在のノードが削除するノードの親ノードである場合は、
        if (( this.left != null && this.left .value == node.value) ||
                ( this.right != null && this.right .value == node.value)) {
これを返します。
        }それ以外{
            if ( this.left != null && node.value < this.value) {
                //検索対象のノードの値が現在のノードの値より小さい場合は、左のサブツリーを再帰的に検索します
this.left.searchParent (ノード)を返します。
            }そうでない場合 (this.right ! = null && value >= this.value) {
                //検索対象のノードの値が現在のノードの値より小さい場合は、左のサブツリーを再帰的に検索します
this.right.searchParent (ノード)を返します。
            }それ以外{
戻る ヌル;
            }
        }
    } 
 
    /**
     * 削除するノードを見つける
     *
     * @param value 削除するノードの値
     * @return削除されたノード
     */
パブリックノード検索( int値){
        if (値 == this.value) {
これを返します。
        }それ以外の場合 (値 < this.value) {
            if ( this.left != null ) {
 this.left.search (値)を返します。
            }それ以外{
戻る ヌル;
            }
        }それ以外{
            if ( this.right != null ) {
 this.right.search (値)を返します。
            }それ以外{
戻る ヌル;
            }
        }
    } 
 
    // バイナリソートツリーの要件を満たすためにノードを再帰的に追加します
パブリックvoid add (Node ノード) {
        if (ノード == null ) {
戻る;
        }
        （ノード値<this値）の場合{
            if ( this.left == null ) {
                this.left = ノード;
            }それ以外{
                // 左のサブツリーに再帰的に追加する
                this.left.add (ノード) ;
            }
        }それ以外{
            this.rightがnullの場合
                this.right = ノード;
            }それ以外{
                // 右の子ノードに再帰的に追加します
                this.right.add (ノード) ;
            }
        }
    } 
 
    // 順序通りの走査
パブリックvoid infixOrder() {
        if ( this.left != null ) {
            this.left .infixOrder();
        }
        System.out.println (これ) ;
        if ( this.right != null ) {
            this.right .infixOrder();
        }
    } 
 
    @オーバーライド
パブリック文字列toString() {
戻る  「ノード{」 +
 "値=" + 値 +
 '}' ;
    }
 }