树的应用

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

哈夫曼树

哈夫曼树（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操作找到两个集合的代表，然后决定哪个代表成为新的根。为了保持树的平衡性，并减少查找时间，常用的策略是按秩合并。其中，秩通常表示树的高度。较低的树会被附加到较高的树的根上。

0
6
7
8
1
6
8
2
3
5
S1
S2
S3
index
0
1
2
3
4
5
6
7
8
9
parent
0
1
2
2
1
2
0
0
0
1
Array Representation of S1, S2, S3
0
6
7
8
1
6
8
2
3
5
S3
index
0
1
2
3
4
5
6
7
8
9
parent
0
0
2
2
1
2
0
0
0
1
After union  S1, S2

代码实现

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