前缀树
前缀树 是 N 叉树 的一种特殊形式。通常来说，一个前缀树是用来 存储字符串 的。前缀树的每一个节点代表一个 字符串（前缀）。每一个节点会有多个子节点，通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的 原始字符串，以及 通往该子节点路径上所有的字符 组成的。
下面是前缀树的一个例子：
在上图示例中，我们在节点中标记的值是该节点对应表示的字符串。例如，我们从根节点开始，选择第二条路径 'b'，然后选择它的第一个子节点 'a'，接下来继续选择子节点 'd'，我们最终会到达叶节点 "bad"。节点的值是由从根节点开始，与其经过的路径中的字符按顺序形成的。
值得注意的是，根节点表示 空字符串。
前缀树的一个重要的特性是，节点所有的后代都与该节点相关的字符串有着共同的前缀。这就是 前缀树 名称的由来。
我们再来看这个例子。例如，以节点 "b" 为根的子树中的节点表示的字符串，都具有共同的前缀 "b"。反之亦然，具有公共前缀 "b" 的字符串，全部位于以 "b" 为根的子树中，并且具有不同前缀的字符串来自不同的分支。
前缀树有着广泛的应用，例如自动补全，拼写检查等等。我们将在后面的章节中介绍实际应用场景。
Trie Tree（字典树/前缀树/单词查找树/键树），是一种树形结构，是一种哈希树的变种。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：最大限度地減少无谓的字符串比较，查询效率比哈希表高。
基本性质
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符（便于插入和查找）
- 从根节点到某一节点，路径是经过的字符连接起来，为该节点对应的字符串
- 每个节点的所有自节点包含的字符都不相同。