浅识Trie树或字典树

Trie这个单词来自‘retrieve’,Trie树又称字典树或键树。它是一种用于快速字符串检索的多叉树，原理是：利用字符串的公共前缀降低时空开销，空间换时间。Trie树的典型应用是统计和排序大量字符串，所以经常被搜索引擎用于文本词频统计。优点是：最大限度减少无谓字符串的比较，查询效率比hash表高。

Trie树的特性

• 根节点不包含字符，除根节点外，每个节点都包含且仅包含一个字符
• 从根节点到某一节点，路径上经过的字符串连接起来，是该节点对应的字符串

• 每个节点的所有子节点包含的字符都不相同

  
  Snip20181018_4.png
  

  如图所示，该Trie树用10个节点保存了5个字符串：amy, aan, em, rob, rg。
  在该Trie树中，字符串“amy”和“ann”有公共前缀“a”，如果系统中存在大量且这些字符串没有公共前缀，则相应的Trie树将非常消耗内存，这也是Trie树的一个缺点。
  比如， 给定一个单词a，如果通过交换单词中字母中的顺序可以得到另外的单词b，那么称b是a的兄弟单词。
  一般情况下，Trie树的结构都是采用26叉树进行组织的，每个节点对应一个字母，查询时，挨个字母进行匹配。算法的时间复杂度就是单词的长度n。
  Trie树的构建是在预处理阶段完成的，首先根据字典中的单词建立字典树，当树创建完毕，查询兄弟单词的频率就会提高很多，比Hash效率还高。
  Trie树适用于数据量大，重复多，但是数据种类小可以容纳内存的情况。