最近公共祖先LCA问题（转）

2024-04-10 20:18
文章标签 问题 公共 lca 最近 祖先

本文主要是介绍最近公共祖先LCA问题（转），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文转载from：july

问题描述

求有根树的任意两个节点的最近公共祖先。

分析与解法

解答这个问题之前，咱们得先搞清楚到底什么是最近公共祖先。最近公共祖先简称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 

//copyright@eriol 2011  
//modified by July 2014  
public int query(Node t, Node u, Node v) {    int left = u.value;    int right = v.value;    //二叉查找树内，如果左结点大于右结点，不对，交换  if (left > 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问题可以用递归很快解决。而关于树的问题一般都可以转换为递归（因为树本来就是递归描述），参考代码如下：

//copyright@allantop 2014-1-22-20:01  
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);  if(left != null && right != null)  return root;  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为1
3，7为一个集合，祖先为3，集合中点和10的LCA为3
8，9，11为一个集合，祖先为8，集合中点和10的LCA为8
10，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

2.3、Tarjan算法流程

Tarjan算法流程为：

Procedure dfs（u）；begin设置u号节点的祖先为u若u的左子树不为空，dfs（u - 左子树）；若u的右子树不为空，dfs（u - 右子树）；访问每一条与u相关的询问u、v-若v已经被访问过，则输出v当前的祖先t（t即u,v的LCA）标记u为已经访问，将所有u的孩子包括u本身的祖先改为u的父亲end

普通的dfs 不能直接解决LCA问题，故Tarjan算法的原理是dfs + 并查集，它每次把两个结点对的最近公共祖先的查询保存起来，然后dfs 更新一次。如此，利用并查集优越的时空复杂度，此算法的时间复杂度可以缩小至O(n＋Q)，其中，n为数据规模，Q为询问个数。

解法三：转换为RMQ问题

解决此最近公共祖先问题的还有一个算法，即转换为RMQ问题，用Sparse Table（简称ST）算法解决。

3.1、什么是RMQ问题

RMQ，全称为Range Minimum Query，顾名思义，则是区间最值查询，它被用来在数组中查找两个指定索引中最小值的位置。即RMQ相当于给定数组A[0, N-1]，找出给定的两个索引如 i、j 间的最小值的位置。

假设一个算法预处理时间为 f(n)，查询时间为g(n)，那么这个算法复杂度的标记为

3.2、如何解决RMQ问题

3.2.1、Trivial algorithms for RMQ

下面，我们对对每一对索引(i, j)，将数组中索引i 和 j 之间最小值的位置 RMQA(i, j) 存储在M[0, N-1][0, N-1]表中。 RMQA(i, j) 有不同种计算方法，你会看到，随着计算方法的不同，它的时空复杂度也不同：

普通的计算将得到一个 

//copyright@  
//modified by July 2014  
void process1(int M[MAXN][MAXN], int A[MAXN], int N)  
{  int i, j;  for (i =0; i < N; i++)  M[i][i] = i;  for (i = 0; i < N; i++)  for (j = i + 1; j < N; j++)  //若前者小于后者，则把后者的索引值付给M[i][j]  if (A[M[i][j - 1]] < A[j])  M[i][j] = M[i][j - 1];  //否则前者的索引值付给M[i][j]  else  M[i][j] = j;  
}

一个比较有趣的点子是把向量分割成sqrt(N)大小的段。我们将在M[0,sqrt(N)-1]为每一个段保存最小值的位置。如此，M可以很容易的在O(N)时间内预处理。
这里写图片描述

一个更好的方法预处理RMQ 是对2^k 的长度的子数组进行动态规划。我们将使用数组M[0, N-1][0, logN]进行保存，其中M[ i ][ j ] 是以i 开始，长度为 2^j 的子数组的最小值的索引。这就引出了咱们接下来要介绍的Sparse Table (ST) algorithm。

3.2.2、Sparse Table (ST) algorithm

这里写图片描述

在上图中，我们可以看出：

在A[1]这个长度为2^0的区间内，最小值即为A[1] = 4，故最小值的索引M[1][0]为1；
在A[1]、A[2] 这个长度为2^1的区间内，最小值为A[2] = 3，故最小值的索引为M[1][1] = 2；
在A[1]、A[2]、A[3]、A[4]这个长度为2^2的区间内，最小值为A[3] = 1，故最小值的索引M[1][2] = 3。
为了计算M[i][j]我们必须找到前半段区间和后半段区间的最小值。很明显小的片段有着2^(j-1)长度，因此递归如下

这里写图片描述

