證明哈夫曼編碼是最優的



====================

引理1：給定W = {w1, w2, w3...,wn} (n >= 2), 以此集合建構相應的哈夫曼樹。

令wi, wj 是W中權重最小的兩個元素。則這兩個數相應的結點是兄弟結點，且這兩結點在二叉樹中的深度不小于其他不論什麼一個葉結點的深度。

證明：由哈夫曼樹的建構過程可知，wi, wj 所在結點是兄弟結點（在不影響閱讀的前提下。以wi, wj 指代這兩個結點）。

如果在哈夫曼樹中，wi, wj 所在結點的深度不是最深的。則哈夫曼樹應似圖1 樣式，存在一些結點，其深度大于wi, wj 的深度。在圖1中。wi, wj的父結點V的權重應大于結點X權重。否則建構哈夫曼樹時，應選擇V而不是X作為U的子結點。但這是不可能的，由于由如果知wi, wj是W中權重最小的兩個元素。得出沖突，問題得證。

圖1 一棵可能的哈夫曼樹。在此樹中，對于最小權重的的兩個葉結點wi,wj, 其深度是不同的。圖中三角形表示子樹。

定理1：哈夫曼樹是最優的。

證明：用歸納法證明。

• 基本情況: 當 n=2 時, 哈夫曼樹具有最小權重外部路徑（EPW），由于樹 僅有二種可能，有二個葉結點的二種哈夫曼樹下的EPW是同樣的。
• 如果: 設有哈夫曼樹有 n−1 個葉子時，定理成立。

• 推導: 令T為有n （n>=2）個葉子的哈夫曼樹。不失 一般性，設 w1 <= w2 <=... <=wn。令V 是w1 與w2的父結點。由引理1知, 在

  T中，不存在葉結點，其深度大于葉結點w1 與w2的深度。若存在深度大于w1, w2深度的結點。我們能夠通過将之與w1, w2交換，由此得到更小的WPL。按例如以下方式得到到二叉樹T'：以結點V'替換結點V, 當中V'的權重是w1+w2，則T'是對應于{w1+w2,w3,...,wn}的一棵哈夫曼樹。依據歸納如果。T'具有最小權重外部路徑，T是最優的（EPW最小）。在T'的結點V'上加入葉結點w1, w2。可得

  T。則T是具有最小權重外部路徑的哈夫曼樹。

  由此，我們由數學照片納法證明了定理1. 

  （注意：哈夫曼編碼是最優之中的一個。）