Trie树和Patricia结构

这些结构是信息检索中常用的结构。

Trie树，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。

Patricia树，或称Patricia trie，或crit bit tree，压缩前缀树，是一种更节省空间的Trie。对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。

Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。

?

Trie树典型应用是用于快速检索（最长前缀匹配），统计，排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计，搜索提示等场景。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

? ?Trie树的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

?

Trie树有3个基本性质：

- 根节点不包含字符，除根节点外每一个节点都只包含一个字符
 - 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
 - 每个节点的所有子节点包含的字符都不相同

http://blog.csdn.net/pony_maggie/article/details/74538902?

?

?

Trie 树落伍了，自动机的功能比 Trie 树强，内存用量比 Trie 树小得多（小十几倍、甚至几十几百倍）