根据上述公式，可以写出这个预处理的递归代码，如下：

void process2(int M[MAXN][LOGMAXN], int A[MAXN], int N)  
{  int i, j;  //initialize M for the intervals with length 1  for (i = 0; i < N; i++)  M[i][0] = i;  //compute values from smaller to bigger intervals  for (j = 1; 1 << j <= N; j++)  for (i = 0; i + (1 << j) - 1 < N; i++)  if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])  M[i][j] = M[i][j - 1];  else  M[i][j] = M[i + (1 << (j - 1))][j - 1];  
}

经过这个O(N logN)时间复杂度的预处理之后，让我们看看怎样使用它们去计算 RMQA(i, j)。思路是选择两个能够完全覆盖区间[i..j]的块并且找到它们之间的最小值。设k = [log(j - i + 1)]。

为了计算 RMQA(i, j)，我们可以使用下面的公式：

这里写图片描述

故，综合来看，咱们预处理的时间复杂度从O(N3)降低到了O(N logN)，查询的时间复杂度为O(1)，所以最终的整体复杂度为：

3.3、LCA与RMQ的关联性

现在，让我们看看怎样用RMQ来计算LCA查询。事实上，我们可以在线性时间里将LCA问题规约到RMQ问题，因此每一个解决RMQ的问题都可以解决LCA问题。让我们通过例子来说明怎么规约的：

这里写图片描述
…….分界线…….
这里写图片描述

注意LCAT(u, v)是在对T进行dfs过程当中在访问u和v之间离根结点最近的点。因此我们可以考虑树的欧拉环游过程u和v之间所有的结点，并找到它们之间处于最低层的结点。为了达到这个目的，我们可以建立三个数组：

  • E[1, 2*N-1] - 对T进行欧拉环游过程中所有访问到的结点;E[i]是在环游过程中第i个访问的结点
  • L[1,2*N-1] - 欧拉环游中访问到的结点所处的层数;L[i]是E[i]所在的层数
  • H[1, N] - H[i] 是E中结点i第一次出现的下标(任何出现i的地方都行，当然选第一个不会错)

假定H[u] < H[v]。可以很容易的看到u和v第一次出现的结点是E[H[u]..H[v]]。现在，我们需要找到这些结点中的最低层。为了达到这个目的，我们可以使用RMQ。因此 LCAT(u, v) = E[RMQL(H[u], H[v])] ,RMQ返回的是索引，下面是E,L,H数组：

这里写图片描述

注意L中连续的元素相差为1。

3.4、从RMQ到LCA

我们已经看到了LCA问题可以在线性时间规约到RMQ问题。现在让我们来看看怎样把RMQ问题规约到LCA。这个意味着我们实际上可以把一般的RMQ问题规约到带约束的RMQ问题(这里相邻的元素相差1)。为了达到这个目的，我们需要使用笛卡尔树。

对于数组A[0,N-1]的笛卡尔树C(A)是一个二叉树，根节点是A的最小元素，假设i为A数组中最小元素的位置。当i>0时，这个笛卡尔树的左子结点是A[0,i-1]构成的笛卡尔树，其他情况没有左子结点。右结点类似的用A[i+1,N-1]定义。注意对于具有相同元素的数组A，笛卡尔树并不唯一。在本文中，将会使用第一次出现的最小值，因此笛卡尔树看作唯一。可以很容易的看到RMQA(i, j) = LCAC(i, j)。

下面是一个例子：

这里写图片描述

这里写图片描述

现在我们需要做的仅仅是用线性时间计算C(A)。这个可以使用栈来实现。

初始栈为空。
然后我们在栈中插入A的元素。
在第i步,A[i]将会紧挨着栈中比A[i]小或者相等的元素插入,并且所有较大的元素将会被移除。
在插入结束之前栈中A[i]位置前的元素将成为i的左儿子，A[i]将会成为它之后一个较小元素的右儿子。
在每一步中，栈中的第一个元素总是笛卡尔树的根。

如果使用栈来保存元素的索引而不是值，我们可以很轻松的建立树。由于A中的每个元素最多被增加一次和最多被移除一次，所以建树的时间复杂度为O(N)。最终查询的时间复杂度为O(1)，故综上可得，咱们整个问题的最终时间复杂度为：

解法四：线段树

解决RMQ问题也可以用所谓的线段树Segment trees。线段树是一个类似堆的数据结构，可以在基于区间数组上用对数时间进行更新和查询操作。我们用下面递归方式来定义线段树的[i, j]区间：

  • 第一个结点将保存区间[i, j]区间的信息
  • 如果i < j左右的孩子结点将保存区间[i, (i+j)/2]和[(i+j)/2+1, j] 的信息

