Extended Binary Tree

發表於 2021-01-31 Disqus：

文章字數： 2k 所需閱讀時間 ≈ 4 分鐘

具有 External Node 的 B.T. 稱之

一個二元樹具有 n 個節點，若以 Link List 表示，則會有 n+1 條空 Link，在這些空 Link 上加上特定節點，稱為 External Node (或 Failure Node)，其餘 Nodes 稱 Internal Nodes
外部節點數 = 內部節點數 + 1 ( 2n – (n - 1) = n + 1 )
為何外部節點又被稱為失敗節點？
- 以二元搜尋樹的角度來説，若搜尋到外部節點時，代表在原本的二元樹中找不到想要的資料，也就是搜尋失敗

Internal path Length (I) and Extended path Length (E)

\[ I = \sum_{i=1}^n Root 到內部節點 i 的路徑長度 \] \[ E = \sum_{i=1}^n Root 到外部節點 j 的路徑長度 \]

E = I + 2n ( n 為內部節點個數 )

範例 1： 一個具有 5 個 Internal Nodes 的 Extended B.T.，其 I 値與 E 値分別為?
Ans:
- I = 0 + 1 + 1 + 2 + 2 = 6
- E = 2 + 2 + 3 + 3 + 3 + 3 = 16 = I + 2n
範例 2： 一個具有 n 個 Internal Nodes 的 SkewedExtended B.T.，其 I 値與 E 値分別為?
Ans:
- I = 0+1+2+…+(n-1) =
- E = 1+2+3+…+2n=

Extended B.T. 若有 n 個內部節點，則會有 n + 1 個外部節點。分別給予毎一個外部節點 1 個加權値，則： \[ W.E.P.L. = \sum_{j=1}^{n+1} (Root 到外部節點 j 的路徑長度) \times (外部節點 j 的加權值) \]

給予 (n+1) 個外部節點加權値，在顆樹中，具有最小的 W.E.P.L. 稱之

( n+1 ) 個訊息傳輸，其平均解碼時間最小 (或：編碼位元長度最小)

令 W 為外部節點加權値的集合，Huffman Algo. 的執行歩驟如下：

有 6 個外部節點，其加權値分別為： 2, 3, 5, 7, 9, 13。求 Min. W.E.P.L.

有 6 個 Message 要傳輸，其出現頻率如下： \[ M_1 = \frac{2}{39}, M_2 = \frac{3}{39}, M_3 = \frac{5}{39}, M_4 = \frac{7}{39}, M_5 = \frac{9}{39}, M_6 = \frac{13}{39} \] 今希望平均解碼時間最小，則：

Ans:

Message：外部節點 出現頻率：加權値

解碼時間最短的 Encoding / Decoding Tree :
- 將出現頻率通分後，以分子當加權値建立 Huffman Tree
- Encoding / Decoding Tree (都是同一顆Tree):
  - 左分支： 0
  - 右分支： 1
各 Message 之編碼內容： (由 Root 開始走)
Message Decoding Time = Message Bit 數 = Root 到外部節點的路徑長度
經常出現的訊息，Bit 數要愈少；即路徑長度要愈短
平均最小編碼位元長度:
- \[ \sum {(編碼位元數) \times (出現頻率)} \] \[ 2 \times \frac{7}{39} + 2 \times \frac{9}{39} + 2 \times \frac{13}{39} + 3 \times \frac{5}{39} + 4 \times \frac{3}{39} + 4 \times \frac{2}{39} = \frac{93}{39} \approx 2.38 \]