目录
一、主要任务
二、主要内容
（一）字典树（Trie）
1. 什么是字典树？
2. 字典树的节点设计
3. 插入单词
4. 查找单词
5. 查找前缀
6. 完整代码与测试
7. 扩展思考
（二）并查集（Union-Find）
1. 什么是并查集？
2. 并查集的表示
3. 查找操作（Find）
4. 路径压缩
5. 合并操作（Union）
6. 完整实现
7. 测试示例
8. 深入理解路径压缩与按秩合并
一、主要任务
1. 实现字典树（Trie）的单词插入与查找。
2. 掌握并查集的合并与路径压缩
二、主要内容
在算法与数据结构的学习中，字典树（Trie）和并查集（Union-Find）是两个非常实用且有趣的结构。字典树擅长处理字符串的前缀匹配问题，而并查集则高效地管理元素之间的连通关系。
（一）字典树（Trie）
1. 什么是字典树？
字典树，又称前缀树或Trie树，是一种专门用于处理字符串集合的树形数据结构。它的核心思想是利用字符串的公共前缀来减少查询时间，最大限度地避免不必要的字符串比较。
想象一个场景：我们要存储一个单词列表，比如 ["cat", "car", "dog"]，并快速判断某个单词是否在列表中，或者查找所有以某个前缀开头的单词。如果用哈希表存储，可以快速判断单词是否存在，但无法高效地查询前缀。而字典树通过将单词拆分成字符，逐层构建树结构，使得查找前缀变得极其高效。
字典树的特点：
-
根节点不包含字符，除根节点外每个节点都包含一个字符。
-
从根节点到某个节点的路径上所有字符连接起来，就是该节点对应的字符串。
-
每个节点的所有子节点包含的字符都不相同。
例如，插入 "cat" 和 "car" 后，树的结构如下（用文字描述）：
(root) / \\ c d / \\ a o / \\ \\ t r g
注意 "cat" 和 "car" 共享了前缀 "ca"，这正是字典树的优势所在。
2. 字典树的节点设计
在Java中，我们通常用一个类来表示Trie的节点。每个节点需要存储两个信息：
-
一个标志，表示从根到当前节点的路径是否构成一个完整的单词。
-
指向子节点的引用。子节点通常用一个数组或哈希表来存储，因为字符集可能有限（比如26个小写字母）或不确定。
对于只包含小写字母的简单场景，我们可以用大小为26的数组来存储子节点。数组下标对应字符 'a' 到 'z'。这样查找子节点的时间复杂度为O(1)。
class TrieNode {
// 子节点数组，长度为26，对应26个小写字母
TrieNode[] children;
// 标记当前节点是否是一个单词的结尾
boolean isEnd;
public TrieNode() {
children = new TrieNode[26];
isEnd = false;
}
}
3. 插入单词
插入单词的过程很简单：从根节点开始，遍历单词的每个字符。对于每个字符，如果当前节点的子节点中不存在该字符，则创建一个新节点；然后移动到该子节点。遍历完所有字符后，将最后一个节点的 isEnd 标记为 true。
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// 插入一个单词
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch – 'a'; // 将字符转换为数组下标，'a'对应0
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEnd = true; // 标记单词结束
}
}
4. 查找单词
查找单词和插入类似，也是从根节点开始逐字符向下遍历。如果某个字符不存在，说明单词不在字典中；如果遍历完所有字符，最后节点的 isEnd 为 true，则表示单词存在；否则，如果 isEnd 为 false，说明该路径只是一个前缀，并非完整单词。
// 查找单词是否存在
public boolean search(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch – 'a';
if (node.children[index] == null) {
return false; // 路径中断，单词不存在
}
node = node.children[index];
}
return node.isEnd; // 必须是单词结尾才返回true
}
5. 查找前缀
查找前缀与查找单词几乎相同，只是最后不需要检查 isEnd。只要路径存在，就说明有单词以该前缀开头。
// 判断是否有单词以给定前缀开头
public boolean startsWith(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch – 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return true; // 前缀路径存在
}
6. 完整代码与测试
将上述代码整合成一个完整的 Trie 类，并编写一个简单的测试程序：
class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() {
children = new TrieNode[26];
isEnd = false;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch – 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch – 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch – 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return true;
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
System.out.println(trie.search("cat")); // true
System.out.println(trie.search("can")); // false
System.out.println(trie.startsWith("ca")); // true
System.out.println(trie.startsWith("do")); // true
System.out.println(trie.startsWith("c")); // true
System.out.println(trie.startsWith("x")); // false
}
}
运行上述代码，你会得到预期的输出。字典树的基础实现就完成了。
7. 扩展思考
-
支持更多字符：如果字符集较大（如包含大写字母、数字等），可以用 HashMap<Character, TrieNode> 来存储子节点，灵活但稍慢。
-
删除单词：删除操作稍微复杂，需要递归删除节点，并注意如果节点还有子节点则不能删除。通常我们只标记 isEnd 为 false，不实际删除节点，以简化实现。
-
自动补全：在 startsWith 的基础上，可以进一步收集所有以该前缀开头的单词，实现简单的输入提示功能。
（二）并查集（Union-Find）
1. 什么是并查集？
并查集是一种用于处理不相交集合的合并与查询问题的数据结构。它支持两种操作：
-
查找（Find）：查询某个元素属于哪个集合（通常返回集合的代表元素）。
-
合并（Union）：将两个元素所在的集合合并成一个集合。
并查集广泛应用于图论中的连通分量判断、最小生成树（Kruskal算法）、社交网络中的朋友圈等场景。
形象理解：假设有n个人，一开始每个人都自成一个圈子（集合）。如果两个人成为朋友，就把他们的圈子合并。我们需要快速判断任意两个人是否在同一个圈子中。并查集正是为解决这类问题而生。
2. 并查集的表示
我们通常用数组来表示并查集。数组的每个下标代表一个元素，数组的值指向它的父节点。如果一个元素的父节点是它自己，那么它就是该集合的代表（根）。
例如，初始状态：parent[i] = i，表示每个元素自成一个集合。
3. 查找操作（Find）
查找元素 x 的根节点。通常递归地找父节点，直到 parent[x] == x。代码很简单：
public int find(int x) {
if (parent[x] != x) {
return find(parent[x]);
}
return x;
}
但这种写法没有优化，每次查找都可能沿着链走到根，最坏情况下树可能退化成链表，时间复杂度O(n)。
4. 路径压缩
路径压缩是并查集最重要的优化之一。它的思想是：在查找某个元素时，顺便把路径上的所有节点直接挂到根节点下，这样下次再查找这些节点时就能一步到位。实现非常简单，只需在递归返回时更新父节点指向。
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
经过路径压缩，每次查找的平均时间复杂度接近O(1)（反阿克曼函数，增长极慢）。
5. 合并操作（Union）
合并两个元素所在的集合：先分别找到它们的根节点，如果根不同，则将其中一个根指向另一个根。为了尽量保持树平衡，可以引入按秩合并（秩可以是树的高度或节点数），将较小的树合并到较大的树上，避免树过高。
我们通常用一个 rank 数组记录每棵树的深度（近似）。初始时每个元素的秩为0。
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
// 按秩合并：将秩小的根挂到秩大的根下
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
// 秩相等，随便挂一个，并增加秩
parent[rootY] = rootX;
rank[rootX]++;
}
}
6. 完整实现
下面给出一个完整的并查集类，包含路径压缩和按秩合并。
public class UnionFind {
private int[] parent;
private int[] rank; // 秩，表示树的高度上界
// 初始化，每个元素自成一派
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// 查找根节点（带路径压缩）
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并两个集合
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
// 按秩合并
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
// 判断两个元素是否连通
public boolean connected(int x, int y) {
return find(x) == find(y);
}
// 可选：获取当前集合数量
public int count() {
int cnt = 0;
for (int i = 0; i < parent.length; i++) {
if (parent[i] == i) cnt++;
}
return cnt;
}
}
7. 测试示例
我们用一个小例子来验证并查集的功能：假设有5个人（0到4），我们建立一些朋友关系，然后查询他们是否连通。
public class UnionFindDemo {
public static void main(String[] args) {
UnionFind uf = new UnionFind(5);
uf.union(0, 1);
uf.union(2, 3);
uf.union(1, 4);
System.out.println(uf.connected(0, 4)); // true (0-1-4)
System.out.println(uf.connected(0, 2)); // false
System.out.println(uf.connected(3, 2)); // true (2-3直接连通)
System.out.println("当前集合数量: " + uf.count()); // 2个集合: {0,1,4} 和 {2,3}
}
}
输出：
true false true 当前集合数量: 2
8. 深入理解路径压缩与按秩合并
-
路径压缩的作用是使树扁平化，大大降低后续查找的时间。它实际上是一种“自优化”行为，每次查找都会让树更平。
-
按秩合并的作用是让树尽量平衡，避免生成过深的树。两者结合，使得并查集的操作几乎为常数时间。
注意：路径压缩后，树的实际高度可能小于 rank 中记录的值，但 rank 仍然可以作为合并时的一个参考，不影响正确性。
