tire树
结构
Trie树，即字典树，又称单词查找树或键树，是一种多叉树结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。如下图：
好比假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词,那我们创建trie树就得到
上图可以归纳出Trie树的本质
- 根节点不包含字符,出根节点外的每一个子节点都包含一个字符
- 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串连接起来,为该节点的字符串
- 每个节点的所有子节点包含的字符互不相同
- 若实现前缀树时用的是hash数组，如vector<Node*> child; Node : child(26);则每个节点的子节点都是按字典序的，如上图根节点的孩子a->b->e->h。（这种前缀树就是字典树，可以用于按字典序输出树种的字符串。优点：可以按字典树输出字符串。缺点：占用空间大）
若实现前缀树时用的是标准库hashmap：unordered_map<char, Node*> child，则每个节点的子节点不是按字典序的（优点：占用空间小。缺点：不能按字典树输出字符串），如下图：
通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。
可以看出tire树的关键字一般都是字符串,而且trie树把每个关键字保存在一条路径上,而不是一个节点中.另外俩个有公共前缀的关键字,在trie树中前缀部分的路径相同,所以Tire树又叫做前缀树
前缀树是一种快速检索的多叉树,核心思想是空间换时间,经常被搜索引擎用于文本词频的统计
优缺点
优点
存储和查询都很高效,都为O(m),其中m是带插入字符串的长度.常用于
- 想前缀树中插入字符串word
- 查询前缀串prefiix是否为已经插入到前缀树中的任意一个字符串word的前缀
- trie 树中不同的关键字不会产生冲突
- Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生
- tire树不用求hash值,对端字符串有更快的速度,通常,求hash值也是要遍历字符串的(java的hash是直接存在对象头上的)
- Tire树可以对关键字按字典序排序(需要用hash数组实现)
缺点
- 当hash函数很好时,trie树的查找效率会低于hash搜索
- 空间消耗比较大
前缀树的应用
字符串检索
检索/查询功能是trie树最原始的功能,给定一组字符串,查找某个字符串是否出现过
思路就是从根节点开始一个一个字符进行比较
如果沿路比较,发现不同的字符,则表示字符在集合中不存在
如果所有的字符全部比较完并且完全相同,还需判断最后一个节点的标志位(标记该节点是否代表一个关键字)
词频统计
Trie树常被搜索引擎系统用于文本词频统计 。
思路： 用整型变量 count 来计数。对每一个关键字执行插入操作，若已存在，计数加1，若不存在，插入后 count 置1。
字符串排序
Trie 树可以对大量字符串按字典序进行排序，思路也很简单：遍历一次所有关键字，将它们全部插入 Trie 树，树的每个结点所有子节点很显然地按照字母表排序，然后先序遍历输出 Trie 树中所有关键字即可。
前缀匹配
例如：找出一个字符串集合中所有以 ab 开头的字符串。我们只需要用所有字符串构造一个 Trie 树，然后输出以 a->b-> 开头的路径上的关键字即可。
Trie 树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。