树的应用

真题练习：可在站内题库按“哈夫曼树”知识点筛选。

编码方式、哈夫曼树与并查集都应掌握。前两者侧重编码性质和带权路径长度，并查集侧重查找、合并及两种优化。

编码和解码

编码（Encoding）是将信息从一种形式（通常是人类可读的符号或数据）转换为另一种形式（通常是机器可处理的格式，如二进制比特流）的过程。其目的是为了便于存储、传输或处理信息。编码通常涉及将原始数据（如字符、数字等）映射为特定的代码，这些代码由一组 编码规则 定义。

解码（Decoding）是编码的 逆过程，即将编码后的数据（如二进制比特流）转换回原始形式的过程。解码需要依赖编码时使用的规则或 编码表，以确保正确还原原始信息。

编码集分类

编码集是一组用于表示特定符号或数据的 编码规则 的集合。

编码集 常按以下方式分类：

固定长度 vs 非固定长度
- 固定长度编码集（定长）：每个代码的长度相同，例如 ASCII 编码中每个字符都用 8 位表示。
- 可变长度编码集（变长）：代码长度可以不同，例如哈夫曼编码中高频符号用较短代码，低频符号用较长代码，以实现数据压缩。
前缀 vs 非前缀
- 前缀编码：没有一个编码是另一个编码的前缀
- 非前缀编码：有编码是其他编码的前缀

定长编码

定长编码是指：为每个符号分配长度完全相同的二进制编码。 也就是说，不管某个符号出现得多还是少，它所占用的 比特数 都是一样的。

定长编码的 构建方式 如下：

统计符号集合：先确定总共有多少个不同的符号，记为 $n$ 。
计算编码长度：要为每个符号分配一个不同的二进制码，所需的最小码长 $l$ 满足
$l=\left\lceil \log_2 n \right\rceil.$
也就是说，使用 $l$ 位二进制，最多可以表示 $2^l$ 个不同的符号。
分配编码：从 0 开始，依次将二进制数分配给每个符号，使用前导零补足到长度 $l$ 。

举个实例 说明一下

假设有 5 个符号：A、B、C、D、E

总数 $n=5$ ，因此编码长度 $l=\lceil\log_2 5\rceil=3$ ；
3 位二进制最多能编码 $2^3=8$ 个符号，足够使用；
分配如下：

根据以上构建过程可知：在定长编码对应的满层编码树中，所有 叶子结点（对应字符的结点）都位于同一层；在变长编码中，叶子结点 可以不位于同一层。

前缀编码

前缀编码（Prefix Code）是一种编码方式，其中没有任何编码是另一个编码的前缀。换句话说，在一组编码中，任何一个编码字符串都不会是另一个编码字符串的开头部分。这种特性确保了编码可以被唯一且无歧义地解码，常用于数据压缩和通信系统。

注意

前缀编码表示 编码集中没有编码是另一个编码的前缀，不要把这个定义和名称本身弄混。

编码集 {1, 01, 001, 0000} 对应的二叉树如上面的左图所示。该编码集为前缀编码，可以观察到，前缀编码的每一个编码都处于 叶子结点 的位置，这说明在对比特流进行解码的过程中不会出现歧义（想要获取到编码需要唯一地到达 叶子结点）。

编码集 {0, 10, 110, 1011} 对应的二叉树如上面的右图所示。该编码集为非前缀编码，可以观察到，非前缀编码 有编码处于 中间结点 的位置，这说明在对比特流进行解码的过程中会出现歧义，比如对于 10110，解码器无法确认是将开始的 10 解码为 B 还是将 1011 解码为 D。

补充

在前缀编码中，由于没有编码是其他编码的前缀，接收方可以逐位读取数据流，立即确定一个编码的结束并开始解码下一个编码，无需额外的分隔符。

编码长度计算

在信息编码相关的试题中，常会考察两种编码长度的计算方式：加权路径长度 和 加权平均长度。这两个概念虽相关，但含义和用途不同，需要仔细辨别。

此外，计算这两个指标时还涉及到两个基本的量：频次和概率。它们在形式上相似，但在理解和运用时也要有所区分。

频次：表示某个符号在整体数据中实际出现的次数。
概率：表示某个符号出现的相对频率，即该符号出现的频次除以总频次。

举个简单的例子：

假设一段文本中总共有 100 个符号，其中字母 A 出现了 20 次。那么 A 的频次是 20，概率是 $\frac{20}{100}=0.2$ 。

编码长度的计算可以基于频次，也可以基于概率。两种方法在数值上本质一致，只是表达形式不同，使用频次适用于原始统计数据，使用概率则适用于标准化分析。

接下来我们就分别介绍这两种编码长度的具体含义及其数学计算方式。

