【数据结构之字典树Trie】C语言实现

/**

 * 字典树

 *  1、根节点（Root）不包含字符，除根节点外的每一个节点都仅包含一个字符；

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

 *  3、任意节点的所有子节点所包含的字符都不相同；

 *  4、关键词的插入和查找过程的时间复杂度均为 O(key_length)，

 *  5、空间复杂度 O(ALPHABET_SIZE * key_length * N) ，其中 N 是关键词的数量。

**/

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

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

    缺点：虽然不同单词共享前缀，但其实trie是一个以空间换时间的算法，每个结点只存储一个字符浪费了