哈夫曼树与并查集

这两个东西放在同一节，是因为它们都是「树的应用」，而不是因为它们相关。 哈夫曼树考的是手算 WPL 和编码，并查集考的是双亲数组里那些负数是什么意思。

对有算法竞赛背景的人，这一节要注意的不是算法（两个都很熟），而是教材的实现细节与你写惯的版本不一样——尤其是并查集的根结点存负数。

机制

带权路径长度与哈夫曼树

• 树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。
• 从树的根到一个结点的路径长度与该结点上权值的乘积，称为该结点的带权路径长度。
• 树中所有叶结点的带权路径长度之和称为该树的带权路径长度：

式中， 是第 个叶结点所带的权值， 是该叶结点到根结点的路径长度。

在含有 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。

边界辨析：

WPL 只累加叶结点，且 是路径长度（边数），不是层数。 教材图 5.24 的三棵树叶结点权都是 ： (a) ； (b) ； (c) ——(c) 最小，它恰好是哈夫曼树。 注意 (c) 里权值最大的 7 的路径长度是 1，权值最小的 2 的路径长度是 3。

哈夫曼树的构造

给定 个权值分别为 的结点：

1. 将这 个结点分别作为 棵仅含一个结点的二叉树，构成森林 。
2. 构造一个新结点，从 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3. 从 中删除刚才选出的两棵树，同时将新得到的树加入 中。
4. 重复步骤 2) 和 3)，直至 中只剩下一棵树为止。

哈夫曼树的三条性质：

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
2. 构造过程中共新建了 个结点（双分支结点），因此哈夫曼树的结点总数为 。
3. 每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。

边界辨析：

教材注意框：「左分支和右分支究竟是表示 0 还是表示 1 没有明确规定，因此构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度 WPL 相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但 WPL 必然相同且为最优。」

两句都要记：树不唯一，WPL 唯一。 题目问「哈夫曼树是否唯一」答否，问「WPL 是否唯一」答是。 由性质 3 还可推出：哈夫曼树是一棵正则二叉树（只有度 0 和度 2），于是 给出 ， 总数 ——性质 2 和性质 3 其实是同一件事的两种说法。

哈夫曼编码与前缀编码

• 固定长度编码：对每个字符用相等长度的二进制位表示。
• 可变长度编码：允许对不同字符用不等长的二进制位表示。可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。

举例：设计字符 A、B 和 C 对应的编码 0、10 和 110 是前缀编码。对前缀编码的解码很简单，因为没有一个编码是其他编码的前缀，所以识别出第一个编码，将它翻译为原字符，再对剩余的码串执行同样的解码操作。例如，码串 0010110 可被唯一地翻译为 A、A、B 和 C。 反例：若再将字符 D 的编码设计为 11，此时 11 是 110 的前缀，则上述码串的后三位就无法唯一翻译。

由哈夫曼树得到哈夫曼编码：将每个字符当作一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树；然后将从根到叶结点的路径上分支标记的字符串作为该字符的编码。约定左分支表示 0，右分支表示 1。

教材图 5.27 的例子（）：

此处的 WPL 可视为最终编码得到二进制编码的长度，共 224 位。若采用 3 位固定长度编码，则得到的二进制编码长度为 300 位，因此哈夫曼编码共压缩了 25% 的数据。

利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

并查集

并查集是一种简单的集合表示，它支持以下 3 种操作：

操作	含义
Initial(S)	将集合 中的每个元素都初始化为只有一个单元素的子集合
Union(S,Root1,Root2)	把集合 中的子集合 Root2 并入子集合 Root1。要求 Root1 和 Root2 互不相交，否则不执行合并
Find(S,x)	查找集合 中单元素 所在的子集合，并返回该子集合的根结点

存储结构：通常用树的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树构成表示全集合的森林，存放在双亲表示数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲域为负数（可设置为该子集合元素数量的相反数）。

#define SIZE 100
int UFSets[SIZE];                     //集合元素数组（双亲指针数组）
 
void Initial(int S[]){
    for(int i=0;i<SIZE;i++)
        S[i]=-1;                      //每个自成单元素集合
}
 
int Find(int S[],int x){
    while(S[x]>=0)                    //循环寻找 x 的根
        x=S[x];
    return x;                         //根的 S[] 小于 0
}
 
void Union(int S[],int Root1,int Root2){
    if(Root1==Root2) return;          //要求 Root1 与 Root2 是不同的集合
    S[Root2]=Root1;                   //将根 Root2 连接到另一根 Root1 下面
}

