最近公共祖先（Least Common Ancestors，LCA）问题详解 |
您所在的位置：网站首页 › 制作家谱有趣吗英语 › 最近公共祖先（Least Common Ancestors，LCA）问题详解 |
最近公共祖先（Least Common Ancestors，LCA）问题详解
|
问题描述与分析
求有根树的任意两个节点的最近公共祖先。 解答这个问题之前，咱们得先搞清楚到底什么是最近公共祖先。最近公共祖先简称LCA（Lowest Common Ancestor），所谓LCA，是当给定一个有根树T时，对于任意两个结点u、v，找到一个离根最远的结点x，使得x同时是u和v的祖先，x 便是u、v的最近公共祖先。（参见：http://en.wikipedia.org/wiki/Lowest_common_ancestor ）原问题涵盖一般性的有根树，本文为了简化，多使用二叉树来讨论。 举个例子，如针对下图所示的一棵普通的二叉树来讲：
结点3和结点4的最近公共祖先是结点2，即LCA（3，4）=2 。在此，需要注意到当两个结点在同一棵子树上的情况，如结点3和结点2的最近公共祖先为2，即 LCA（3，2）=2。同理：LCA（5，6）=4，LCA（6，10）=1。 明确了题意，咱们便来试着解决这个问题。直观的做法，可能是针对是否为二叉查找树分情况讨论，这也是一般人最先想到的思路。除此之外，还有所谓的Tarjan算法、倍增算法、以及转换为RMQ问题（求某段区间的极值）。后面这几种算法相对高级，不那么直观，但思路比较有启发性，了解一下也有裨益。 解法一：暴力对待 1.1、是二叉查找树在当这棵树是二叉查找树的情况下，如下图：
那么从树根开始： 如果当前结点t 大于结点u、v，说明u、v都在t 的左侧，所以它们的共同祖先必定在t 的左子树中，故从t 的左子树中继续查找；如果当前结点t 小于结点u、v，说明u、v都在t 的右侧，所以它们的共同祖先必定在t 的右子树中，故从t 的右子树中继续查找；如果当前结点t 满足 u right) { int temp = left; left = right; right = temp; } while (true) { //如果t小于u、v，往t的右子树中查找 if (t.value < left) { t = t.right; //如果t大于u、v，往t的左子树中查找 } else if (t.value > right) { t = t.left; } else { return t.value; } } } 1.2、不是二叉查找树但如果这棵树不是二叉查找树，只是一棵普通的二叉树呢？如果每个结点都有一个指针指向它的父结点，于是我们可以从任何一个结点出发，得到一个到达树根结点的单向链表。因此这个问题转换为两个单向链表的第一个公共结点。 此外，如果给出根节点，LCA问题可以用递归很快解决。而关于树的问题一般都可以转换为递归（因为树本来就是递归描述），参考代码如下： node* getLCA(node* root, node* node1, node* node2) { if(root == null) return null; if(root== node1 || root==node2) return root; node* left = getLCA(root->left, node1, node2); node* right = getLCA(root->right, node1, node2); // node1 和 node2 不存在祖先关系 if(left != null && right != null) return root; // node1 和 node2 其中一个是另一个的祖先 else if(left != null) return left; else if (right != null) return right; else return null; }不论是针对普通的二叉树，还是针对二叉查找树，上面的解法有一个很大的弊端就是：如需N 次查询，则总体复杂度会扩大N 倍，故这种暴力解法仅适合一次查询，不适合多次查询。 接下来的解法，将不再区别对待是否为二叉查找树，而是一致当做是一棵普通的二叉树。总体来说，由于可以把LCA问题看成是询问式的，即给出一系列询问，程序对每一个询问尽快做出反应。故处理这类问题一般有两种解决方法： 一种是在线算法，相当于循序渐进处理；另外一种则是离线算法，如Tarjan算法，相当于一次性批量处理，一开始就知道了全部查询，只待询问。 解法二：Tarjan算法如上文末节所述，不论咱们所面对的二叉树是二叉查找树，或不是二叉查找树，都可以把求任意两个结点的最近公共祖先，当做是查询的问题，如果是只求一次，则是单次查询；如果要求多个任意两个结点的最近公共祖先，则相当于是批量查询。 涉及到批量查询的时候，咱们可以借鉴离线处理的方式，这就引出了解决此LCA问题的Tarjan离线算法。 2.1、什么是Tarjan算法Tarjan算法 （以发现者Robert Tarjan命名）是一个在图中寻找强连通分量的算法。算法的基本思想为：任选一结点开始进行深度优先搜索dfs（若深度优先搜索结束后仍有未访问的结点，则再从中任选一点再次进行）。搜索过程中已访问的结点不再访问。搜索树的若干子树构成了图的强连通分量。 应用到咱们要解决的LCA问题上，则是：对于新搜索到的一个结点u，先创建由u构成的集合，再对u的每颗子树进行搜索，每搜索完一棵子树，这时候子树中所有的结点的最近公共祖先就是u了。 举一个例子，如下图（不同颜色的结点相当于不同的集合）：
假设遍历完10的孩子,要处理关于10的请求了，取根节点到当前正在遍历的节点的路径为关键路径,即1-3-8-10，集合的祖先便是关键路径上距离集合最近的点。 比如： 1，2，5，6为一个集合,祖先为1，集合中点和10的LCA为13，7为一个集合，祖先为3，集合中点和10的LCA为38，9，11为一个集合，祖先为8，集合中点和10的LCA为810，12为一个集合，祖先为10，集合中点和10的LCA为10得出的结论便是：LCA(u,v)便是根至u的路径上到节点v最近的点。 2.2、Tarjan算法如何而来但关键是 Tarjan算法是怎么想出来的呢？再给定下图，你是否能看出来：分别从结点1的左右子树当中，任取一个结点，设为u、v，这两个任意结点u、v的最近公共祖先都为1。 
于此，我们可以得知：若两个结点u、v分别分布于某节点t 的左右子树，那么此节点 t即为u和v的最近公共祖先。更进一步，考虑到一个节点自己就是LCA的情况，得知： 若某结点t 是两结点u、v的祖先之一，且这两结点并不分布于该结点t 的一棵子树中，而是分别在结点t 的左子树、右子树中，那么该结点t 即为两结点u、v的最近公共祖先。这个定理就是Tarjan算法的基础。 一如上文1.1节我们得到的结论：“如果当前结点t 满足 u tree = tree; } map calLCA(vector& query) { map queryMap; map result; for (int i =0; i< query.size(); i++) { int u = query[i].first; int v = query[i].second; set temp; if (queryMap.count(u) == 0) queryMap[u] = temp; if (queryMap.count(v) == 0) queryMap[v] = temp; queryMap[u].insert(v); queryMap[v].insert(u); } tarjan(0, queryMap, result); return result; } void tarjan(int u, map& queryMap, map& result) { fatSet.father[u] = u; hasVisit[u] = true; cout |
【本文地址】
今日新闻 |
推荐新闻 |