数据结构：Trie Tree，字典树、前缀树
2017-12-03
0.概要
关于 Trie Tree，深究一下，实现原理等内容。
1.Trie Tree：字典树、前缀树
几个方面：
- 是什么？
- 有什么用？
- 如何构建 Trie Tree？新增、删除、查询等操作，在当前数据结构上，如何进行？
1.1.是什么？
Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。
上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。
从上图可以归纳出Trie树的基本性质：
- 根节点：根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
- 子节点：每个节点的所有子节点，包含的字符互不相同。
- 路径：从根节点到某一个节点，路径上经过的字符连起来，为该节点对应的字符串。
实际场景中，每个中间节点，会设置「一个标记」，用于标识当前节点是否构成一个单词（关键词）。
- 关键字，都存储在「路径」上，而没有存储再「节点」中。
- 前缀树：公共前缀相等的「关键字」在 Trie Tree 中，前缀部分对应路径相同，因此，Trie 树，又称为前缀树。
1.2.有什么用？
字典树，作为数据结构，有什么用？本质是：查询效率，或者说「时间复杂度」。
Trie树：
- 核心思想：
空间换时间 - 利用字符串的「公共前缀」，来减少无谓的字符串比较，以达到提高查询效率的目的。
优点：
- 插入和查询的效率很高，都为O(m)，其中 m 是待插入/查询的字符串的长度。
- 关于查询，会有人说 hash 表时间复杂度是O(1)O(1)不是更快？但是，哈希搜索的效率通常取决于 hash 函数的好坏，若一个坏的 hash 函数导致很多的冲突，效率并不一定比Trie树高。
- Trie树中，不同的关键字不会产生冲突。
- Trie树只有在允许一个关键字关联多个值的情况下，才有类似hash碰撞发生。
- Trie树不用求 hash 值，对短字符串有更快的速度。通常，求hash值也是需要遍历字符串的。
- Trie树可以对关键字，按字典序排序。
缺点：
- 当 hash 函数很好时，Trie树的查找效率会低于哈希搜索。
- 空间消耗比较大。
具体的应用场景：
- 字符串检索
- 词频统计
- 字符串排序：Trie 树，每层节点采用「字典序」存储
- 前缀匹配：例如网址自动提示
- 其他数据结构和算法的辅助结构：后缀树、AC自动机等
1.3.如何构建 Trie 树？
参考：
2.参考资料
原文地址：https://ningg.top/data-structure-series-01-trie-tree/