ハフマンツリーについて混乱しています。上記のリンクの終わり近くに、2つの要素が残っているツリーと、完成したツリーが表示されます。私はそれが分岐する方法について混乱しています。ハフマンツリーを分岐する必要がある特定の方法はありますか？
たとえば、57：*とその右の子35：*は、右に分岐しています。左に35分岐し、右に22分岐したのでしょうか。また、22：*が15：4とペアになっていないのはなぜですか？20：5とペアになっているだけで、新しいツリーが作成されます。
最初の観察から、ツリーのバランスをとる必要はなく、リーフの頻度が親ノードの値に加算される以外の特定の順序を持つ必要はないようです。同じデータでハフマンツリーを作成する2人が、異なるエンコーディング値で終わる可能性はありますか？
これまでの投稿は間違っていて誤解を招く可能性があります。同じ重みを持つ葉の選択は重要であり、データの圧縮率が変わります。
さまざまな選択がさまざまな圧縮率にどのようにつながるかを示す反例を次に示します。ABBBCCCDDDDEEEEEEEEE
A：1、B：3、C：3、D：4、E：8。最初のステップ：AとBを取り、重み4のノードを形成します。2番目のステップ：
Cを使用して最初のステップで新しく作成されたノードを取得
(19 (11 (7 (4 (1-A) (3-B)) (3-C)) (4-D)) (8-E))すると、37ビットの圧縮データが得られます。
一方、新しく作成されたノードの代わりに、重みが4のDを使用すると、
(19 (11 (4 (1-A) (3-B)) (7 (3-C) (4-D))) (8-E))41ビットの圧縮データが得られます。
ハフマンの木の鍵はこれです：
このリストを頻度で並べ替えて、最も低い2つの要素を葉にします
頻度が最も低い要素が3つ以上ある場合（たとえば、3,4,4 ...）、任意の2つで問題ありません（3つと4のいずれか-2つの4ではありません）。また、これらの最も低い要素のどちらに0が割り当てられ、どちらが1であるかは重要ではありません。これらの2つの事実により、同じデータから異なるが有効なハフマンエンコーディングを生成できます。
ハフマンツリーは、ノードの数ではなく、周波数によってバランスが取れていると想定されています。したがって、以下はバランスが取れています。
(100 (50 (25 (12 (12 1)))))
これはそうではありません：
(((100 50) 25) ((12 12) 1)))
特にあなたの質問では、15と20が残りの2つの最も低い値（両方とも22未満）であるため、15は22ではなく20とペアになっています。一貫性がある限り、分岐（左または右）のどちらでも問題ありません（同じアルゴリズム内で常に左が小さい、または右が小さいので、もう一方の端でエンコーディングを再構築できます）。
すべてがページで説明されています。22：*は15：4とペアになりませんでした。これは、各ステップで、要素が最も低い2つのノードが結合されるためです。これにより、一意の順序が作成されます。
ハフマンコードは異なる場合がありますが（同じ頻度で複数の値がある場合、または左/右の0と1の表現を交換する場合）、ハフマンの長さを変えることはできません。
左/右への分岐は、ツリーの描画方法またはグラフィカルな表現方法の問題であるため、これは重要ではありません。