Trie ，又可稱為字典樹、前綴樹 (Prefix Tree)
Trie 結構特性
- hash tree 的變種，常用在搜尋系統中
- 空間換取時間，利用字串的共同前綴詞 (commen prefix) 作為儲存依據，以字母作為結點，降低查詢時間的開銷以達到提高效率之目的。
- 樹的高度為最長字串長 + 1
- 時間複雜度為 O(m), m 為欲插入/搜尋的字串長度
優點 ：
- 大幅減少無謂的字串比對，查詢效率比 hash map 高
- 容易撰寫
- 查詢是否存在 & 前綴相關具有非常好的效果
缺點：
- 十分消耗記憶體空間，因為需要存取與前綴相關的指標，因此大部分使用情況會占用大量空指標
Hash vs Trie
| Compare | Hash | Trie |
|---|---|---|
| 時間複雜度 | O(1)~O(n) | O(n) |
| 空間複雜度 | 優 | 劣 |
| 性質 | 只能找尋完整字符 | 除完整字符，也可找尋StarWith 前綴字符 |
若使 Hash 得以搜尋每個前綴字符，空間複雜度將比 Trie 來得低 (Trie還必須存取前綴相連的指標)。
References
https://medium.com/@derekfan/九章算法-template-trie-tree-字典樹-132e19c6c827