数据结构与算法_字典树

    字典树，又称为 Trie树，单词查找树，是一种树形结构，也是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

    它的优点是，利用字符串的公共前缀来减少查询时间，最大限度地减少无谓地字符串比较，查询效率比哈希树高。

    字典树的 3 个基本性质：

    1） 根结点不包含字符，除根结点以外每一个结点都只包含一个字符；

    2）从根结点到某一结点，路径上经过的字符连接起来，为该节点对应的字符串；

    3）每个结点的所有子结点包含的字符都不相同。

     例如，图中 bee 是一个单词， beer也是一个单词，此时可以在每个单词结束位置加一个 end[ ] 标记，就直到从根到这里有一个单词。

    字典的基本操作： 查找，插入和删除，极少出现删除操作。

    字典树的应用：

（1）字典树的创建

算法代码：

（2）字典树的查找

    算法代码：

性能分析：