컨셉
이 기사는 트리에서 두 노드의 LCA를 찾는 문제를 RMQ 문제로 축소하여 해결하는 방법을 설명합니다.
예
최하위 공통 조상(LCA) 루트 트리 T의 두 노드 a와 b 중 하나는 루트에서 가장 멀리 위치한 노드로 정의되며, 이 노드는 b와 b를 모두 자손으로 가지고 있습니다.
예를 들어, 아래 다이어그램에 따르면 노드 D와 노드 I의 LCA는 노드 B입니다.
LCA 문제를 해결하기 위해 많은 접근 방식을 적용할 수 있습니다. 이러한 접근 방식은 시간 및 공간 복잡성 측면에서 다릅니다.
최소 검색어 범위(RMQ) 두 개의 지정된 인덱스 사이에 최소값이 있는 요소의 위치를 찾기 위해 배열에 적용됩니다. RMQ를 해결하기 위해 다양한 접근 방식을 적용할 수 있습니다. 이 기사에 따르면 Segment Tree 기반 접근 방식에 대해 설명합니다. 세그먼트 트리의 경우 전처리 시간은 O(n)이고 범위 최소 쿼리 시간은 O(Logn)입니다. 여기서 필요한 추가 공간은 세그먼트 트리를 저장하기 위해 O(n)입니다.
LCA를 RMQ로 감소
선주문 순회 특성을 갖는 DFS(Depth First Search) 유형 순회인 오일러 순회(연필을 들지 않고 방문)로 루트에서 시작하여 트리를 방문하는 아이디어를 설명합니다.
관찰 − 위의 다이어그램에 따르면 노드 D와 I의 LCA는 노드 B이며, 이는 T의 DFS 동안 D와 I의 방문 사이에 발생한 모든 노드 중 루트에 가장 가까운 노드임을 나타냅니다. 따라서 이 관찰을 말할 수 있습니다. 감소의 핵심이다. 다시 우리의 노드는 T의 오일러 투어에서 의 연속적인 발생(임의)과 b 사이에 발생하는 모든 노드 중에서 최소 수준의 노드이자 해당 수준의 유일한 노드라고 말할 수 있습니다.
구현을 위해 3개의 어레이가 필요합니다 -
-
T의 오일러 순회 순으로 방문한 노드
-
T의 오일러 투어에서 방문한 각 노드 레벨
-
T의 오일러 투어에서 노드의 첫 번째 발생 인덱스(어떤 발생이든 좋을 것이므로 첫 번째 항목을 추적합시다)
방법
-
트리에서 오일러 둘러보기를 수행하고 오일러, 레벨 및 첫 번째 발생 배열을 채웁니다.
-
첫 번째 발생 배열을 적용하여 최소값에 대한 RMQ 알고리즘에 공급되는 레벨 배열에서 범위의 모서리가 될 두 노드에 해당하는 인덱스를 가져옵니다.
-
알고리즘이 범위 내 최소 수준의 인덱스를 반환할 때 이를 적용하여 오일러 순회 배열을 사용하여 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.