在樹這種數據結構中，有時候需要知道兩個節點的最近的公共祖先。
我們經常只需要知道某兩個節點的公共祖先，這樣最簡單的遞歸算法即可解決問題，分析如下：
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 閱讀(3190)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