树的应用
哈夫曼树
带权路径长度
结点的权：有某种现实含义的数值（如：表示结点的重要性等）
结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
树的带权路径长度：所有的叶子结点带权路径长度之和
哈夫曼树的定义
在含有n个带权叶节点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树
哈夫曼树的构造
在给定n个权值分别为w1,w2……wn的结点，构造哈夫曼树的算法描述如下：
① 将这n个结点分别作为n棵仅含有一个结点的二叉树，构成森林F。
② 构造一个新结点，从F中选取两颗根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
③ 从F中删除刚才选出的两棵子树，并将新结点的权值置为左、右子树上根结点的权值之和。
④ 从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
④ 重复步骤②和③，直至F中只剩下一棵树为止。
【特点】
① 每个初始节点最终都成为叶节点，且权值越小的结点到根结点的路径长度越大
② 哈夫曼树的结点总数为2n - 1
③ 哈夫曼树中不存在度为1的结点
④ 哈夫曼树并不唯一，但WPL必然相同且为最优
哈夫曼编码
固定长度编码 – 每个字符用相等长度的二进制位表示
可变长度编码 – 允许对不同字符用不等长的二进制位表示
若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码
前缀编码解码无歧义
非前缀编码解码有歧义
由哈夫曼树得到哈夫曼编码 – 字符集中的每个字符作为一个叶子节点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树
使用哈夫曼编码可以进行数据压缩
并查集
逻辑结构 – 集合
将各个元素划分为若干个互不相交的子集
用互不相交的树，表示多个“集合”
查
如何“查”到一个元素到底属于哪个集合？
– 从指定元素出发，一路向上，找到根结点
如何判断两个元素是否属于同一个集合？
– 分别查到两个元素的根，判断根结点是否相同即可
并
如何把两个集合“并”为一个集合？
– 让一棵树称为另一棵树的子树即可
并查集的基本操作
使用 双亲表示法、孩子表示法、孩子兄弟表示法 中的哪种方法？
– 双亲表示法
【原因】
双亲表示法：每个结点保存指向双亲的“指针”
优点：找根节点比较方便
集合的两个基本操作 – “并”和“查”
Find – ”查“操作：确定一个指定元素所属集合
Union – ”并“操作：将两个不相交的集合合并为一个
注：并查集（Disjoint Set）是逻辑结构 – 集合的一种具体实现，只进行”并“和”查“两种基本操作
#define SIZE 13
int UFSet[SIZE]; //集合元素数组
//初始化并查集
void Initial(int S[]){
for(int i = 0;i<SIZE;i++)
S[i] = -1;
}
//Find "查"操作，找x所属集合（返回x所属根结点）
int Find(int S[],int x){
while(S[x]>=0) //循环寻找x的根
x = S[x];
return x; //根的S[]小于0
}
//Union "并"操作，将两个集合合并为一个
void Union(int S[],int Root1,int Root2){
//要求Root1和Root2是不同的集合
if(Root1 == Root2) return ;
//将根Root2连接到另一个根Root1下面
S[Root2] = Root1;
}
”查“操作时间复杂度(最坏情况下)：O(n)
”并“操作时间复杂度：O(1)
Union操作的优化
优化思路：在每次Union操作构建树的时候，尽可能让树不长高
① 用根节点的绝对值，表示树的结点总数
② Union操作，让小树合并到大树
//Union "并"操作，小树合并到大树
void Union(int S[],int Root1,int Root2){
if(Root1 == Root2) return;
if(s[Root2]>S[Root1]){ //Root2结点数更少
S[Root1] += S[Root2]; //累加结点总数
S[Root2] =Root1; //小树合并到大树
}else{
S[Root2] += S[Root1]; //累加结点总数
S[Root1] = Root2; //小树合并到大树
}
}
该方法构造的树高不超过[log2n]+1
Find操作最坏的时间复杂度：O(log2n)
并查集的进一步优化
Find操作的优化（压缩路径）
压缩路径 – Find操作，先找到根结点，再将查找路径上所有的结点都挂到根结点下
（在下一次查找时，查找路径就被压缩了）
//Find "查"操作优化，先找到根结点，再进行"压缩路径"
int Find(int S[],int x){
int root = x;
while(S[root]>=0) root = S[root]; //循环找到根
while(x!=root){ //压缩路径
int t = S[x]; //t指向x的父节点
S[x] = root; //x直接挂到根结点下
x = t;
}
return root; //返回根结点编号
}
并查集优化的核心思想：尽量让树变矮
点开链接玩一玩：https://www.cs.usfca.edu/~galles/visualization/DisjointSets.html
更多算法：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html