加权路径长度

加权路径长度 是指：所有符号的编码长度与其出现频次的乘积之和。

这个量表示整体编码所需的总比特数，是衡量编码总开销的重要指标。

设：

一共有 $n$ 个符号；
第 $i$ 个符号的出现频次为 $f_i$ ；
该符号的编码长度为 $l_i$ 。

则加权路径长度为：

WPL=\sum_{i=1}^{n}f_i l_i.

注意

“加权路径长度” 在树结构中也称为 “带权路径长度”，在各种前缀编码或变长编码场景中广泛使用。需要注意，这些不同的表述方式本质上描述的是相同的概念。

加权平均长度

加权平均长度 是指：在整个编码过程中，平均每个符号所占用的编码长度。它是在加权路径长度的基础上，除以总频次得到的平均值。

设：

第 $i$ 个符号的出现频次为 $f_i$ ；
编码长度为 $l_i$ ；
总频次为 $F=\sum_{i=1}^{n}f_i$ 。

则加权平均长度 L 为：

L=\frac{\sum_{i=1}^{n}f_i l_i}{\sum_{i=1}^{n}f_i} =\frac{WPL}{F}.

如果已将频次标准化为概率

p_i=\frac{f_i}{\sum_{j=1}^{n}f_j},

也可以表示为：

L=\sum_{i=1}^{n}p_i l_i.

注意

加权平均长度越小，说明编码越高效。很多编码算法（如哈夫曼编码）的目标之一就是最小化加权平均长度。

接下来通过一个实例来说明一下两个概念的计算：

假设我们有如下符号统计信息：

符号	出现频次 $f_i$	概率 $p_i$	码长 $l_i$
A	50	0.50	1
B	20	0.20	2
C	20	0.20	3
D	10	0.10	3

计算一：加权路径长度（WPL）

WPL=50\cdot1+20\cdot2+20\cdot3+10\cdot3 =50+40+60+30=180\ \text{位}.

表示：这段编码文本总共用了 180 位。

计算二：加权平均长度

方法一（基于频次）：

L=\frac{180}{50+20+20+10} =\frac{180}{100} =1.8\ \text{位/符号}.

方法二（基于概率）：

L=0.5\cdot1+0.2\cdot2+0.2\cdot3+0.1\cdot3 =0.5+0.4+0.6+0.3 =1.8\ \text{位/符号}.

表示：平均每个符号的编码长度为 1.8 位/符号。

对比总结

项目	值	单位	用途
加权路径长度	180	位（bit）	整体编码所占的总位数
加权平均长度	1.8	位/符号（bit/symbol）	衡量单位符号的平均编码效率

哈夫曼树

哈夫曼树（Huffman Tree）是一种特殊的 二叉树，通常用于 数据压缩 算法中，特别是用于构建 哈夫曼编码（Huffman Coding）。哈夫曼树的主要目标是实现 无损压缩，通过赋予不同的数据符号不同长度的编码来减少数据的存储空间。

特点

哈夫曼树是一棵二叉树，通常是 带权二叉树，其中每个 叶子节点 都对应一个数据符号，而每个内部节点都没有数据，只有权值。
哈夫曼树的 叶子节点 的权值通常表示数据符号的 出现频率，而内部节点的权值等于其子节点 权值之和。
哈夫曼树的 构建目标 是找到一棵树，使得权值较高的数据符号拥有较短的编码，权值较低的数据符号拥有较长的编码。

构建过程

创建一个包含所有数据符号的森林（初始状态下，每个数据符号都是一棵单节点树）。
从森林中 选择两棵树，这两棵树的 权值最小。将它们 合并为一棵新的树，新树的权值为两棵树的 权值之和。
将 新的树放回森林 中，重复步骤 2，直到森林中只剩下一棵树，这棵树就是 哈夫曼树。
构建好的哈夫曼树具有一个重要的性质：权值较高的数据符号在树中的深度较浅，权值较低的数据符号在树中的深度较深。

执行轨迹

哈夫曼树为什么每次合并最小权值

逐步合并权值 2、4、5、7，观察新结点权值如何重新进入候选集合并最终形成根结点。

0214253746511618

初始森林四个权值各自是一棵单结点树。

对于后文权值 $2,4,5,7$ 的例子，三次合并依次为 $2+4=6$ 、 $5+6=11$ 、 $7+11=18$ 。其目标仍是最小化

WPL=\sum_{i=1}^{n}f_i l_i.

一旦构建了哈夫曼树，就可以生成数据符号的 哈夫曼编码。哈夫曼编码是一种 变长编码，用于表示不同数据符号。在哈夫曼编码中，权值较高 的数据符号通常对应 较短的编码，权值较低 的数据符号对应 较长的编码。这种编码方式可以实现数据的高效压缩和解压缩。