注意具有N个区间元素的线段树的高度为[logN] + 1。下面是区间[0,9]的线段树：

这里写图片描述

线段树和堆具有相同的结构，因此我们定义x是一个非叶结点，那么左孩子结点为2x,而右孩子结点为2x+1。想要使用线段树解决RMQ问题，我们则要要使用数组 M[1, 2 * 2[logN] + 1]，这里M[i]保存结点i区间最小值的位置。初始时M的所有元素为-1。树应当用下面的函数进行初始化(b和e是当前区间的范围)：

void initialize(int node, int b, int e, int M[MAXIND], int A[MAXN], int N)  
{  if (b == e)  M[node] = b;  else  {  //compute the values in the left and right subtrees  initialize(2 * node, b, (b + e) / 2, M, A, N);  initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A, N);  //search for the minimum value in the first and  //second half of the interval  if (A[M[2 * node]] <= A[M[2 * node + 1]])  M[node] = M[2 * node];  else  M[node] = M[2 * node + 1];  }  
}

上面的函数映射出了这棵树建造的方式。当计算一些区间的最小值位置时，我们应当首先查看子结点的值。调用函数的时候使用 node = 1, b = 0和e = N-1。

现在我们可以开始进行查询了。如果我们想要查找区间[i, j]中的最小值的位置时，我们可以使用下一个简单的函数：

int query(int node, int b, int e, int M[MAXIND], int A[MAXN], int i, int j)  
{  int p1, p2;  //if the current interval doesn't intersect  //the query interval return -1  if (i > e || j < b)  return -1;  //if the current interval is included in  //the query interval return M[node]  if (b >= i && e <= j)  return M[node];  //compute the minimum position in the  //left and right part of the interval  p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);  p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);  //return the position where the overall  //minimum is  if (p1 == -1)  return M[node] = p2;  if (p2 == -1)  return M[node] = p1;  if (A[p1] <= A[p2])  return M[node] = p1;  return M[node] = p2;  
}

你应该使用node = 1, b = 0和e = N - 1来调用这个函数，因为分配给第一个结点的区间是[0, N-1]。

可以很容易的看出任何查询都可以在O(log N)内完成。注意当我们碰到完整的in/out区间时我们停止了，因此数中的路径最多分裂一次。用线段树我们获得了

其余解法

除此之外，还有倍增法、重链剖分算法和后序遍历也可以解决该问题。其中，倍增思路相当于层序遍历，逐层或几层跳跃查，查询时间复杂度为O(log n)，空间复杂度为nlogn，对于每个节点先存储向上1层2层4层的节点，每个点有depth信息。

这篇关于最近公共祖先LCA问题（转）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/892034。

相关文章

好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
poj1330（LCA最近公共祖先）

poj1330（LCA最近公共祖先）

题意：求最近公共祖先 思路：之前学习了树链剖分，然后我就用树链剖分的一小部分知识就可以解这个题目了，记录每个结点的fa和depth。然后查找时，每次将depth大的结点往上走直到x = y。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...
缓存雪崩问题

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库，瞬间耗尽数据库资源，导致数据库无法使用。 解决方案： 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内，大量缓存数据同时失效，导致所有请求直接涌向数据库，瞬间增加数据库的负载压力，可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【VUE】跨域问题的概念，以及解决方法。

【VUE】跨域问题的概念，以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略，该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同，则需要服务器显式地允许这种跨域请求。一般在springbo
阅读更多...
题目1254：N皇后问题

题目1254：N皇后问题

题目1254：N皇后问题 时间限制：1 秒 内存限制：128 兆 特殊判题：否 题目描述： N皇后问题，即在N*N的方格棋盘内放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在同一斜线上。因为皇后可以直走，横走和斜走如下图)。 你的任务是，对于给定的N，求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入
阅读更多...
vscode中文乱码问题，注释，终端，调试乱码一劳永逸版

vscode中文乱码问题，注释，终端，调试乱码一劳永逸版

忘记咋回事突然出现了乱码问题，很多方法都试了，注释乱码解决了，终端又乱码，调试窗口也乱码，最后经过本人不懈努力，终于全部解决了，现在分享给大家我的方法。 乱码的原因是各个地方用的编码格式不统一，所以把他们设成统一的utf8. 1.电脑的编码格式 开始-设置-时间和语言-语言和区域 管理语言设置-更改系统区域设置-勾选Bata版：使用utf8-确定-然后按指示重启 2.vscode
阅读更多...
Android Environment 获取的路径问题

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2