数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用RMQ在C++中查找二叉树中的LCA
概念
本文解释了一种解决在树中查找两个节点的LCA问题的方法，该方法通过将其简化为RMQ问题来实现。
示例
在有根树T中，两个节点a和b的最近公共祖先 (LCA) 定义为距离根节点最远且同时具有a和b作为后代的节点。
例如，根据下图，节点D和节点I的LCA是节点B。
我们可以应用多种方法来解决LCA问题。这些方法在时间和空间复杂度方面有所不同。
范围最小查询 (RMQ) 应用于数组，以定位在两个指定索引之间具有最小值的元素的位置。我们可以应用不同的方法来解决RMQ。本文解释了基于线段树的方法。对于线段树，预处理时间为O(n)，范围最小查询时间为O(Logn)。这里，需要额外的O(n)空间来存储线段树。
将LCA简化为RMQ
我们解释了这个思想，即通过欧拉遍历（不抬起笔的访问）从根节点开始访问树，这是一种具有先序遍历特征的深度优先搜索 (DFS) 类型的遍历。
观察 - 根据上图，节点D和I的LCA是节点B，这表示在T的DFS期间，在访问D和I之间遇到的所有节点中，最靠近根节点的节点。所以我们可以说这个观察是简化的关键。我们还可以说，我们的节点是处于最小级别且在T的欧拉遍历中a和b的连续出现（任何出现）之间出现的节点中唯一处于该级别的节点。
我们需要三个数组来实现：
按T的欧拉遍历顺序访问的节点
在T的欧拉遍历中访问的每个节点的级别
节点在T的欧拉遍历中的第一次出现索引（由于任何出现都可以，因此让我们跟踪第一次出现）
方法
对树执行欧拉遍历，并填充euler、level和第一次出现数组。
应用第一次出现数组，获得对应于两个节点的索引，这两个索引将成为馈送到RMQ算法以获取最小值的level数组中的范围的角点。
当算法返回范围内最小级别的索引时，我们使用欧拉遍历数组来确定LCA。
示例
/* This C++ Program is implemented to find LCA of u and v by reducing the problem to RMQ */
#include<bits/stdc++.h>
#define V 9 // indicates number of nodes in input tree
int euler1[2*V - 1]; // indicates for Euler tour sequence
int level1[2*V - 1]; // indicates level of nodes in tour sequence
int firstOccurrence1[V+1]; // indicates first occurrences of nodes in tour
int ind; // indicates variable to fill-in euler and level arrays
//This is a Binary Tree node
struct Node1{
int key;
struct Node1 *left, *right;
};
// Utility function creates a new binary tree node with given key
Node1 * newNode1(int k){
Node1 *temp = new Node1;
temp->key = k;
temp->left = temp->right = NULL;
return temp;
}
// indicates log base 2 of x
int Log2(int x){
int ans = 0 ;
while (x>>=1) ans++;
return ans ;
}
/* A recursive function is used to get the minimum value in a given range of array indexes. The following are parameters for this function.
st --> indicates pointer to segment tree
index --> indicates index of current node in the segment tree.
Initially 0 is passed as root is always at index 0
ss & se --> indicate starting and ending indexes of the segment
represented by current node, i.e., st[index]
qs & qe --> indicate starting and ending indexes of query range
*/
int RMQUtil(int index1, int ss1, int se1, int qs1, int qe1, int *st1){
// It has been seen that if segment of this node is a part of given range, then return the min of the segment
if (qs1 <= ss1 && qe1 >= se1)
return st1[index1];
//It has been seen that if segment of this node is outside the given range
else if (se1 < qs1 || ss1 > qe1)
return -1;
// It has been seen that if a part of this segment overlaps with the given range
int mid = (ss1 + se1)/2;
int q1 = RMQUtil(2*index1+1, ss1, mid, qs1, qe1, st1);
int q2 = RMQUtil(2*index1+2, mid+1, se1, qs1, qe1, st1);
if (q1==-1) return q2;
else if (q2==-1) return q1;
return (level1[q1] < level1[q2]) ? q1 : q2;
}
// Return minimum of elements in range from index qs (query start) to
// qe (query end). It mainly uses RMQUtil()
int RMQ(int *st1, int n, int qs1, int qe1){
// Check for erroneous input values
if (qs1 < 0 || qe1 > n-1 || qs1 > qe1){
printf("Invalid Input");
return -1;
}
return RMQUtil(0, 0, n-1, qs1, qe1, st1);
}
// Now a recursive function that constructs Segment Tree for
array[ss1..se1]. // si1 is index of current node in segment tree st
void constructSTUtil(int si1, int ss1, int se1, int arr1[], int *st1){
// When there will be only one element in array, store it in current node of
// segment tree and return
if (ss1 == se1)st1[si1] = ss1;
else{
// It has been seen that if there are more than one
elements, then recur for left and right subtrees and store the
minimum of two values in this node
int mid1 = (ss1 + se1)/2;
constructSTUtil(si1*2+1, ss1, mid1, arr1, st1);
constructSTUtil(si1*2+2, mid1+1, se1, arr1, st1);
if (arr1[st1[2*si1+1]] < arr1[st1[2*si1+2]])
st1[si1] = st1[2*si1+1];
else
st1[si1] = st1[2*si1+2];
}
}
/* Now this function is used to construct segment tree from given
array. This function allocates memory for segment tree and calls
constructSTUtil() to fill the allocated memory */
int *constructST(int arr1[], int n){
// Allocating memory for segment tree
//Indicates height of segment tree
int x = Log2(n)+1;
// Indicates maximum size of segment tree
int max_size = 2*(1<<x) - 1; // 2*pow(2,x) -1
int *st1 = new int[max_size];
// Indicates filling the allocated memory st1
constructSTUtil(0, 0, n-1, arr1, st1);
// Returning the constructed segment tree
return st1;
}
// Indicates recursive version of the Euler tour of T
void eulerTour(Node1 *root, int l){
/* if the passed node exists */
if (root){
euler1[ind] = root->key; // inserting in euler array
level1[ind] = l; // inserting l in level array
ind++; // indicates increment index
/* It has been seen that if unvisited, mark first occurrence*/
if (firstOccurrence1[root->key] == -1)
firstOccurrence1[root->key] = ind-1;
/* touring left subtree if exists, and remark euler
and level arrays for parent on return */
if (root->left){
eulerTour(root->left, l+1);
euler1[ind]=root->key;
level1[ind] = l;
ind++;
}
/* touring right subtree if exists, and remark euler
and level arrays for parent on return */
if (root->right) {
eulerTour(root->right, l+1);
euler1[ind]=root->key;
level1[ind] = l;
ind++;
}
}
}
// Returning LCA of nodes n1, n2 (assuming they are
// present in the tree)
int findLCA(Node1 *root, int u1, int v1){
/* Marking all nodes unvisited. Note that the size of
firstOccurrence is 1 as node values which vary from
1 to 9 are used as indexes */
memset(firstOccurrence1, -1, sizeof(int)*(V+1));
/* To start filling euler and level arrays from index 0 */
ind = 0;
/* Starting Euler tour with root node on level 0 */
eulerTour(root, 0);
/* constructing segment tree on level array */
int *st1 = constructST(level1, 2*V-1);
/*It has been seen that if v before u in Euler tour. For RMQ to
work, first parameter 'u1' must be smaller than second 'v1' */
if (firstOccurrence1[u1]>firstOccurrence1[v1])
std::swap(u1, v1);
// Indicates starting and ending indexes of query range
int qs1 = firstOccurrence1[u1];
int qe1 = firstOccurrence1[v1];
// Indicates query for index of LCA in tour
int index1 = RMQ(st1, 2*V-1, qs1, qe1);
/* returning LCA node */
return euler1[index1];
}
// Driver program to test above functions
int main(){
// Let us create the Binary Tree as shown in the diagram.
Node1 * root = newNode1(1);
root->left = newNode1(2);
root->right = newNode1(3);
root->left->left = newNode1(4);
root->left->right = newNode1(5);
root->right->left = newNode1(6);
root->right->right = newNode1(7);
root->left->right->left = newNode1(8);
root->left->right->right = newNode1(9);
int u1 = 4, v1 = 9;
printf("The LCA of node %d and node %d is node %d.\n",
u1, v1, findLCA(root, u1, v1));
return 0;
}输出
The LCA of node 4 and node 9 is node 2.
更新于：2020年7月23日
120 次浏览
广告