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

[[389315]]

基本的な紹介

n 個のリーフ ノードとして n 個の重みが与えられ、バイナリ ツリーを構築します。ツリーの重み付きパス長 (wpl) が最小化される場合、そのようなバイナリ ツリーは最適バイナリ ツリーと呼ばれ、ハフマン ツリー (Huffman Tree) とも呼ばれ、一部の書籍ではハフマン ツリーと翻訳されています。

ハフマン ツリーは、重み付けされたパスの長さが最も短いツリーであり、重みが大きいノードはルートに近くなります。

いくつかの重要な概念

1. **パスとパスの長さ: **ツリーでは、ノードから到達できる子ノードまたは孫ノード間のパスをパスと呼びます。パス内の分岐の数をパスの長さと呼びます。ルート ノードのレイヤー数を 1 に設定した場合、ルート ノードから L レイヤー ノードまでのパスの長さは L-1 になります。
2. **ノードの重みと重み付きパスの長さ: **ツリー内のノードに何らかの意味を持つ数値が割り当てられている場合、この数値はノードの重みと呼ばれます。ノードの重み付きパス長は、ルート ノードからノードまでのパス長とノードの重みの積です。
3. ツリーの重み付きパス長: ツリーの重み付きパス長は、すべてのリーフ ノードの重み付きパス長の合計、つまり WPL (重み付きパス長) として定義されます。重みが大きいノードがルート ノードに近いバイナリ ツリーが最適なバイナリ ツリーです。
4. 最小のWPLはハフマン木である

wpl=59はハフマン木である

ハフマンツリー作成のアイデア

シーケンス{13,7,8,3,29,6,1}が与えられた場合、それをハフマン木に変換する必要がある。

1. 小さいものから大きいものへとソートし、各データをノードと見なし、各ノードは最も単純なバイナリ ツリーと見なすことができます。
2. ルートノードの重みが最も小さい 2 つのバイナリ ツリーを取り出します。
3. 新しい二分木が形成され、新しい二分木のルート ノードの重みは、前の 2 つの二分木のルート ノードの重みの合計になります。
4. 次に、この新しいバイナリ ツリーをルート ノードの重みでソートし、シーケンス内のすべてのデータが処理されてハフマン ツリーが得られるまで、手順 1-2-3-4 を繰り返します。次の図に示すように:

コード例

パッケージ com.xie.huffmantree; 
 
 java.util.ArrayList をインポートします。
 java.util.Collections をインポートします。
 java.util.List をインポートします。 
 
パブリッククラスHuffmanTree {
公共 静的void main(String[] args) {
 int [] arr = {13, 7, 8, 3, 29, 6, 1};
        ノード huffmanTree = createHuffmanTree(arr);
        // 事前順序トラバーサル
        ハフマンツリーを事前注文します。
        /**
         * ノード{値=67}
         * ノード{値=29}
         * ノード{値=38}
         * ノード{値=15}
         * ノード{値=7}
         * ノード{値=8}
         * ノード{値=23}
         * ノード{値=10}
         * ノード{値=4}
         * ノード{値=1}
         * ノード{値=3}
         * ノード{値=6}
         * ノード{値=13}
         */
    } 
 
    //ハフマン木を作成する
公共 静的ノードcreateHuffmanTree( int []arr){
        //最初のステップは操作を容易にすることです
        //1. arr配列を走査する
        //2. arrの各要素はノードを形成する
        //3. ノードをArrayListに入れる
        リスト<Node> nodes = 新しい ArrayList<>();
 for ( int値: arr ) {
            nodes.add (新しいノード(値));
        } 
 
        ノードサイズ() > 1の場合{
            // 小さい順から大きい順に並べ替える
            コレクション.sort(ノード);
            システム.out.println ( "ノード = " + ノード); 
 
            // ルートノードの重みが最小の2つのバイナリツリーを取り出します
            //(1) 重みが最小のノードを取り出す（二分木）
            ノード leftNode = nodes.get(0);
            //(2) 2番目に小さい重みを持つノードを取り出す（二分木）
            ノード rightNode = nodes.get(1); 
 
            //(3) 新しいバイナリツリーを構築する
            ノード親 = 新しいノード(leftNode.value + rightNode.value);
            親.left = leftNode ;
            親ノードの rightNode をダブルクリックします。 
 
            //(4) ArrayListから処理済みのバイナリツリーを削除する
            ノードを削除します(左ノード)。
            ノードを削除します。(右ノード) 
 
            //(5) ノードに親を追加する
            nodes.add (親);
        } 
 
        //ハフマン木のルートノードを返す
nodes.get(0)を返します。 
 
    } 
 
公共 静的void preOrder(Node ノード) {
        if (ノード ​​!= null ) {
            ノードを事前注文します。
        }それ以外{
            System.out.println ( "空のツリーなので、走査できません~~" );
        } 
 
    }
 } 
 
 //ノードクラスを作成します。Nodeオブジェクトがソートをサポートするようにするには、Comparableインターフェースを実装します。
クラスNodeはComparable<Node>を実装します。
    //重さ
int値;
    //左の子ノードを指す
    ノード左;
    //右の子ノードを指す
    ノード右; 
 
    // 事前順序トラバーサルを記述する
パブリックボイドpreOrder() {
        System.out.println (これ) ;
        if ( this.left != null ) {
            this.left.preOrder ();
        } 
 
        if (this.roght != null ) {
            this.roght.preOrder();
        }
    } 
 
パブリックノード( int値){
        this.value = 値;
    } 
 
    @オーバーライド
パブリック文字列toString() {
戻る  「ノード{」 +
 "値=" + 値 +
 '}' ;
    } 
 
    @オーバーライド
公共  int compareTo(ノードo) {
        // 小さい順から大きい順に並べ替える
this.value - o.valueを返します。
    }
 }

【編集者のおすすめ】

1. 妹に Java 16 の新機能について話しましたが、とても素晴らしいそうです!
2. IT プロジェクトが多すぎて管理が難しくなっていませんか?いいえ！あなたはまだこの7つのコツを学んでいないからです
3. Pythonを5年間学んできましたが、これらのウェブサイトをもっと早く知らなかったことを後悔しています。ぜひ一緒に見に来てください。
4. Java はすでに 16 まで達しているのに、なぜまだ 8 が使われているのでしょうか? どんどん悪化しているのでしょうか?
5. すごいですね！ Windows 10 のこれらのブラックテクノロジー機能を使用したことがありますか?