树的应用

🔥 高优先级

本页覆盖哈夫曼编码与并查集：掌握定义、算法、不变量和复杂度后，再用题型检查边界。

编码和解码

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

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

编码集分类

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

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

• 固定长度 vs 非固定长度

• 固定长度编码集 （定长）：每个代码的长度相同，例如 ASCII 编码中每个字符都用 8 位表示。

• 可变长度编码集 （变长）：代码长度可以不同，例如 哈夫曼编码 中高频符号用较短代码，低频符号用较长代码，以实现数据压缩。

  • 前缀 vs 非前缀

• 前缀编码 ：没有一个编码是另一个编码的前缀

• 非前缀编码 ：有编码是其他编码的前缀

定长编码

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

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

1. 统计符号集合 ：先确定总共有多少个不同的符号，记为 n 。
2. 计算编码长度 ：要为每个符号分配一个不同的二进制码，所需的**最小码长 l **满足：

$$l=\lceil\log_2 n\rceil$$，可表示 $2^l$ 个码。

也就是说，使用 l 位二进制，可以最多表示 2l 个不同的符号。

3. 分配编码 ：从 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，概率是 $20/100=0.2$。

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

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

加权路径长度

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

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

设：

• 一共有 n 个符号；
• 第 i 个符号的出现频次 为 fi​ ；
• 该符号的编码长度为 li​ ；

则加权路径长度为：

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

注意

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

加权平均长度

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

设：

• 第 i 个符号的出现频次 为 fi​ ；
• 编码长度为 li​ ；
• 总频次 为 F=∑i=1n​fi​ ；

则加权平均长度 L 为：

$$L=\frac{WPL}{\sum_{i=1}^{n}f_i}=\sum_{i=1}^{n}p_i l_i$$

如果已将频次 标准化为概率 pi​=∑fi​fi​​ ，也可以表示为：

L=i=1∑n​pi​⋅li​

注意

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

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

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

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

WPL=50⋅1+20⋅2+20⋅3+10⋅3=50+40+60+30=180 位​

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

计算二：加权平均长度

方法一（基于频次）：

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

方法二（基于概率）：

L=0.5⋅1+0.2⋅2+0.2⋅3+0.1⋅3=0.5+0.4+0.6+0.3=1.8 位/符号​

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

对比总结

哈夫曼树

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

特点

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

构建过程

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

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

构建时维护一个最小堆：每轮取出两个最小权值 x,y，合并为 x+y 后放回。循环不变量是“森林中每棵树的权值等于其叶子权值之和”；合并结束时森林恰有一棵树。若有 n 个符号，建堆及合并复杂度为 O(n log n)。

哈夫曼树的带权路径长度（WPL）满足一个很实用的等价式：

WPL = 各次合并权值之和。

例如权值 2, 3, 5, 6, 7, 8, 9：合并序列为 2+3=5、5+5=10、6+7=13、8+9=17、10+13=23、17+23=40，所以 WPL = 5+10+13+17+23+40 = 108（即 WPL = 108）。左右分支取 0/1 可以互换，但叶子编码始终是前缀码：任何编码都不是另一编码的前缀，因此可逐位无歧义解码。单个符号时编码长度为 0（或按题目约定补 1 位），不要机械套用多符号结论。

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

边界、易错与题型闭环：只有一个符号时需按题目约定处理 0/1 位；权值相同时合并顺序可能不同，但 WPL 不变。不要把叶子权值之和当作 WPL，也不要把任意变长码误认为前缀码。题目通常给出频次要求合并次序、WPL 或某符号编码长度：先建最小堆逐轮记录合并值，再用“合并和”复核，最后从根到叶读 0/1。

严格二叉性质与高度约定：多符号 Huffman 树是严格二叉树（每个内部结点恰有 2 个孩子，无度 1 结点）。有 n 个叶结点时有 n-1 个分支结点、2n-1 个总结点；按边计高度最大 n-1、最小 ⌈log₂ n⌉，按层计再加 1（根为第 1 层，5 叶最大为 5 层）。前缀码判定要逐个检查“短码是否为其他码前缀”；例如 {0, 1, 00, 11} 不是前缀码。译码从根逐位走，抵达叶即输出并回根。若码长≤4且已有 1、01，剩余仅 00 子树的 0000/0001/0010/0011 共 4 码。

m 叉 Huffman：内部结点度只能为 0 或 m；若有 n₀ 个叶、n_m 个分支，则 n₀=(m-1)n_m+1。因此合并前需满足补零条件 (n-1)%(m-1)=0；不满足时先补若干个权值 0 的叶，再每轮取 m 个最小权值合并。

哈夫曼编码

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

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

实例

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

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

并查集

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

查找

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

一种紧凑表示把根的 parent 存成负值：parent[root] < 0 表示它是根，-parent[root] 表示集合规模；非根位置存父节点下标。这样不需要额外的 size 数组。

合并

合并操作 的目的是将两个 集合 合并为一个集合。先 Find 得到根；按规模合并时把规模较小的根挂到较大的根，并累加负值。按秩合并也可行，秩相等时才增加秩。路径压缩与按规模/秩合并同时使用，均摊复杂度为 O(α(n))（近似常数），单次朴素操作最坏可退化为 O(n)。

数组语义：Initial 时每个 parent[i]=-1（单元素根、规模 1）；Find(x) 返回根并做路径压缩；Union(a,b) 先找根再按规模合并。根的负值绝对值是规模，非根值是父下标；同集 Union 不改变数组。按规模合并使树高 ≤ ⌊log₂ n⌋，再配合路径压缩，均摊为 O(α(n))。

find(x):
    if parent[x] < 0: return x
    parent[x] = find(parent[x])       // 路径压缩
    return parent[x]

union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return false
    if parent[ra] > parent[rb]: swap(ra, rb) // ra 规模更大（负值更小）
    parent[ra] += parent[rb]
    parent[rb] = ra
    return true

易错点：根不是 parent[root] == root 而是负值；合并前必须先找根；同一集合合并不改变结构；路径压缩只改沿途父指针，不改变集合规模。题型通常围绕“最终根/数组状态、连通性判断、操作次数与复杂度”展开。

题目闭环

相关笔记

• 数组和特殊矩阵
• 串的定义与实现
• 串的模式匹配
• 串概述