字典树与家族谱 —— Trie与并查集
你在手机上打字，刚敲了”alg”三个字母，输入法就自动建议”algorithm”——这背后是Trie在工作。你在社交网络上查看”你们有5个共同好友”——这背后是并查集在工作。两种看似无关的数据结构，各自解决着一类独特的问题。
📋 开篇自测：你已经知道多少？
- 如果有100万个英文单词，如何高效地判断某个字符串是否是其中某个单词的前缀？用哈希表可以吗？
- 社交网络中有1亿用户和10亿条好友关系，如何快速判断两个人是否在同一个朋友圈内？
- “路径压缩”和”按秩合并”分别解决了并查集的什么问题？
一、Trie——为前缀而生的树
从输入法说起
你有没有想过手机输入法的自动补全是怎么实现的？
假设词库里有”apple”、“app”、“application”、“banana”、“band”这几个词。当你输入”app”时，输入法要做两件事：
- 判断”app”本身是不是一个完整的词——是的
- 找出所有以”app”开头的词——“apple”、“application”
如果用哈希表存所有单词，判断一个完整词是否存在很快（O(1)），但找出所有以某个前缀开头的词就困难了——你得遍历所有单词逐个检查前缀。
如果用排序数组+二分查找呢？能找到前缀的起始位置，但维护有序性的代价很高。
Trie（前缀树/字典树）就是为这类”前缀查询”问题量身定做的数据结构。它的名字来自Retrieval（检索），读作”try”。
Trie的结构
Trie是一棵多叉树，每个节点代表一个字符，从根到某个节点的路径拼起来就是一个字符串前缀。用一个标记来标识某条路径是否构成一个完整的单词。
存储单词: "app", "apple", "application", "banana", "band"
(root)
/ \
a b
| |
p a
| |
p* n
/ \ | \
l l a d*
| | |
e* i n
| |
c a*
|
a
|
t
|
i
|
o
|
n*
注：带 * 号的表示该节点是一个完整单词的结尾关键特征：公共前缀只存储一次。 “app”、“apple”、“application”共享前三个字符”a-p-p”的路径，不像哈希表那样每个词独立存储完整字符串。这既节省空间，又让前缀查询变得天然高效。
二、从零实现一棵Trie
每个Trie节点包含两样东西：
- 一个映射（children），记录”下一个字符”对应的子节点
- 一个布尔值（isEnd），标记当前节点是否是某个单词的结尾
class TrieNode:
def __init__(self):
self.children = {} # 字符 -> 子节点
self.is_end = False # 是否是单词的结尾
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
"""插入一个单词"""
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True # 标记单词结尾
def search(self, word):
"""查找一个完整单词是否存在"""
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end # 必须是完整单词
def starts_with(self, prefix):
"""判断是否有某个前缀"""
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True # 只要路径存在，就是合法前缀
def find_all_with_prefix(self, prefix):
"""找出所有以某个前缀开头的单词"""
node = self.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
# 从当前节点开始，用DFS收集所有完整单词
results = []
self._dfs(node, prefix, results)
return results
def _dfs(self, node, path, results):
if node.is_end:
results.append(path)
for ch, child in node.children.items():
self._dfs(child, path + ch, results)
# 验证
trie = Trie()
for w in ['app', 'apple', 'application', 'banana', 'band']:
trie.insert(w)
print(trie.search('app')) # True
print(trie.search('appl')) # False（不是完整单词）
print(trie.starts_with('app')) # True
print(trie.starts_with('ban')) # True
print(trie.starts_with('cat')) # False
print(trie.find_all_with_prefix('app')) # ['app', 'apple', 'application']
print(trie.find_all_with_prefix('ban')) # ['banana', 'band']Trie操作的时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 插入 | O(m) | m是单词长度 |
| 查找完整单词 | O(m) | m是单词长度 |
| 前缀匹配 | O(m) | m是前缀长度 |
| 找所有前缀匹配词 | O(m + k) | k是匹配到的字符总数 |
注意：这里的复杂度和词库中有多少单词无关，只和你查找的字符串长度有关。这就是Trie的威力——词库从1万扩大到1000万，查找”app”的速度一样快。
🤔 想一想 Trie节点的children用的是对象（哈希映射）。如果确定只有26个小写字母，用一个长度为26的数组代替会怎样？有什么优缺点？
三、Trie的实际应用
应用1：自动补全
搜索引擎的搜索框、IDE的代码补全、手机输入法——它们的核心逻辑都可以用Trie来实现。上面实现的findAllWithPrefix就是自动补全的基础。
# 简易搜索建议系统
class SearchSuggest:
def __init__(self, words):
self.trie = Trie()
for w in words:
self.trie.insert(w.lower())
def suggest(self, input_str, max_results=5):
all_matches = self.trie.find_all_with_prefix(input_str.lower())
return all_matches[:max_results] # 只返回前几个
engine = SearchSuggest([
'javascript', 'java', 'json', 'jquery',
'python', 'pytorch', 'pandas',
'react', 'redux', 'rust'
])
print(engine.suggest('ja')) # ['java', 'javascript']
print(engine.suggest('py')) # ['python', 'pytorch']
print(engine.suggest('r')) # ['react', 'redux', 'rust']应用2：拼写检查
输入一个词，判断它是否在词典中。如果不在，找出最相似的候选词。Trie可以高效地完成第一步，也可以为第二步提供基础（结合编辑距离算法）。
应用3：IP路由的最长前缀匹配
网络路由器收到一个IP包后，需要在路由表中找到与目标IP最长匹配的前缀，决定往哪条线路转发。这正是Trie最擅长的事情。
四、并查集——回答”你们是一伙的吗”
从社交网络说起
假设有6个人：小明、小红、小华、小刚、小丽、小王。已知的朋友关系是：
- 小明 和 小红 是朋友
- 小红 和 小华 是朋友
- 小刚 和 小丽 是朋友
现在问：小明和小华是不是同一个朋友圈的？小明和小刚呢？
朋友圈1: 小明 -- 小红 -- 小华
朋友圈2: 小刚 -- 小丽
朋友圈3: 小王（独自一人）小明和小华在同一个圈子里（通过小红间接认识），小明和小刚不在同一个圈子里。
这类问题的本质是：给定一堆**合并（union）操作，能否快速查找（find）**两个元素是否属于同一个集合？
**并查集（Union-Find / Disjoint Set Union）**就是为这类问题而生的。它只做两件事：
- 合并（Union）： 把两个元素所在的集合合并成一个
- 查找（Find）： 判断一个元素属于哪个集合（返回集合的”代表元素”）
并查集的直觉——家族族谱
你可以把每个集合想象成一个家族，每个家族有一个”族长”。
- 查找就是沿着族谱往上追溯，找到你的族长是谁。两个人的族长相同，说明是同一个家族。
- 合并就是让一个家族的族长认另一个家族的族长为新族长，两家合并成一家。
五、从零实现并查集
基础版本
每个元素有一个”父节点”指针。初始时，每个元素的父节点指向自己——每个人都是自己家族的族长。
class UnionFind:
def __init__(self, n):
# parent[i] 表示元素i的父节点
# 初始时每个元素的父节点是自己
self.parent = list(range(n))
self.count = n # 连通分量（集合）的数量
def find(self, x):
"""查找元素x的根节点（族长）"""
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
"""合并元素x和y所在的集合"""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return # 已经在同一集合
self.parent[root_x] = root_y # 让x的族长认y的族长为新族长
self.count -= 1
def connected(self, x, y):
"""判断x和y是否在同一集合"""
return self.find(x) == self.find(y)
# 验证（0=小明, 1=小红, 2=小华, 3=小刚, 4=小丽, 5=小王）
uf = UnionFind(6)
uf.union(0, 1) # 小明和小红是朋友
uf.union(1, 2) # 小红和小华是朋友
uf.union(3, 4) # 小刚和小丽是朋友
print(uf.connected(0, 2)) # True —— 小明和小华同一圈子
print(uf.connected(0, 3)) # False —— 小明和小刚不同圈子
print(uf.count) # 3 —— 共3个朋友圈问题来了——这棵树可能退化
如果合并操作恰好形成了一条链：
合并 0-1, 1-2, 2-3, 3-4:
0 -> 1 -> 2 -> 3 -> 4
find(0) 需要走4步才能找到根节点4最坏情况下，find操作退化成O(n)。这就像一个家族的族谱退化成了一条直线——要找族长得一代一代往上数，太慢了。
六、路径压缩——让族谱变”扁”
**路径压缩（Path Compression）**的想法很简单：既然我们只关心”族长是谁”，不关心中间隔了几代，那在find的过程中，顺手把沿途所有节点直接指向根节点就好了。
路径压缩前： 路径压缩后：
0 -> 1 -> 2 -> 3 -> 4 0 -> 4
1 -> 4
2 -> 4
3 -> 4一次find之后，路径上所有节点都直接连到根了，以后再查就是O(1)。
# 路径压缩版find（只需改一行代码）
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 递归压缩
return self.parent[x]这一行递归代码做了两件事：
- 找到根节点
- 把路径上每个节点的父指针直接指向根节点
就像你问太爷爷”咱家族长是谁”，太爷爷告诉你是老祖宗，然后你直接记住”老祖宗”，下次不用再问太爷爷了。
七、按秩合并——让高个子当族长
**按秩合并（Union by Rank）**解决的是另一个问题：合并两个集合时，该让谁的根成为新的根？
如果总是把高的树挂到矮的树下面，树会越来越高。反过来，让矮的树挂到高的树下面，就能保持整体较矮。
不优化的合并： 按秩合并：
（矮树挂到高树下，高度不变） 高树A作为根，矮树B挂上去
A B A
/ \ | => / \ \
x y z x y B
|
zclass UnionFindOptimized:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n # rank[i] 表示以i为根的树的高度上界
self.count = n
def find(self, x):
"""带路径压缩的查找"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""按秩合并"""
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
# 矮的树挂到高的树下面
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
# 等高时，任选一个，高度加1
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.count -= 1
def connected(self, x, y):
return self.find(x) == self.find(y)优化后的复杂度——近乎魔法
同时使用路径压缩和按秩合并后，每次操作的均摊时间复杂度是O(α(n))，其中α是阿克曼函数的反函数。这个函数增长极其缓慢——对于任何你能在实际中遇到的n（哪怕n是宇宙中原子的数量），α(n)都不超过5。
所以在实际应用中，可以认为每次find和union都是 常数时间O(1)。
| 版本 | find复杂度 | union复杂度 |
|---|---|---|
| 基础版 | O(n) 最坏 | O(n) 最坏 |
| + 路径压缩 | O(log n) 均摊 | O(log n) 均摊 |
| + 路径压缩 + 按秩合并 | O(α(n)) ≈ O(1) | O(α(n)) ≈ O(1) |
🤔 想一想 路径压缩会改变树的形状，这会不会影响按秩合并中rank的准确性？（提示：路径压缩后rank可能不再精确反映树的高度，但这不影响正确性——rank只是一个”高度上界”的估计。）
八、经典题目实战
题目1：朋友圈问题
问题： 有n个人，给定一组朋友关系对，求一共有多少个朋友圈？
这正是并查集的典型用例：每对朋友执行一次union，最后看有多少个不同的集合。
def find_circle_num(friendships, n):
uf = UnionFindOptimized(n)
for a, b in friendships:
uf.union(a, b)
return uf.count
# 5个人，3对朋友关系
# 初始5个集合，union(0,1)减到4，union(1,2)减到3，union(3,4)减到2
# 圈子1: {0,1,2}, 圈子2: {3,4}
print(find_circle_num([(0, 1), (1, 2), (3, 4)], 5)) # 2题目2：岛屿数量（并查集解法）
问题： 给定一个二维网格，其中’1’表示陆地，‘0’表示水。上下左右相邻的’1’构成一个岛屿。求岛屿的数量。
你可能见过用DFS/BFS解这道题。但并查集提供了另一种思路——把每个’1’看作一个独立的集合，然后把相邻的’1’合并，最后数有几个集合。
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
# 为每个格子分配一个编号: (r, c) -> r * cols + c
uf = UnionFindOptimized(rows * cols)
water_count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '0':
water_count += 1
continue
idx = r * cols + c
# 向右合并
if c + 1 < cols and grid[r][c + 1] == '1':
uf.union(idx, idx + 1)
# 向下合并
if r + 1 < rows and grid[r + 1][c] == '1':
uf.union(idx, idx + cols)
# 总集合数 - 水的数量 = 岛屿数量
return uf.count - water_count
grid = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
]
print(num_islands(grid)) # 3为什么只向右和向下合并就够了？ 因为我们是从左到右、从上到下遍历的。每个格子只需要看它右边和下面的邻居，左边和上面的在之前的遍历中已经处理过了。
题目3：最长连续序列
问题： 给定一个未排序的整数数组，找出最长的连续元素序列的长度。要求O(n)时间复杂度。
例如 [100, 4, 200, 1, 3, 2]，最长连续序列是 [1, 2, 3, 4]，长度为4。
并查集思路： 对于数组中的每个数num，如果num+1也在数组中，就把它们union到一起。最后找最大的集合。
def longest_consecutive(nums):
if not nums:
return 0
num_set = set(nums)
unique_nums = list(num_set)
index_map = {num: i for i, num in enumerate(unique_nums)}
# 带 size 追踪的并查集（在 UnionFindOptimized 基础上增加集合大小记录）
uf = UnionFindOptimized(len(unique_nums))
size = [1] * len(unique_nums) # size[root] 记录以 root 为代表元的集合大小
for num in unique_nums:
if num + 1 in num_set:
root_a = uf.find(index_map[num])
root_b = uf.find(index_map[num + 1])
if root_a != root_b:
uf.union(index_map[num], index_map[num + 1])
# 合并后将两个集合的大小累加到新的根上
new_root = uf.find(index_map[num])
size[new_root] = size[root_a] + size[root_b]
return max(size)
print(longest_consecutive([100, 4, 200, 1, 3, 2])) # 4
print(longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])) # 9⚠️ 常见误区
- 误区1：“Trie只能存英文单词” —— Trie可以存储任何字符序列。中文词语、URL路径、DNA序列都可以。只不过字符集越大，每个节点的children就越多，空间开销也越大。
- 误区2：“并查集的union总是O(1)” —— 基础版本的union可以是O(n)。只有加上路径压缩和按秩合并后，均摊才接近O(1)。面试时一定要提到这两个优化。
- 误区3：“并查集可以拆分集合” —— 标准并查集只支持合并，不支持拆分。如果你需要”断开”两个元素的关系，并查集就不适用了，需要考虑其他数据结构。
题目4：最小生成树（Kruskal算法）
在第8章中我们提到，Kruskal算法是并查集的经典应用。现在我们有了并查集这个武器，来实现它：
问题： 给定一个无向加权图，找出连接所有节点的最小总权重的边集合（即最小生成树）。
思路： 把所有边按权重从小到大排序，依次尝试加入。如果一条边连接的两个节点已经连通（在同一个集合中），就跳过它（否则会形成环）；如果还没连通，就加入这条边并合并两个集合。
def kruskal(n, edges):
"""Kruskal算法求最小生成树
n: 节点数（编号0到n-1）
edges: [(权重, 节点u, 节点v), ...]
返回: (最小总权重, 最小生成树的边列表)
"""
edges.sort() # 按权重排序
uf = UnionFindOptimized(n)
mst = []
total_weight = 0
for weight, u, v in edges:
if uf.find(u) != uf.find(v): # 不在同一集合，加入不会成环
uf.union(u, v)
mst.append((u, v, weight))
total_weight += weight
if len(mst) == n - 1: # 树有n-1条边，提前结束
break
return total_weight, mst
# 示例：5个城市之间的光缆铺设成本
edges = [
(1, 0, 1), (4, 0, 2), (3, 1, 2),
(2, 1, 3), (5, 2, 3), (7, 3, 4), (6, 2, 4)
]
cost, cables = kruskal(5, edges)
print(f"最小铺设成本: {cost}") # 13
print(f"需要铺设的线路: {cables}")九、Trie vs 并查集——两种思维方式
这两种数据结构解决的是完全不同类型的问题。了解它们的适用场景，能帮你在面试和工程中做出正确选择。
| 维度 | Trie（前缀树） | 并查集（Union-Find） |
|---|---|---|
| 解决的核心问题 | 字符串的前缀查询与匹配 | 元素之间的连通性/分组 |
| 核心操作 | insert、search、startsWith | find、union、connected |
| 底层结构 | 多叉树（每个节点对应一个字符） | 森林（用数组表示的多棵树） |
| 时间复杂度 | O(m)，m为字符串长度 | O(α(n)) ≈ O(1)，均摊 |
| 空间消耗 | 较大（每个节点存储children映射） | 很小（只需要一个parent数组） |
| 典型应用 | 自动补全、拼写检查、IP路由 | 朋友圈、岛屿计数、最小生成树 |
| 适用数据类型 | 字符串、序列数据 | 任何需要分组的元素集合 |
选择Trie的信号：
- 题目涉及”前缀”、“匹配”、“补全”、“词典”
- 需要在大量字符串中做高效检索
- 公共前缀能显著节省空间
选择并查集的信号：
- 题目涉及”连通”、“分组”、“圈子”、“是否属于同一类”
- 需要动态地合并集合
- 只需要判断关系，不需要存储具体路径
📝 掌握度自测
- 概念题： Trie的空间复杂度和什么因素有关？如果字符集很大（比如Unicode），Trie还适用吗？有什么优化方案？
- 手算题： 将单词 “cat”、“car”、“card”、“care”、“do”、“dog” 插入一棵空的Trie，画出最终的树形结构。
- 分析题： 并查集的路径压缩和按秩合并各自解决了什么问题？只用其中一个优化够不够？
- 编码题： 用Trie实现一个函数，判断给定的单词列表中是否存在这样的情况：某个单词是另一个单词的前缀。例如 [“app”, “apple”] 中 “app” 是 “apple” 的前缀，返回true。
- 设计题： 如果你在设计一个在线游戏，需要支持”创建公会”和”合并公会”的功能，并且能快速查询两个玩家是否在同一公会，你会怎么设计底层数据结构？
💡 自我评估
- 全部答对：Trie和并查集已经是你的工具箱里的利器了，可以自信地应对相关面试题。
- 答对3-4题：掌握良好，建议找几道LeetCode上的Trie和并查集题目练手。
- 答对1-2题：重新阅读并查集的”路径压缩”和”按秩合并”部分，这是理解并查集性能的关键。
- 全部答错：Trie和并查集都是比较专门化的数据结构，第一次接触时感到陌生很正常。建议先手动在纸上模拟操作过程，再回来看代码。
至此，本课程的所有知识章节已经全部结束。从复杂度分析到数组链表，从树与图到动态规划，从面试实战到堆、Trie、并查集——你已经建立起了一套完整的数据结构与算法知识体系。在结束篇中，让我们回望来路、梳理全景图，并为你的下一段算法之旅指明方向。
购买课程解锁全部内容
刷题到通关：数据结构与算法面试实战
¥29.90