哈夫曼树和哈夫曼编码在 数据压缩 领域具有广泛的应用，例如在无损压缩算法中，如 ZIP 文件压缩，图像压缩（如 JPEG）等。通过构建适用的哈夫曼树和编码，可以大幅减少数据的存储和传输成本。

哈夫曼编码

遍历 哈夫曼树，为每个数据符号生成相应的 哈夫曼编码。编码的生成方式如下（左 0 右 1）：

向左走时添加一个 0 位。
向右走时添加一个 1 位。
沿着树的路径一直到达 叶子节点 时，即可生成该 叶子节点 对应的数据符号的编码。

实例

为 a, b, c, d 四个字母生成 哈夫曼编码，其对应的权值分别为 7, 5, 2, 4

注意

哈夫曼编码 是一种经典的前缀编码。

并查集

并查集（Union-Find）是一种数据结构，主要用于解决 集合划分 及 查询问题。它主要支持两种操作：查找（Find）和合并（Union）。其核心思想是使用一个数组（或其他数据结构）来存储每个元素的 父节点信息。

查找

查找操作 的目的是找到给定元素所属集合的代表。这可以通过追踪 父节点 来实现，直到找到 根元素（即 父节点 为其自身的元素）。路径压缩 可以在查找过程中应用，使得从指定节点到其根的路径上的每个节点都直接指向根，从而提高后续查找的效率。

合并

合并操作 的目的是将两个集合合并为一个集合。为了执行合并，首先使用 Find 操作找到两个集合的代表，然后决定哪个代表成为新的根。为了保持 树的平衡性，并减少查找时间，常用的策略是 按秩合并。其中，秩通常表示 树的高度。较低的树 会被附加到 较高的树 的根上。

同时使用路径压缩与按秩（或按大小）合并时， $m$ 次操作的总时间为 $O(m\alpha(n))$ ，其中 $\alpha$ 是增长极慢的反阿克曼函数；在实际规模下可近似看作常数时间。

#define MAXN 1000

int parent[MAXN];  // 存储每个点的父节点
int rank[MAXN];    // 秩

// 初始化
void initialize(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;  // 初始时，每个元素的父节点是其自身
        rank[i] = 0;    // 初始时，每个元素的秩为 0
    }
}

// 查找
int find(int x) {
    if (parent[x] != x) {
        // 路径压缩
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 合并
void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

编码与并查集的判定边界

前缀编码为何可以逐位解码

前缀编码要求任意一个码字都不是另一个码字的前缀。接收端从根开始按比特向下走，走到叶结点就输出一个字符并回到根；由于不会在到达一个码字后还可能把它延长成另一个码字，这个切分过程是唯一的。若码表中同时有 0 和 01，则比特串 01 可以被解释为“0 后面还有 1”，也可以解释为“01”，因此它不是前缀编码。

哈夫曼树给出的是一组最优前缀码，而不是唯一的一组码字。权值相等时，先合并哪两个叶结点可以不同；左右子树标记为 0、1 也可以互换。树形和具体码字虽然不同，只要每一步都选择当前最小的两个权值合并，加权路径长度仍达到最小。答题时若没有要求输出唯一编码，应比较 WPL，而不应因为某一位不同就判错。

若权值是出现次数 $w_i$ ，码长是 $l_i$ ，则

\operatorname{WPL}=\sum_iw_il_i,\qquad \bar L=\frac{\operatorname{WPL}}{\sum_iw_i}.

前者是整批消息的总编码长度，后者才是平均每个符号的码长。只有当权值已经是总和为 1 的概率时，二者才数值相同。构建哈夫曼树时，内部结点权值等于两个孩子权值之和，最终根权值等于所有原始权值之和，这是手算的快速核验。

并查集维护的是“集合代表元”

并查集把每个集合表示为一棵以根为代表元的父指针树。Find 操作返回根，而不是返回直接父结点；两个元素的根相同才说明它们属于同一个集合。路径压缩会把本次查找路径上的结点直接连到根，按秩或按集合大小合并会把较矮或较小的树接到另一棵树下。两种优化配合后， $m$ 次操作的均摊时间是 $O(m\alpha(n))$ ，其中 $\alpha(n)$ 增长极慢，在考试规模下可近似视为常数。

路径压缩后，秩不再等于结点的实时高度，它只保留“合并时的高度上界”这一用途。因此不能看到父指针变短就去手改秩。并查集也常用于无向图判环：处理边 $(u,v)$ 前，若 Find( $u$ ) 与 Find( $v$ ) 已相同，加入该边会形成环；否则 Union 两个集合。它只能回答连通性和合并问题，不能替代图的邻接关系或最短路径算法。