#include <自己的作業自己寫.h>
**Trie（字典樹）
在實作 Prefix-search 的時候，當然不能不提到 trie 這樣特別的樹狀資料結構。
以下為 trie 的簡介：
字典樹最大的特性為"利用單字的共同前綴（common prefix）作為儲存依據"，用來
減少佔用的記憶體與加快搜尋的效能。共同前綴說穿了就是數個單字"前面幾個相同的
字母"，像是 CUT 與 CUTE 就有 CUT 這個共同前綴。
舉例而言，若依序輸入 CAT、CUT、CUTE、TO、B 五筆資料，則會建立如下圖的字典樹。
https://i.imgur.com/quFVMHU.png (圖片來源自：https://goo.gl/vyvzAG)
而 Trie 建立的規則如下：
1. 所有 nodes 皆接在 root 這個不包含任何字母的節點底下。
2. 除了 root 以外，其他 nodes 皆代表一個字母。
3. 每個 node 最多可能有 26 個子節點(若universal set 為所有不分大小寫的字母)。
4. 每個 children 皆為字串可能的下一個字母，在上圖中，C 節點後有 A 與 U 兩
個可能的字母。
5. 整棵樹的高度為 "最長字串 + 1"
6. "並非"只有葉子代表一個字串的結尾，從 root 向下走訪的每個節點，皆可能是某
個字串的結尾。如上圖中的 CUT。
簡易實作步驟(以上面的字典樹為例)：
1. 一開始，建立一個 value = NULL 的節點 root;
2. 欲插入字串為 CAT，將 CAT 拆成 C、A、T;
3. root 沒有 value == C 的 children，建立一個 children，value = C;移動到 C;
4. 因 C 沒有 value == A 的 children，建立一個 children，value = A;移動到 A;
5. 因 A 沒有 value == T 的 children，建立一個 children，value = T;移動到 T;
6. 欲插入字串為 CUT，將 CUT 拆成 C、U、T;
7. 在 root 找到 children C，移動到 C;
8. 因 C 沒有 value == U 的 children，建立一個 children，value = U;移動到 U;
9. 因 U 沒有 value == T 的 children，建立一個 children，value = T;移動到 T;
.
.
.
優點：trie 的優點顯而易見，即是運作速度快且容易撰寫，針對搜尋目標字串是否存在
與前綴相關的議題有不錯的效果。
缺點：因為每個 node 皆可能有最大分支度的 child nodes 數，因此在 node struct 宣
告時必須宣告 N(最大分支度) 個指標。在多數情況下，這些指標不會被充份利用
，更可能有許多空指標，勢必造成巨大的記憶體成本。
TODO:改用 Ternary search tree (TST)以減少不必要的記憶體成本，與 trie 相比較，
列出 優缺點。
此文章僅為個人學習留下點足跡，若有錯誤歡迎批評指教。