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

[[390860]]

バイナリソートツリーで起こりうる問題

シーケンス {1,2,3,4,5,6} が与えられた場合、バイナリソートツリー (BST) を作成し、問題を分析する必要があります。

問題分析:

左のサブツリーはすべて空で、形式的には単一のリンクリストのように見えます。
挿入速度は影響しません。
クエリ速度が大幅に低下し (1 回の比較が必要になるため)、BST の利点を活かすことができません。左のサブツリーを毎回比較する必要があるため、クエリ速度は単一のリンクリストよりも遅くなります。
ソリューション - バランスバイナリツリー (ALV)

基本的な紹介

バランスのとれたバイナリツリーは、自己バランスバイナリサーチツリー (AVL ツリーとも呼ばれます) とも呼ばれ、高いクエリ効率を保証できます。
空の木であるか、左右のサブツリー間の高さの差の絶対値が 1 を超えず、左右のサブツリーが両方ともバランスの取れた二分木であるという特徴があります。バランスのとれた二分木の一般的な実装方法には、赤黒木、AVL、スケープゴート木、Treap、ストレッチ木などがあります。
たとえば、下の図の最初の 2 つはバランスの取れた二分木です。最初の二分木は左右のサブツリー間の高さの差の絶対値が 1、2 番目の二分木は左右のサブツリー間の高さの差の絶対値が 0、3 番目の二分木は左右のサブツリー間の高さの差の絶対値が 2 なので、バランスの取れた二分木ではありません。

バランスのとれた二分木の左回転

ステップ：

現在のルートノードの値と同じ値を持つ新しいノード newNode を作成します。
新しいノードの左サブツリーを現在のノードの左サブツリーに設定します。
新しいノードの右サブツリーを、現在のノードの右サブツリーの左サブツリーに設定します。
現在のノードの値を現在の右の子ノードの値に置き換えます。
現在のノードの右サブツリーを右サブツリーの右サブツリーに設定します。
現在のノードの左のサブツリーを新しいノードに設定します。

バランスのとれた二分木の右回転

ステップ：

現在のルートノードの値と同じ値を持つ新しいノードを作成します。
新しいノードの右サブツリーを現在のノードの右サブツリーに設定します。
新しいノードの左サブツリーを、現在のノードの左サブツリーの右サブツリーに設定します。
現在のノードの値をその左の子の値と交換します。
現在のノードの左サブツリーを左サブツリーの左サブツリーに設定します。
現在のノードの右サブツリーを新しいノードに設定します。

バランスのとれた二分木の二重回転

場合によっては、1 回の回転ではバランスの取れたバイナリツリーの変換を完了できず、2 回の回転が必要になります。

右サブツリーの左サブツリーの高さが右サブツリーの右サブツリーの高さよりも大きい場合は、最初に右サブツリーを右に回転してから、現在のノードを左に回転する必要があります。
左サブツリーの右サブツリーの高さが左サブツリーの左サブツリーの高さより大きい場合、
まず左のサブツリーを左に回転し、次に現在のノードを右に回転する必要があります。

コード例

パッケージ com.xie.avl; 
 
パブリッククラス AVLTreeDemo {
公共 静的void main(String[] args) {
 int [] arr = {4, 3, 6, 5, 7, 8};
        AVLTree avlTree = 新しい AVLTree();
 ( int i = 0; i < arr.length; i++) {
            avlTree.add (新しいノード(arr[i]));
        }
        System.out.println ( "順序通りの走査" );
        avlTree.infixOrder();
        System.out.println ( "バランス処理前~~" );
        System.out.println ( "ツリーの高さ = " + avlTree.getRoot().height());
        System.out.println ( "ツリーの左サブツリーの高さ = " + avlTree.getRoot().leftHeight());
        System.out.println ( "ツリーの右サブツリーの高さ = " + avlTree.getRoot().rightHeight());
    }
 } 
 
