前言

今天介紹的是二元搜尋樹的一種，Huffman tree。

對於一棵Binary tree，我們可以定義其 內部路徑長 和 外部路徑長。

• 內部路徑長 Internal path length : Root到每個 Internal node 的path長度的加總。
• 外部路徑長 External path length : Root到每個 Leaf 的path長度的加總。

如果我們給Leaf賦予一個加權值(Weight):

• 外部加權路徑長 WE : Root到每個 Leaf 的path的長度乘上Weight的加總。

霍夫曼樹 Huffman tree

WE最小的Binary tree。

Huffman 演算法

• 建立Huffman tree例子:
  假設有A、B、C、D四個Leaf，其加權分別為15、8、35、26。

1. 將Leaf的加權值由小到大排序加入串列:
   B/8 、 A/15 、 D/26 、 C/35

2. 取加權最小的兩個subtree(8和15)形成新subtree(23)，並把新subtree加進串列
   

3. 新串列: E/23 、 D/26 、 C/35
   取加權最小的兩個subtree(23和26)形成新subtree(49)，並把新subtree加進串列
   

4. 新串列: C/35 、 F/49
   取加權最小的兩個subtree(35和49)形成新subtree(84)，並把新subtree加進串列
   

5. 新串列: G/84
   因為串列元素只剩下一個，所以Huffman tree已經建立完成。
   

• Huffman Tree 常被用在資料處理的壓縮和編碼。
  如果有一篇文章希望用二進制數字來編碼，就只用0和1來表示整篇文章，而且希望編碼能越短越好
  那我們使用Huffman Tree來表示的話，Leaf就是要編碼的字，而Leaf的加權就是字在文章出現的次數。

  • 每個節點往左子樹的path標記0，而往右子樹的path標記1。
  • 從Root到每個Leaf所經過的路徑就是每個Leaf的編碼。
  • 以上面例子來說明:
    
  • 從圖就可以看出:

  A 的編碼	101
  B 的編碼	100
  C 的編碼	0
  D 的編碼	11

  • 出現頻率越高的字編碼會越短，因為加權最大，在建構Huffman tree的時候，會最晚被選取，在樹的Level也會越小。