Trie(字典树, 前缀树)

Trie(字典树, 前缀树)

Tire树:

又叫做字典树, 前缀树(prefixTree), 单词查找树或键树, 是一种多叉树结构

注意: Trie是一个多叉树

可以读作"try", 也可以读作"tree"

字典树的性质:

1. 根节点(root)不包含字符, 除根节点之外的每一个节点都包括一个字符

   • 根节点是作为一个虚拟节点存在的

     • 为什么我们要将根节点作为虚拟节点?(也就是为什么我们不在根节点中存储数据了)

       • 因为我们的树的根节点有一个, 而开始的时候第一层我们要存储的字母有26个, 所以我们只能是将头结点设置为虚拟结点, 然后从头结点的下一层开始存储字母

       • 小结: 很多时候如果我们第一层中就要求有多个数据时, 并且如果是要使用树结构来实现, 这个时候我们就要将头结点设置为虚拟头结点, 从头结点的下一层开始存储数据

2. 从根节点到某一个节点路径上所经过的字符连接起来, 即为该结点对应的字符串

3. 任意节点的所有子节点所包含的字符都不相同

trie树的使用场景:

1. 搜索引擎的自动补全
   • 当我们输入前几个字母之后, 就会匹配很多对应的前缀单词, 这个功能就是使用trie树实现的
2. IP路由的最长前缀匹配
3. 拼写检查
4. 打字预测(输入法)

对于词频统计等, 我们之前使用Map完成, 我们将单词存储到key中, 单词出现的次数存储到value中, 但是对于词频统计, 其实我们也可以使用trie树来解决, 并且trie树存储时还节省空间, 因为trie树来完成词频统计时如果我们的某个单词的前缀是我们的另一个单词, 这个时候我们的另一个单词和这个单词就只用存储一次, 只用存储一个长的就可以了, 这个长单词的一部分前缀就是短单词

• 我们使用trie树完成词频统计时只需要在isword属性为true的结点中使用count值就可以统计词频
  • isword就是trie树中的一个引用, 这个引入为true时就是表示这个节点所表示的字符串是一个单词
  • count也是trie树中的一个引用, 用于统计这个节点所表示的字符串的个数

Trie树练习题: 208, 211, 212

Bitwise Trie : 一种特殊的Trie树

• Bitwise Trie树中每个node都有只有两个分支, 存储的是0或者是1
  • 也就是Bitwise Trie是一个二叉树

Bitwise Trie相当于对值进行了一个编码, 在对于做异或等类似算法中常常使用(在比较两个值的编码的相同于不同点的时候常使用)

Bitwise Trie树练习题: 421