Trie前缀树

Trie前缀树

什么是Trie?

又被称为：多叉树、字典；通常用来处理字符串

问：同样是遍历为什么时间复杂度只和要查找的字符长度有关；

​ 是一棵上面挂着很多单词子树的树？

查询的时间复杂度与一共有多少条无关，与查找的字符串的长度有关；

class 	Node{
    boolean isWord;//标志是不是，不用存c
	Map<char,Node> next;//
}

添加操作：

查找存在：

前缀搜索

Trie的局限性

• 最大的问题：空间！

• 因为trie中每个node中只储存一个字符，26个字母就要26个Node，孩子太多

• 结局办法：压缩字典树–合并、三分搜索树TST

Others：

• leetcode第208题实现一个trie树
• leetcode第211题添加与搜索单词
• leetcode第677题 包含某个单词前缀的value的和

更多字符串问题

• 后缀树–字符串模式识别（了解）

• 字串查询Ctrl+F

• 文件压缩

• 编译原理

• DNA