树的应用

需熟练掌握哈夫曼树的构建过程，可能在选择题或大题中考察，另外需了解并查集的概念。

编码和解码

符号映射
反向映射
比特流
符号序列
原始符号序列
编码
解码

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

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

编码集分类

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

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

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

前缀编码

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

注意

前缀编码表示 编码集中没有编码是另一个编码的前缀，不要这个定义和它的名字弄混了。

A
B
C
D
A
B
D
C
0
0
0
0
1
1
1
0
1
1
0
0
1
1
前缀编码
非前缀编码

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

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

补充

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

哈夫曼树

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

特点

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

构建过程

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

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

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

哈夫曼编码

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

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

实例

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

a
b
c
d
7
5
2
4
a
b
7
5
c
d
6
a
b
7
c
d
11
a
b
c
d
18
0
0
0
1
1
1
注意

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

并查集

并查集（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]++;
        }
    }
}