在樹這種數(shù)據(jù)結(jié)構(gòu)中，有時(shí)候需要知道兩個(gè)節(jié)點(diǎn)的最近的公共祖先。
我們經(jīng)常只需要知道某兩個(gè)節(jié)點(diǎn)的公共祖先，這樣最簡單的遞歸算法即可解決問題，分析如下：
1、對(duì)于當(dāng)前節(jié)點(diǎn)t，如果其是要查詢的兩個(gè)節(jié)點(diǎn)a和b中的一個(gè)，則直接返回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
算法結(jié)果即最近公共祖先節(jié)點(diǎn)在result中。
不過有時(shí)候我們的查詢量很大，針對(duì)同一顆樹有成百上千次查詢，這樣上面的算法效率就太低了，不過不要急，Tarjan算法派上用場了~
Tarjan算法是一種離線算法，意思就是給定一棵樹，然后給定若干詢問，先緩存所有詢問，然后再一次性的給出所有詢問的回答。
設(shè)定如下數(shù)據(jù)結(jié)構(gòu)：
1 vector<int> tree[MAX_NODE];
2 vector<int> query[MAX_QUERY];
由上面可知，樹是有鄰接表存儲(chǔ)的(這樣也是為了節(jié)約空間)。對(duì)于查詢，如(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)是并查集（不知道并查集？去翻翻《算法導(dǎo)論》吧！）的標(biāo)準(zhǔn)操作，函數(shù)功能分別是尋找x的根節(jié)點(diǎn)；合并x和y這兩棵樹，將y的根節(jié)點(diǎn)的父指針指向x。
核心操作當(dāng)然是LCA_Tarjan(u)了。它的思想如下：
1、看遞歸就知道其實(shí)還是深度遍歷這棵樹；
2、首先使當(dāng)前節(jié)點(diǎn)u的父指針指向自己；
3、處理u的所有孩子節(jié)點(diǎn)，每處理完一個(gè)孩子節(jié)點(diǎn)就讓孩子節(jié)點(diǎn)的父指針指向u，即將孩子節(jié)點(diǎn)所在的集合與u的集合合并；
4、u的全部孩子處理完畢則將u標(biāo)記為處理結(jié)束，即checked[u] = 1;
5、處理所有和u相關(guān)的詢問，比如query[u][i] = v，則如果v已經(jīng)被處理結(jié)束，則u和v必然處在一棵并查集樹上，并且這棵樹的根節(jié)點(diǎn)一定是他們的公共祖先(為什么？畫圖找實(shí)例然后手動(dòng)運(yùn)行一遍不難理解，因?yàn)?span style="color: #ff0000">每個(gè)節(jié)點(diǎn)(比如為x)運(yùn)行完之后就將x的父指針指向它的父親(這時(shí)父親節(jié)點(diǎn)的父指針依然指向自己)，然后再去運(yùn)行x的兄弟節(jié)點(diǎn)，這時(shí)兄弟節(jié)點(diǎn)下的某個(gè)節(jié)點(diǎn)(比如y)如果在查詢中，且查詢?nèi)绻『檬?y, x的子孫)，則x所在并查集樹中的根節(jié)點(diǎn)一定是x的父節(jié)點(diǎn)，而這個(gè)父節(jié)點(diǎn)也是y的祖先，因此可知(y, x的子孫)的祖先一定包含x的父節(jié)點(diǎn)，由上面過程知道不能可包含比x的父節(jié)點(diǎn)更低的祖先節(jié)點(diǎn)，因此x的祖先節(jié)點(diǎn)必然是(y, x的子孫)的最近公共祖先)；這樣說必然很難理解，不過找個(gè)真正的實(shí)例運(yùn)行一遍就一目了然了~
posted on 2011-05-12 21:42
myjfm 閱讀(3163)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)