#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 相比较，
列出 优缺点。
此文章仅为个人学习留下点足迹，若有错误欢迎批评指教。