13.字典树和并查集

字典树Trie

字典树的数据结构

字典数,即Trie树，又称单词查找树或键树,是一种树形结构.典型应用是用于统计和排序大量的字符串(但不仅限于字符串)， 所以经常被搜索引擎系统用于词频统计.

它的优点是:最大限度地减少无谓的字符串比较，查找效率比哈希表高

字典树的核心思想

字典树的基本性质

• 节点本身不存完整单词
• 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串
• 每个结点的所有子结点路径代表的字符都不相同