简介
trie树（字典树），又称单词查找树，是一种树形结构，哈希树的变种。
trie 以字符为索引建树，因此，查找时间不带 \(log\) ，而是由字符串长度决定。
满trie树（原创图）。
但这张图不足以说明 trie 是如何存字符串的，因此有了下面一段。
trie 是如何存字符串的
下面这张图说明了 trie 是如何存字符串的，其中，\(\color{red}\textbf{☆}\) 表示从树顶走到某个位置的唯一路径上的所有节点表示了一个字符串。(原创图)
trie 的用处
- 可以当 \(map\) 用，更快。
- 统计以 \(str\) 为前缀的字符串的数量。