在计算机领域里，树结构是一种特别常见的数据结构，像文件系统、数据库索引等地方都会用到它。在处理树结构的时候，经常会碰到需要找出两个节点最近公共祖先的问题。今天咱就来聊聊两种能快速求解树节点最近公共祖先的方法：倍增法和 Tarjan 离线算法。
一、树和最近公共祖先问题
咱们先简单了解一下树。树就像是现实生活中的大树，有一个根节点，从根节点开始不断分支，每个分支又可以有自己的子分支。树里的每个元素都叫节点，节点和节点之间的连接叫边。
那什么是最近公共祖先问题呢？简单来说，就是在树里找两个节点，然后找出离它们最近的共同祖先节点。比如说，在一个家族树里，你和你的堂兄弟，你们最近的共同祖先可能就是你们的爷爷。
举个例子，有这样一棵树：
# Python 示例
# 定义树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 构建一个简单的树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
在这棵树里，如果要找节点 4 和节点 5 的最近公共祖先，那就是节点 2。
二、倍增法
原理
倍增法的核心思想就是利用二进制的特性，通过预先计算每个节点的 2^i 级祖先，这样在查找最近公共祖先的时候，就可以快速地跳跃，减少查找的次数。
步骤
- 先进行深度优先搜索（DFS），记录每个节点的深度和父节点。
- 预处理每个节点的 2^i 级祖先。
- 对于要查找的两个节点，先让它们跳到同一深度。
- 然后一起向上跳，直到找到最近公共祖先。
示例代码
# Python 示例
# 定义树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 深度优先搜索，记录深度和父节点
def dfs(node, parent, depth, depth_dict, parent_dict):
depth_dict[node] = depth
parent_dict[node] = parent
if node.left:
dfs(node.left, node, depth + 1, depth_dict, parent_dict)
if node.right:
dfs(node.right, node, depth + 1, depth_dict, parent_dict)
# 预处理每个节点的 2^i 级祖先
def preprocess(parent_dict, n):
ancestors = {}
for node in parent_dict:
ancestors[node] = [None] * n
ancestors[node][0] = parent_dict[node]
for j in range(1, n):
for node in parent_dict:
if ancestors[node][j - 1]:
ancestors[node][j] = ancestors[ancestors[node][j - 1]][j - 1]
return ancestors
# 查找最近公共祖先
def lca(u, v, depth_dict, ancestors):
if depth_dict[u] < depth_dict[v]:
u, v = v, u
# 让 u 和 v 跳到同一深度
diff = depth_dict[u] - depth_dict[v]
for i in range(20):
if (diff >> i) & 1:
u = ancestors[u][i]
if u == v:
return u
# 一起向上跳
for i in range(19, -1, -1):
if ancestors[u][i] != ancestors[v][i]:
u = ancestors[u][i]
v = ancestors[v][i]
return ancestors[u][0]
# 构建树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 初始化深度和父节点字典
depth_dict = {}
parent_dict = {}
dfs(root, None, 0, depth_dict, parent_dict)
# 预处理祖先信息
ancestors = preprocess(parent_dict, 20)
# 查找节点 4 和节点 5 的最近公共祖先
node4 = root.left.left
node5 = root.left.right
result = lca(node4, node5, depth_dict, ancestors)
print(f"节点 4 和节点 5 的最近公共祖先是: {result.val}")
优缺点
优点：预处理之后，每次查询的时间复杂度是 O(log n)，效率比较高，适合多次查询的场景。 缺点：预处理需要 O(n log n) 的时间和空间，对于单次查询来说，可能会有一些浪费。
注意事项
- 预处理的数组大小要根据树的节点数量来确定，一般设为 log2(n) 向上取整。
- 在代码实现中，要注意边界条件，比如节点的深度和祖先的计算。
三、Tarjan 离线算法
原理
Tarjan 离线算法是一种离线算法，也就是说，它需要先把所有的查询都收集起来，然后一次性处理。它的核心思想是利用并查集来实现。在深度优先搜索的过程中，把已经访问过的节点合并到同一个集合里，当遇到查询时，根据并查集的信息来找出最近公共祖先。
步骤
- 初始化并查集。
- 进行深度优先搜索，在搜索过程中处理查询。
- 对于每个查询，如果两个节点都已经访问过，就通过并查集找出它们的最近公共祖先。
示例代码
# Python 示例
# 定义树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 并查集类
class UnionFind:
def __init__(self, n):
self.parent = list(range(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:
self.parent[root_x] = root_y
# Tarjan 离线算法
def tarjan(node, queries, uf, visited, result):
visited.add(node)
for query in queries:
u, v = query
if u == node and v in visited:
lca = uf.find(v)
result[query] = lca
elif v == node and u in visited:
lca = uf.find(u)
result[query] = lca
if node.left:
tarjan(node.left, queries, uf, visited, result)
uf.union(node.left.val, node.val)
if node.right:
tarjan(node.right, queries, uf, visited, result)
uf.union(node.right.val, node.val)
# 构建树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 初始化并查集
uf = UnionFind(6)
# 定义查询
queries = [(4, 5)]
visited = set()
result = {}
# 调用 Tarjan 算法
tarjan(root, queries, uf, visited, result)
# 输出结果
for query, lca in result.items():
print(f"节点 {query[0]} 和节点 {query[1]} 的最近公共祖先是: {lca}")
优缺点
优点：时间复杂度是 O(n + m)，其中 n 是树的节点数，m 是查询的数量，对于大量查询的场景非常高效。 缺点：需要一次性收集所有的查询，不适合在线查询的场景。
注意事项
- 并查集的实现要注意路径压缩，这样可以提高查找的效率。
- 在处理查询时，要确保两个节点都已经访问过。
四、应用场景
数据库索引
在数据库的 B 树索引中，经常需要查找两个节点的最近公共祖先，以便进行范围查询等操作。
文件系统
在文件系统中，查找两个文件或目录的最近公共祖先，可以帮助进行权限管理和路径计算。
生物信息学
在生物进化树中，查找两个物种的最近公共祖先，可以研究物种的进化关系。
五、总结
倍增法和 Tarjan 离线算法都是解决最近公共祖先问题的有效方法。倍增法适合多次查询的场景，它通过预处理节点的祖先信息，在查询时可以快速跳跃，时间复杂度是 O(log n)。Tarjan 离线算法适合大量查询的场景，它利用并查集在深度优先搜索的过程中处理查询，时间复杂度是 O(n + m)。在实际应用中，要根据具体的场景和需求来选择合适的算法。
评论