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

[[389315]]

基本的な紹介

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

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

いくつかの重要な概念

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

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

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

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

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