Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串）。
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
它有3个基本性质：
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。
注意：不用动态数组或者动态申请空间的话复杂度会达到26^n次方，在建树的时候最好用动态数组和malloc链表。最好不要用结构体进行封装，有可能会爆栈。
查询复杂度与树高有关，基本O(len)
Hash：
hash算法的意义在于提供了一种快速存取数据的方法，它用一种算法建立键值与真实值之间的对应关系，(每一个真实值只能有一个键值,但是一个键值可以对应多个真实值)，这样可以快速在数组等条件中里面存取数据，其实就是一种映射。
Hash最重要就是Hash映射和冲突处理，
Hash可以拿来判重和统计数目，主要把字符串映射为整数，尽量选比较大的素数。
网友评论