• Extended Binary Tree - 延伸二元樹
  • Internal Path Length - 內部路徑長
  • External Path Length - 外部路徑長
  • 定理：E = I + 2N
  • Skewed Extended Binary Tree
• Weighted External Path Length (WEPL) - 加權外部路徑長
  • Minimum Weighted External Path Length (MWEPL) - 最小加權外部路徑長
• Huffman Algo. - 霍夫曼編碼
• 應用

Extended Binary Tree - 延伸二元樹

• 在一般的 Binary Tree 中 Leaf 的 Link 為 Null，而我們將指向 Null 改成指向一種 Node 稱做：

  1. 紅色 Node：External Node ( Failure Node ) 外部節點 (失敗節點)

  2. 藍色 Node：內部節點 (Internal Node)

     • 另一版本定義 External Node = Leaf，Internal Node = Non-Leaf

• 在 Binary Tree 中有談到 N 個 Nodes 則擁有 N+1 條的 Link 指向 Null
  同理，此時我們將會有 N+1 個 External Node = 3+1 = 4

---

Internal Path Length - 內部路徑長

• Root 到最後一個 Internal Node 的長度，每個 Node 都需要計算一次

• 藍線部分：

  • Node 1->2 = 1
  • Node 1->3 = 1
  • Node 1->4 = 2
  • Internal Path Length = 1 + 1 + 2 = 4

---

External Path Length - 外部路徑長

• Root 到 External Node 的長度，每個 Node 都需要計算一次並取最長的 Path Length

• 紅線部分：

  • Node 1->8 = 3
  • Node 1->9 = 3
  • Node 1->5 = 2
  • Node 1->6 = 2
  • Node 1->7 = 2
  • External Path Length = 3 + 3 + 2 + 2 + 2 = 12

---

定理：E = I + 2N

• 外部長
  $=$ 內部長
  $+2\ast$ 內部節點

Proof：數學歸納法

---

Skewed Extended Binary Tree

• 公式：內部路徑長 = 0 + 1 + 2 + … + (n-1) =
  ${\displaystyle \frac{n(n-1)}{2}}$
• 根據 E = I + 2N =
  ${\displaystyle \frac{n(n-1)}{2}}+2n={\displaystyle \frac{n(n+3)}{2}}$

---

Weighted External Path Length (WEPL) - 加權外部路徑長

• 將各 External Path Length * 相對應的 External Node 之加權值即可
• 當有加權值存在，高度愈小 WEPL 不一定愈小

---

Minimum Weighted External Path Length (MWEPL) - 最小加權外部路徑長

• n 個 nodes 的 BT 中尋找哪一顆樹具有最小值

  • 根據 Binary Tree 定義，n 個 Nodes ( 相當於 Internal Node )

    之相異結構 BT =

    ${\displaystyle \frac{1}{n+1}}$
    $\left(\begin{array}{c}2n\\ n\end{array}\right)$

• 若題目給 n 個 External Node 則只有 n-1 個 Internal Node

  公式為：

  ${\displaystyle \frac{1}{n}}$
  $\left(\begin{array}{c}2(n-1)\\ n-1\end{array}\right)$

• 求出最佳(小)的 WEPL 方法：

  1. 暴力法
  2. Huffman Algo.
  3. Dynamic Programming

---

Huffman Algo. - 霍夫曼編碼

• 依照加權值畫成 Huffman Tree ，步驟如下

  1. 將加權值設於一集合中
  2. 依序將最小的兩值取出
  3. 將兩值相加之值取代原本兩值並放進集合
  4. 重複 2. 3. 直到集合值剩下一個
     
     
     

• 例：一加權集合 {

  $2,3,5,7,9,11$ }，取出 2 , 3

• 2 + 3 = 5 ，將相加後的值繪成內部節點

• 刪除 2 , 3 將 5 放入集合 {
  $5,5,7,9,11$ }

• 取出 5 , 5 (第一個 5 的樹繼續使用，與新的 5 合併)

• 5 + 5 = 10 ，將 10 繪成內部節點，刪除 5 , 5 將 10 放入集合 {
  $10,7,9,11$ }

• 取出 7 , 9 相加、並刪除 7 , 9 將 16 放入集合 {
  $10,16,11$ }

• 取出 10 , 11 相加、並刪除 10 , 11 將 21 放入集合 {
  $16,21$ }

• 最後兩元素 {
  $16,21$ } 取出相加即完成
• 最佳 WEPL：
  $2\ast 11+3\ast 5+4\ast 2+4\ast 3+2\ast 7+2\ast 9=89$

Time Complexity：
使用 Min-Heap 維持加權值，插入 = 刪除 = n(log₂n)
總共 n-1 回合 -> n(nlog₂n)

---

應用

• N 個回合最佳合併方式 (Merge Sort)
• N 個 Messages 編碼/解碼 之最佳方法
  1. 為訊息
  2. 依照個字母出現的次數依序給出他的權重，或也可以將次數改成頻率
  • 編碼方式：建立完 Tree 後將 Left Child 填上 0，Right Child 填上 1

• 此種方式為 Optimal Prefix Code，是 Unique 的

tags: Data Structure