数据结构与算法---哈夫曼树、字典树
哈夫曼编码
哈夫曼编码，又称为霍夫曼编码。它是现代压缩算法的基础。
假设要把字符串【ABBBCCCCCCCCDDDDDDEE】转成二进制编码进行传输，那么，可以转成ASCII编码(65 ~ 69，1000001 ~1000101)，但是有点冗长。
如果希望编码更短呢?
可以先约定5个字母对应的二进制
对应的二进制编码:
000001001001010010010010010010010010011011011011011011100100 这样，一共20个字母，转成了20*3 = 60个二进制位
如果使用哈夫曼编码，可以压缩至41个二进制位，约为原来长度的68.3%
是如何做到哈夫曼树呢？
哈夫曼树
先计算出每个字母的出现频率(权值，这里直接用出现次数)，
【ABBBCCCCCCCCDDDDDDEE】
利用这些权值，构建一棵哈夫曼树(又称为霍夫曼树、最优二叉树)
如何构建一棵哈夫曼树?(假设有 n 个权值)
- 以权值作为根节点构建n棵二叉树，组成森林
- 在森林中选出2个根节点最小的树合并，作为一棵新树的左右子树，且新树的根节点为其左右子树根节点之和
- 从森林中删除刚才选取的2棵树，并将新树加入森林
- 重复2、3步骤，直到森林只剩一棵树为止，该树即为哈夫曼树
Trie(字典树)
需求
如何判断一堆不重复的字符串是否以某个前缀开头？
我们可以使用Set/Map存储字符串，然后遍历作比较。
时间复杂度是O(n)
而，Trie可以很好的解决前缀搜索问题。
Trie也叫做字典树、前缀树（Prefix Tree）、单词查找树
Trie的搜索效率主要跟前缀字符串的长度有关
假设使用 Trie 存储 cat、dog、doggy、does、cast、add 六个单词
Trie是一棵多叉树