数据结构——5.5 树与二叉树的应用
5.5 树与二叉树的应用
- 概念
-
结点的权：大小可以表示结点的重要性
-
结点的带权路径长度：从树的根到该结，的路径长度（经过的边数）与该结点权的乘积
-
树的带权路径长度：树中所有叶结点的带权路径长度之和(WPL)
-
哈夫曼树（最优二叉树）：在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL) 最小的二叉树
-
编码方式
-
每个字符对应二进制长度分：
-
固定长度编码，每个字符对应相同长度的二进制编码
-
可变长度编码，允许不同字符用不同长度的二进制编码
-
-
按是否有歧义分：
-
（解码无歧义）前缀编码：没有一个编码是另一个编码的前缀
-
（解码有歧义）非前缀码
-
-
哈夫曼编码：利用构造哈夫曼树的方法得到哈夫曼编码，左边0，右边1
-
-
并查集
-
如何查到一个元素到底属于哪一个集合?
·指定元案出发，一路向北，找到根节点
-
如何断两个元素否属于同一个集合?
·分别查到两个元素的根，判断根节点是否相同即可
-
如何把两个集合并为一个集合?
·让一棵树成为另一棵树的子树即可
-
采用双亲表示法存储并查集树的好处
-
容易向上溯源（易于查）
-
另一棵树的根指向目标树的根即可实现并（易于并）
-
-
- 理解
-
哈夫曼树的构造
-
并查集的实现
-
定义：有n个元素则定义大小为n的数组，根的值为-1，其他结点值为根节点的下标
-
查操作：往上溯源找到只为-1的根节点的下标（最坏复杂度O[n]）
-
并操作：两个集合合并成一个，把其中一个集合的根的值改成另一个根节点的下标即可（复杂度O[1]）
-
并操作的优化：尽可能降低并查集的高度
-
修改复杂度为O[1]的并操作，该方法使得构造的树高不超过log₂n（向下取整）+1，从而查操作的复杂度降到O[log₂n]
-
每次合并的时候让小树合并到大树的根下
-
根的值仍然取负值，但是绝对值是该树的所有节点数目，从而可以体现树的大小
-
-
查操作的优化：压缩路径（复杂度O[α(n)]）
-
路径上经过的结点都直接挂到根节点下面
-
while循环向上溯源，目的是找到根（与优化前一样）
-
再次while循环，目的是把路上的结点都直接转接到根节点下面（优化内容）（如果每个叶结点都经过这个操作，那么原来的树的高度就变成了2，一个根，其他全是叶子）
-
-
-
-
-
- 技巧
-
在有n个叶子结点的哈夫曼二叉树中，非叶子结点一共有n-1个，总共有2n-1个结点，叶结点个数即为可编码的个数
-
哈夫曼编码不超过4，已经编码两个：1、01，则最多还可以编码4个：0000、0001、0010、0011
-
哈夫曼二叉树的度只有0和2两种情况
-
n个有序的序列和m个有序的序列合并，最坏情况要比较m+n-1次大小