クラス AVLTree {
    プライベートノードルート; 
 
パブリックノードgetRoot() {
ルートを返します。
    } 
 
パブリックvoid setRoot(ノード ルート) {
        ルート
    } 
 
    //削除するノードの親ノードを見つける
パブリックノード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 = 値;
    } 
 
    /**
     * 左サブツリーの高さを返します
     *
     * @戻る 
     */
公共  int左高さ() {
        if (左== null ) {
 0を返します。
        }
戻る 左.height();
    } 
 
    /**
     * 右サブツリーの高さを返します
     *
     * @戻る 
     */
公共  int右高さ() {
        this.rightがnullの場合
0を返します。
        }
戻る 右.height();
    } 
 
    /**
     * このノードをルートノードとするツリーの高さを返します
     *
     * @戻る 
     */
公共 整数高さ() {
 Math.max (this.left == null ? 0 : this.left .height(), this.right == null ? 0 : this.right .height()) + 1を返します。
    } 
 
    /**
     * 左に回転
     */
パブリックボイド左回転() {
        //現在のルートノードの値で新しいノードを作成します
        ノード newNode = 新しいノード(値);
        //新しいノードの左サブツリーを現在のノードの左サブツリーに設定します
        newNode.left =左;
        //新しい右サブツリーを現在のノードの右サブツリーの左サブツリーに設定します
        newNode.right = right.left ;
        //現在のノードの値を右の子ノードの値に置き換えます
        値 =右.value;
        //現在のノードの右サブツリーを、現在のノードの右の子の右サブツリーに設定します
右=右.右;
        //現在のノードの左の子ノード（左のサブツリー）を新しいノードに設定します
左= newNode;
    } 
 
    /**
     * 右に回転
     */
パブリックボイド右回転() {
        //現在のルートノードの値で新しいノードを作成します
        ノード newNode = 新しいノード(値);
        //新しいノードの右サブツリーを現在のノードの右サブツリーに設定します
        newNode.right =右;
        //新しいノードの左サブツリーを現在のノードの左サブツリーの右サブツリーに設定します
        newNode.left = left.right ;
        //現在のノードの値を左の子ノードの値に置き換えます
        値 =左.value;
        //現在のノードの左サブツリーを左サブツリーの左サブツリーに設定します
左=左.左;
        //現在のノードの右サブツリーを新しいノードに設定します
右= newNode;
    } 
 
    /**
     * 削除するノードの親ノードを見つける
     *
     * @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 (ノード) ;
            }
        } 
 
        //ノードを追加した後、(右サブツリーの高さ - 左サブツリーの高さ) > 1 の場合は左回転を実行します
        右の高さ() - 左の高さ() > 1 の場合 {
            // 右サブツリーの左サブツリーの高さが右サブツリーの右サブツリーの高さよりも大きい場合は、まず右サブツリーを右に回転してから、現在のノードを左に回転する必要があります。
            if( right != null && right .leftHeight() > right .rightHeight()){
右.rightRotate();
                左回転();
            }それ以外{
                //左に回転するだけ
                左回転();
            }
戻る;
        } 
 
        //ノードを追加した後、(左サブツリーの高さ - 右サブツリーの高さ) > 1 の場合は右回転を実行します
        （左の高さ（） - 右の高さ（） > 1）の場合{
            // 左サブツリーの右サブツリーの高さが左サブツリーの左サブツリーの高さよりも大きい場合は、まず左サブツリーを左に回転してから、現在のノードを右に回転する必要があります。
            if(左!= null &&左.rightHeight() >左.leftHeight()){
左.leftRotate();
                右回転();
            }それ以外{
                //右に回転するだけ
                右回転();
            } 
 
        }
    } 
 
    // 順序通りの走査
パブリックvoid infixOrder() {
        if ( this.left != null ) {
            this.left .infixOrder();
        }
        System.out.println (これ) ;
        if ( this.right != null ) {
            this.right .infixOrder();
        }
    } 
 
    @オーバーライド
パブリック文字列toString() {
戻る  「ノード{」 +
 "値=" + 値 +
 '}' ;
    }
 }