树的应用

🔥 高优先级

并查集其实没考过，编码方式和哈夫曼树也是高频考点。

编码和解码

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

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

编码集分类

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

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

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

定长编码

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

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

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

l = ⌈ lo g_{2} n ⌉

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

分配编码：从 $0$ 开始，依次将二进制数分配给每个符号，使用前导零补足到长度 $l$ 。

举个实例 说明一下

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

总数 $n = 5$ ，因此编码长度 $l = ⌈ lo g_{2} 5 ⌉ = 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 = i = 1 \sum n f_{i} \cdot l_{i}

注意

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

加权平均长度

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

设：

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

则加权平均长度 $L$ 为：

L = \frac{\sum _{i = 1}^{n} f _{i} \cdot l _{i}}{\sum _{i = 1}^{n} f _{i}}

如果已将频次标准化为概率 $p_{i} = \frac{f _{i}}{\sum f _{i}}$ ，也可以表示为：

L = i = 1 \sum n p_{i} \cdot 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 \cdot 1 + 20 \cdot 2 + 20 \cdot 3 + 10 \cdot 3 = 50 + 40 + 60 + 30 = 180 位

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

计算二：加权平均长度

方法一（基于频次）：

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

方法二（基于概率）：

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

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

对比总结

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

哈夫曼树

哈夫曼编码构建规则

在数据压缩中，如果所有数据符号都采用 固定长度编码（如 ASCII 编码），那么无论某个符号出现得多频繁，都需要占用相同数量的比特。

如果能够让出现频率高的数据符号使用 较短的编码，而 出现频率低 的数据符号使用 较长的编码，就可以在保证能够正确解码的前提下，减少整体编码长度，从而提高压缩效率。

哈夫曼树（Huffman Tree）正是为解决这一问题而提出的一种特殊的 带权二叉树。它又称 最优二叉树（Optimal Binary Tree），其特点是所有叶子结点的 带权路径长度（WPL）最小，因此被广泛应用于各种无损压缩算法中。

特点

哈夫曼树是一棵 带权路径长度（WPL）最小 的二叉树，因此又称 最优二叉树。
叶子结点 表示待编码的数据符号，其权值通常表示该符号的 出现频率。
内部结点 不对应任何数据符号，其权值等于左右孩子结点权值之和。
权值越大的叶子结点通常距离根越近，因此对应的编码越短；权值越小的叶子结点通常距离根越远，因此对应的编码越长。

构建过程

构建哈夫曼树采用的是一种 贪心策略：每一步都选择当前权值最小的两棵树进行合并。

具体步骤如下：

创建一个包含所有数据符号的森林（初始时，每个数据符号都是一棵单结点树）。
从森林中选择 权值最小 的两棵树，将它们合并为一棵新的二叉树，新树的根结点权值为两棵树权值之和。
将新树重新放回森林中，重复步骤 2，直到森林中只剩下一棵树，这棵树就是 哈夫曼树。

性质

哈夫曼树具有以下几个重要性质：

哈夫曼树的 带权路径长度（WPL）最小。
权值越大的叶子结点通常距离根越近，对应的编码越短。
哈夫曼树 不唯一，但对于同一组权值，其 最小带权路径长度（WPL）唯一。
哈夫曼树中不存在度为 1 的结点，因此一定是一棵 满二叉树。

哈夫曼编码

构建好哈夫曼树后，即可为每个数据符号生成对应的 哈夫曼编码。

哈夫曼编码具有以下特点：

是一种 变长编码；
是一种 前缀编码（Prefix Code），任意一个数据符号的编码都不是另一个数据符号编码的前缀，因此能够唯一译码。

编码方法如下：

从根结点开始遍历哈夫曼树；
向左走记为 0；
向右走记为 1；
从根结点到某个叶子结点经过的 0、1 序列，就是该数据符号对应的哈夫曼编码。

说明
左子树记为 0、右子树记为 1 只是一种约定，也可以反过来表示，不会影响编码长度，只会得到另一组等价的哈夫曼编码。

实例

已知四个数据符号 a、b、c、d 的权值分别为 7、5、2、4，构建哈夫曼树并生成对应的哈夫曼编码。

注意

哈夫曼编码是一种经典的前缀编码，广泛应用于 ZIP、GZIP 等无损压缩算法，同时也是 JPEG 等多媒体压缩标准中的重要编码步骤。

并查集

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

查找

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

合并

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

#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]++;
        }
    }
}