### 建構方法

#### Ternary Huffman code

用 ${0, 1, 2}$ 來編 codeword，首先檢查要編碼的 letter 個數
- if letter 個數: even
> 第一次挑 probability 最小的兩個 letter 來 merge
- if letter 個數: odd
> 第一次挑三個 probability 最小的 letter 來 merge

接著每次都次挑三個來 merge
> $\therefore$ 一棵 Ternary Huffman tree 中最多只會出現一個 internal node 具 2 children

*編出來的 code 對應的 code tree 為 ternary tree

### 特性
#### Optimal variable length code 的條件
1. 如果有兩個 letter a, b，a 出現的機率比 b 高，則 a 的 code length 比 b 小（用比較短的 code 來編比較常出現的字）
2. 最不常出現的兩個 letter，其 code length 相同（同為 maximal code length）
3. opt code 對應的 tree 中，所有 internal node 都有兩個點
4.
\begin{multline*}\sum_{\forall i : \text{ external node}} 2 ^ {−𝑙_𝑖} = 1 \qquad \text{where $𝑙_𝑖$: external node i 的 length} \end{multline*}

>可參考下方「判斷是否為 Huffman Code 」的題目

---
- Huffman Code 不一定唯一
> 如果有具相同 probability 的 element，根據 merge 的順序不同，會得到不同的 code tree，因此編出來的 Code 也不同

- Huffman Tree 非 BST，node 大小不需按照順序
> 因為 Huffman Coding 的重點在於 compression，而不是 search

### 判斷是否為 Huffman Code


### CLRS 題目


---

### Reference
[NYCU Lecture Notes](https://people.cs.nycu.edu.tw/~cjtsai/courses/imc/classnotes/imc14_03_Huffman_Codes.pdf)
[Balanced Ternary Huffman encoding](https://hackaday.io/project/164907-ternary-computing-menagerie/log/170171-balanced-ternary-huffman-encoding)