Find 操作和 Union 操作的时间复杂度分别为 和 ，其中 为树的深度。

优化：在极端情况下， 个元素构成的集合树的深度为 ，则 Find 操作的最坏时间复杂度为 。改进的办法是：在做 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{                             //Root1 结点数更少
        S[Root2]+=S[Root1];
        S[Root1]=Root2;
    }
}

采用这种方法构造得到的集合树，其深度不超过 。

随着子集逐对合并，集合树的深度越来越大，为了进一步减少确定元素所在集合的时间，还可进一步对 Find 操作进行优化——压缩路径。

口径差异：

教材的并查集与算竞写法有三处实质差异，每一处都能出选择题：

	算竞常见写法	王道教材
根的标记	fa[x]==x（自环）	S[x] 为负数
根存什么	无额外信息	成员数量的相反数（-size）
合并依据	按秩（rank/height）或随意	按成员数量（size），小树并到大树
路径压缩	默认必写，与按秩合并同时用	作为「进一步优化」单独列出

所以题目给出一个数组 [-4, -3, -3, 2, 1, 2, 0, 0, 0, 1] 让你画出森林时， 负数的绝对值是那棵树的结点数，不是深度、不是秩。 教材图 5.29 的例子： 的根是 0，S[0]=-4； 的根是 1，S[1]=-3。 深度界 也是按 size 合并推出来的，与「按秩合并」的界形式相同但依据不同。

手算模板

构造哈夫曼树：

1. 把 个权值排成一列。
2. 每次取最小的两个合并，新结点权值 = 两者之和，放回队列。
3. 重复到只剩一个。
4. 左 0 右 1 标分支，从根到叶读出编码。
5. 验算：结点总数应为 ，且没有度为 1 的结点。

算 WPL 的两种等价方法：

• ；
• ——因为每次合并的和都恰好被多计一层。第二种更快，可以用来验算。

并查集画森林：

1. 扫一遍数组，负数位置就是根，绝对值是该树的结点数。
2. 其余位置的值指向双亲，逐个挂上去。
3. 验算：所有负数绝对值之和 = 元素总数。

边界

说法	判断	说明
「WPL 要累加所有结点」	❌	只累加叶结点
「 是叶结点所在的层数」	❌	是路径长度（边数），等于层数减 1
「哈夫曼树唯一」	❌	不唯一，但 WPL 唯一且最优
「哈夫曼树中可能有度为 1 的结点」	❌	不存在，它是正则二叉树
「 个字符的哈夫曼树有 个结点」	❌	个
「左分支必须是 0」	❌	没有明确规定，只是习惯约定
「前缀编码就是编码有公共前缀」	❌	正相反：没有一个编码是另一个编码的前缀
「哈夫曼编码一定比定长编码短」	⚠️	各字符频率相同时不会更短；教材例子压缩了 25%
「并查集的根 fa[x]==x」	❌	教材口径是 S[x] 为负数
「根存的负数是树的深度」	❌	是成员数量的相反数
「Union 的复杂度是 」	❌	； 的是 Find
「按大小合并后深度是 」	⚠️	是不超过
「Union 可以对同一集合执行」	❌	要求两根互不相交，否则不执行合并

对照速查

量	结论
WPL	（只算叶结点） 所有非叶结点的权值
哈夫曼树结点总数
新建结点数
度为 1 的结点数	0
Find 复杂度
Union 复杂度
按大小合并后深度

并查集数组值	含义
负数	这是根；绝对值 = 该子集合的成员数量
非负数	指向双亲的下标

考点

• WPL 的定义与手算（2012、2018、2021、2023 命题追踪）。
• 哈夫曼树不唯一但 WPL 唯一（教材注意框）。
• 结点总数 、无度为 1 的结点（2010、2019 命题追踪）。
• 前缀编码的定义与译码（2014、2017、2020 命题追踪）。
• 哈夫曼编码与定长编码的差异（2022 命题追踪），会算压缩率。
• 并查集用双亲表示法，根存负数且绝对值是成员数量。
• 按成员数量合并后深度 。

链接

• 🏠 返回总览：数据结构第 5 章：树与二叉树总览
• ⬅️ 上一节：5.4 树、森林
• 🔗 双亲表示法：5.4.1 树的存储结构
• 🔗 正则二叉树与 ：5.2.1 二叉树的定义及其主要特性
• 🔗 并查集用于判环：6.4.1 最小生成树
• 📖 名词库：第 5 章名词库