5.5 树与二叉树的应用

• 概念

1. 结点的权：大小可以表示结点的重要性

2. 结点的带权路径长度：从树的根到该结，的路径长度（经过的边数）与该结点权的乘积

3. 树的带权路径长度：树中所有叶结点的带权路径长度之和(WPL)

   

4. 哈夫曼树（最优二叉树）：在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL) 最小的二叉树

5. 编码方式

   1. 每个字符对应二进制长度分：

      1. 固定长度编码，每个字符对应相同长度的二进制编码

      2. 可变长度编码，允许不同字符用不同长度的二进制编码

   2. 按是否有歧义分：

      1. （解码无歧义）前缀编码：没有一个编码是另一个编码的前缀

      2. （解码有歧义）非前缀码

   3. 哈夫曼编码：利用构造哈夫曼树的方法得到哈夫曼编码，左边0，右边1

      

6. 并查集

   1. 如何查到一个元素到底属于哪一个集合?

      ·指定元案出发，一路向北，找到根节点

   2. 如何断两个元素否属于同一个集合?

      ·分别查到两个元素的根，判断根节点是否相同即可

   3. 如何把两个集合并为一个集合?

      ·让一棵树成为另一棵树的子树即可

   4. 采用双亲表示法存储并查集树的好处

      1. 容易向上溯源（易于查）

      2. 另一棵树的根指向目标树的根即可实现并（易于并）

• 理解

1. 哈夫曼树的构造

   

2. 并查集的实现

   1. 定义：有n个元素则定义大小为n的数组，根的值为-1，其他结点值为根节点的下标

   2. 查操作：往上溯源找到只为-1的根节点的下标（最坏复杂度O[n]）

   3. 并操作：两个集合合并成一个，把其中一个集合的根的值改成另一个根节点的下标即可（复杂度O[1]）

   4. 并操作的优化：尽可能降低并查集的高度

      1. 修改复杂度为O[1]的并操作，该方法使得构造的树高不超过log₂n（向下取整）+1，从而查操作的复杂度降到O[log₂n]

      2. 每次合并的时候让小树合并到大树的根下

      3. 根的值仍然取负值，但是绝对值是该树的所有节点数目，从而可以体现树的大小

   5. 查操作的优化：压缩路径（复杂度O[α(n)]）

      1. 路径上经过的结点都直接挂到根节点下面

         1. while循环向上溯源，目的是找到根（与优化前一样）

         2. 再次while循环，目的是把路上的结点都直接转接到根节点下面（优化内容）（如果每个叶结点都经过这个操作，那么原来的树的高度就变成了2，一个根，其他全是叶子）

   6. 

3. 

• 技巧

1. 在有n个叶子结点的哈夫曼二叉树中，非叶子结点一共有n-1个，总共有2n-1个结点，叶结点个数即为可编码的个数

2. 哈夫曼编码不超过4，已经编码两个：1、01，则最多还可以编码4个：0000、0001、0010、0011

3. 哈夫曼二叉树的度只有0和2两种情况

4. n个有序的序列和m个有序的序列合并，最坏情况要比较m+n-1次大小