Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 其它算法 » , ,

LCA与RMQ互相转化

前面我们介绍过LCARMQ问题各自的解法,其实这两个问题非常类似,本质上是等价的。他们之间可以互相进行转化,并且复杂度不高,有时恰当的转化可以大大提升算法解决问题的性能,这里主要介绍二者之间互相转化的算法思想及核心代码实现。

一 LCA转RMQ

LCA转RMQ主要是通过DFS(深度优先搜索)完成,时间复杂度为O(n)。

DFS时每次进入以及回溯到某一个节点时,我们都记录访问到的节点val,同时记录下这个节点的深度depth。因为进入及回溯时都要记录,所以一个节点可能会被记录多次。另外,为了后面应用RMQ的方便,还使用数组first记录每个元素第一次访问的下标。

例如,下面是一棵以节点0为根节点的多叉树:

lca例子树

以这棵树为例,我们进行DFS时可以得到如下depth数组和val数组:

val 0 1 4 1 5 7 5 1 0 2 0 3 6 3 0
depth 0 1 2 1 2 3 2 1 0 1 0 1 2 1 0

first数组为

下标 0 1 2 3 4 5 6 7
0 1 9 11 2 4 12 5

要求x和y的LCA时,因为LCA的深度肯定是最小的,于是可以通过first数组找到x和y首次出现的位置first[x]和first[y],然后再depth数组查找从first[x]到first[y]的RMQ的下标id,然后在val数组中找到下标id所代表的元素,即为x和y的LCA。

即 LCA(x, y) = val[RMQ(depth, first[x], first[y])]

这里沿用之前的代码,使用邻接表表示多叉树。

下面是LCA转RMQ的核心代码,生成对应的三个数组。

使用时先初始化id=0,然后使用dfs(root, 0)进行调用。注意,depth的最终长度为id,并且调用RMQ时需要使用下标版本,即initRMQIndex()和RMQIndex(x, y)。

int depth[mx], val[mx], first[mx];
int id; //记录当前数组的长度
void dfs(int x, int dep)
{
	depth[id] = dep; val[id] = x; first[x] = id; id++;
	for (int i = 0; i < tree[x].size(); i++)
	{
		dfs(tree[x][i], dep+1);
		depth[id] = dep; val[id] = x; id++; //递归完一棵子树回到自身
	}
}

二 RMQ转LCA

RMQ转LCA比较麻烦,因为RMQ使用相对简单,实际上很少转换。

RMQ转LCA时需要用到笛卡尔树(Cartesian Tree),构造笛卡尔树时把数组中最小的数作为树根,其左右儿子分别为左右两边的子数组构成的笛卡尔树。

根据笛卡尔树的性质,对其进行中序遍历会得到原数组,相当于把数组中的最小值提到最高处,次小值提到次高处。

算法实现时不用每次去找最小的数字,只需要从左到右依次把数组中的数字加入笛卡尔树中(平均复杂度O(n))。每次新加入的数字x肯定在笛卡尔树的最右边,没有右儿子。于是,如果x比根节点还小,那把x作为新的根节点,并把原笛卡尔树作为其左儿子;否则,在树的最右边的路径中寻找第一个比x大的数字,把它作为x的左儿子,它的父亲作为x的父亲。如果全部比x小,则把x加入到最右下角处。

由于这里笛卡尔树是二叉树,为了方便,以下没有用邻接表实现树,所以对应的LCA上的Tarjan算法跟之前也不太一致,不过只要算法思想清楚,很容易修改过来。

struct Node{ int val, lchild, rchild;} node[mx]; //树节点,儿子指针用数组下标表示
int root; //树根

int a[mx], n; //数组、长度
void buildTree()
{
	node[0].val = a[0]; node[0].lchild = node[0].rchild = -1; //第一个做树根
	root = 0; 
	for (int i = 1; i < n; i++)		
		if (node[root].val > a[i]) //整棵树作为新节点的左子树
		{
			node[i].val = a[i]; 
			node[i].lchild = root; node[i].rchild = -1;
			root = i;
		}
		else
		{
			int p1 = root, p2 = node[root].rchild;
			while (p2 != -1 && node[p2].val < a[i])
				p1 = p2, p2 = node[p2].rchild;
			node[p1].rchild = i;
			node[i].val = a[i];
			node[i].lchild = p2; node[i].rchild = -1;	
		}
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论