---
title: 'Extended Binary Tree'
disqus: hackmd
---
[TOC]
## Extended Binary Tree - 延伸二元樹
* 在一般的 Binary Tree 中 Leaf 的 Link 為 Null，而我們將指向 Null 改成指向一種 Node 稱做：
1. 紅色 Node：External Node ( Failure Node ) 外部節點 (失敗節點)
3. 藍色 Node：內部節點 (Internal Node)
* 另一版本定義 External Node = Leaf，Internal Node = Non-Leaf
```graphviz
graph graphname{
1 [label="1" color=blue]
2 [label="2" color=blue]
3 [label="3" color=blue]
4 [label="4" shape=s style=dashed color=red]
5 [label="5" shape=s style=dashed color=red]
6 [label="6" shape=s style=dashed color=red]
7 [label="7" shape=s style=dashed color=red]
1--2
1--3
2--4 [style=dashed]
2--5 [style=dashed]
3--6 [style=dashed]
3--7 [style=dashed]
}
```
* 在 Binary Tree 中有談到 N 個 Nodes 則擁有 N+1 條的 Link 指向 Null
同理，此時我們將會有 N+1 個 External Node = 3+1 = 4
```graphviz
graph graphname{
1 [label="1"]
2 [label="2"]
3 [label="3"]
4 [label="4" shape=s style=dashed]
5 [label="5" shape=s style=dashed]
6 [label="6" shape=s style=dashed]
7 [label="7" shape=s style=dashed]
1--2
1--3
2--4 [style=dashed color=red]
2--5 [style=dashed color=red]
3--6 [style=dashed color=red]
3--7 [style=dashed color=red]
}
```
---
### 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
```graphviz
graph graphname{
1 [label="1"]
2 [label="2"]
3 [label="3"]
4 [label="4"]
5 [label="5" shape=s style=dashed]
6 [label="6" shape=s style=dashed]
7 [label="7" shape=s style=dashed]
8 [label="8" shape=s style=dashed]
9 [label="9" shape=s style=dashed]
1--2 [color=blue]
1--3 [color=blue]
2--4 [color=blue]
2--5 [style=dashed ]
3--6 [style=dashed ]
3--7 [style=dashed ]
4--8 [style=dashed ]
4--9 [style=dashed ]
}
```
---
### 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
```graphviz
graph graphname{
1 [label="1"]
2 [label="2"]
3 [label="3"]
4 [label="4"]
5 [label="5" shape=s style=dashed]
6 [label="6" shape=s style=dashed]
7 [label="7" shape=s style=dashed]
8 [label="8" shape=s style=dashed]
9 [label="9" shape=s style=dashed]
1--2 [color=red]
1--3 [color=red]
2--4 [color=red]
2--5 [style=dashed color=red]
3--6 [style=dashed color=red]
3--7 [style=dashed color=red]
4--8 [style=dashed color=red]
4--9 [style=dashed color=red]
}
```
---
### 定理：E = I + 2N
* 外部長 $=$ 內部長 $+\ 2\ *$ 內部節點
:::success
Proof：數學歸納法
:::
---
### Skewed Extended Binary Tree
* 公式：內部路徑長 = 0 + 1 + 2 + ... + (n-1) = $\dfrac{n(n-1)}{2}$
* 根據 E = I + 2N = $\dfrac{n(n-1)}{2}+2n=\dfrac{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 = $\dfrac{1}{n+1}$ $\left(\begin{array}{ccc}2n \\n\\\end{array}\right)$
* 若題目給 n 個 External Node 則只有 n-1 個 Internal Node
公式為：$\dfrac{1}{n}$ $\left(\begin{array}{ccc}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. 直到集合值剩下一個
<br><br>
* 例：一加權集合 { $2, 3, 5, 7, 9, 11$ }，取出 2 , 3
```graphviz
graph graphname{
2[shape=s style=dashed]
3[shape=s style=dashed]
}
```
* 2 + 3 = 5 ，將相加後的值繪成內部節點
```graphviz
graph graphname{
2[shape=s style=dashed]
3[shape=s style=dashed]
5--2
5--3
}
```
* 刪除 2 , 3 將 5 放入集合 { $5 , 5, 7, 9, 11$ }
```graphviz
graph graphname{
2[shape=s style=dashed]
3[shape=s style=dashed]
5--2
5--3
}
```
* 取出 5 , 5 (第一個 5 的樹繼續使用，與新的 5 合併)
```graphviz
graph graphname{
0[label="5" shape=s style=dashed]
2[shape=s style=dashed]
3[shape=s style=dashed]
5--2
5--3
}
```
* 5 + 5 = 10 ，將 10 繪成內部節點，刪除 5 , 5 將 10 放入集合 { $10, 7, 9, 11$ }
```graphviz
graph graphname{
0[label="5" shape=s style=dashed]
2[shape=s style=dashed]
3[shape=s style=dashed]
5--2
5--3
10--0
10--5
}
```
* 取出 7 , 9 相加、並刪除 7 , 9 將 16 放入集合 { $10, 16, 11$ }
```graphviz
graph graphname{
7[label="7" shape=s style=dashed]
9[label="9" shape=s style=dashed]
16--7
16--9
}
```
* 取出 10 , 11 相加、並刪除 10 , 11 將 21 放入集合 { $16, 21$ }
```graphviz
graph graphname{
0[label="5" shape=s style=dashed]
2[shape=s style=dashed]
3[shape=s style=dashed]
11[label="11" shape=s style=dashed]
5--2
5--3
10--0
10--5
21--10
21--11
}
```
* 最後兩元素 { $16, 21$ } 取出相加即完成
* 最佳 WEPL：$2*11 + 3*5 + 4*2 + 4*3 + 2*7 + 2*9=89$
```graphviz
graph graphname{
0[label="5" shape=s style=dashed]
2[shape=s style=dashed]
3[shape=s style=dashed]
11[label="11" shape=s style=dashed]
7[label="7" shape=s style=dashed]
9[label="9" shape=s style=dashed]
5--2
5--3
10--0
10--5
21--10
21--11
16--7
16--9
37--16
37--21
}
```
:::warning
**Time Complexity：**
使用 Min-Heap 維持加權值，插入 = 刪除 = n(log~2~n)
總共 n-1 回合 -> **n(nlog~2~n)**
:::
---
## 應用
* N 個回合最佳合併方式 (Merge Sort)
* N 個 Messages 編碼/解碼 之最佳方法
1. 為訊息
2. 依照個字母出現的次數依序給出他的權重，或也可以將次數改成頻率
* 編碼方式：建立完 Tree 後將 Left Child 填上 0，Right Child 填上 1
* 此種方式為 Optimal Prefix Code，是 Unique 的
###### tags: `Data Structure`
Sign in with Wallet
Connect another wallet