在树这种数据结构中，有时候需要知道两个节点的最近的公共祖先。
我们经常只需要知道某两个节点的公共祖先，这样最简单的递归算法即可解决问题，分析如下：
1、对于当前节点t，如果其是要查询的两个节点a和b中的一个，则直接返回t；
2、否则如果a和b都在t的左子树或者右子树中，则递归左子树或右子树
3、直到a和b分属t的左子树与右子树为止。
后序遍历二叉树的递归算法如下：
1 typedef struct lca
2 {
3 int data;
4 struct lca *left, *right;
5 } lca;
6
7 int LCA(lca *root, lca *a, lca *b, lca **result)
8 {
9 int l, r;
10 if (root == NULL)
11 return 0;
12 if ((l = LCA(root->left, a, b, result)) == 2) return 2;
13 if ((r = LCA(root->right, a, b, result)) == 2) return 2;
14 if (l + r == 2) { *result = root; return 2; }
15 if (root == a || root == b) {
16 if (l + r == 1) { *result = root; return 2; }
17 return 1;
18 }
19 return l + r;
20 }
21
算法结果即最近公共祖先节点在result中。
不过有时候我们的查询量很大，针对同一颗树有成百上千次查询，这样上面的算法效率就太低了，不过不要急，Tarjan算法派上用场了~
Tarjan算法是一种离线算法，意思就是给定一棵树，然后给定若干询问，先缓存所有询问，然后再一次性的给出所有询问的回答。
设定如下数据结构：
1 vector<int> tree[MAX_NODE];
2 vector<int> query[MAX_QUERY];
由上面可知，树是有邻接表存储的(这样也是为了节约空间)。对于查询，如(3, 5)，query[3][5] 和query[5][3]都需要被置为1。
先看模板吧：
1 int find(int x)
2 {
3 if (x == parent[x])
4 {
5 return x;
6 }
7 else
8 {
9 parent[x] = find(parent[x]);
10 }
11
12 return parent[x];
13 }
14
15 void merge(int x, int y)
16 {
17 parent[y] = x;
18 }
19
20 void LCA_Tarjan(int u)
21 {
22 int i;
23 parent[u] = u;
24
25 for (i = 0; i < tree[u].size(); ++i)
26 {
27 LCA_Tarjan(tree[u][i]);
28 merge(u, tree[u][i]);
29 anscestor[find(u)] = u;
30 }
31
32 checked[u] = 1;
33
34 for (i = 0; i < query[u].size(); ++i)
35 {
36 if (checked[query[u][i]] == 1)
37 {
38 res = anscestor[find(query[u][i])];
39 }
40 }
41 }
42
其中find(x)、merge(x, y)是并查集（不知道并查集？去翻翻《算法导论》吧！）的标准操作，函数功能分别是寻找x的根节点；合并x和y这两棵树，将y的根节点的父指针指向x。
核心操作当然是LCA_Tarjan(u)了。它的思想如下：
1、看递归就知道其实还是深度遍历这棵树；
2、首先使当前节点u的父指针指向自己；
3、处理u的所有孩子节点，每处理完一个孩子节点就让孩子节点的父指针指向u，即将孩子节点所在的集合与u的集合合并；
4、u的全部孩子处理完毕则将u标记为处理结束，即checked[u] = 1;
5、处理所有和u相关的询问，比如query[u][i] = v，则如果v已经被处理结束，则u和v必然处在一棵并查集树上，并且这棵树的根节点一定是他们的公共祖先(为什么？画图找实例然后手动运行一遍不难理解，因为每个节点(比如为x)运行完之后就将x的父指针指向它的父亲(这时父亲节点的父指针依然指向自己)，然后再去运行x的兄弟节点，这时兄弟节点下的某个节点(比如y)如果在查询中，且查询如果恰好是(y, x的子孙)，则x所在并查集树中的根节点一定是x的父节点，而这个父节点也是y的祖先，因此可知(y, x的子孙)的祖先一定包含x的父节点，由上面过程知道不能可包含比x的父节点更低的祖先节点，因此x的祖先节点必然是(y, x的子孙)的最近公共祖先)；这样说必然很难理解，不过找个真正的实例运行一遍就一目了然了~
posted on 2011-05-12 21:42
myjfm 阅读(3156)
评论(0) 编辑 收藏 引用 所属分类:
算法基础