अवधारणा
यह लेख ट्री में दो नोड्स के LCA को खोजने की समस्या को RMQ समस्या में कम करके हल करने की एक विधि बताता है।
लोएस्ट कॉमन एंसेस्टर (LCA)
एक रूटेड ट्री T में दो नोड्स a और b का लोएस्ट कॉमन एंसेस्टर (LCA) उस नोड के रूप में परिभाषित किया जाता है जो रूट से सबसे दूर स्थित होता है और जिसके दोनों a और b वंशज होते हैं।
उदाहरण के लिए, नीचे दिए गए आरेख के अनुसार, नोड D और नोड I का LCA नोड B है।

रेंज मिनिमम क्वेरी (RMQ)
RMQ का उपयोग सरणियों पर दो निर्दिष्ट सूचकांकों के बीच न्यूनतम मान वाले तत्व की स्थिति खोजने के लिए किया जाता है। RMQ को हल करने के लिए विभिन्न दृष्टिकोण लागू किए जा सकते हैं। इस लेख में, सेगमेंट ट्री आधारित दृष्टिकोण समझाया गया है। सेगमेंट ट्री के लिए, प्रीप्रोसेसिंग समय O(n) है और रेंज मिनिमम क्वेरी के लिए समय O(Logn) है। यहां, सेगमेंट ट्री को स्टोर करने के लिए अतिरिक्त स्थान O(n) चाहिए।
LCA को RMQ में कमी
हम रूट से शुरू करके ट्री का यूलर टूर (पेंसिल उठाए बिना दौरा) करके इस विचार को समझाते हैं, जो प्रीऑर्डर ट्रैवर्सल विशेषताओं वाला एक DFS-प्रकार का ट्रैवर्सल है।

अवलोकन - उपरोक्त आरेख के अनुसार, नोड्स D और I का LCA नोड B है, जो T के DFS के दौरान D और I के दौरे के बीच मिलने वाले सभी नोड्स में रूट के सबसे करीब का नोड प्रतीत होता है। तो हम कह सकते हैं कि यह अवलोकन कमी की कुंजी है। फिर हम कह सकते हैं कि हमारा नोड न्यूनतम स्तर पर नोड है और उस स्तर पर एकमात्र नोड है जो T के यूलर टूर में a और b की लगातार घटनाओं (कोई भी) के बीच होता है।
कार्यान्वयन के लिए हमें तीन सरणियों की आवश्यकता होती है:
- यूलर टूर में देखे गए नोड्स का क्रम
- यूलर टूर में देखे गए प्रत्येक नोड का स्तर
- यूलर टूर में नोड की पहली घटना का सूचकांक (चूंकि कोई भी घटना अच्छी होगी, आइए पहली को ट्रैक करें)

विधि
- ट्री पर यूलर टूर करें, और यूलर, लेवल और पहली घटना सरणियों को भरें।
- पहली घटना सरणी का उपयोग करके, उन दो नोड्स के अनुरूप सूचकांक प्राप्त करें जो लेवल सरणी में रेंज के कोने होंगे जिसे RMQ एल्गोरिदम को न्यूनतम मान के लिए दिया जाता है।
- जब एल्गोरिदम रेंज में न्यूनतम स्तर का सूचकांक लौटाता है, तो हम यूलर टूर सरणी का उपयोग करके LCA निर्धारित करते हैं।
C++ कार्यान्वयन
/* C++ Program to find LCA of u and v by reducing the problem to RMQ */
#include<bits/stdc++.h>
#define V 9
int euler1[2*V - 1];
int level1[2*V - 1];
int firstOccurrence1[V+1];
int ind;
struct Node1{
int key;
struct Node1 *left, *right;
};
Node1 * newNode1(int k){
Node1 *temp = new Node1;
temp->key = k;
temp->left = temp->right = NULL;
return temp;
}
int Log2(int x){
int ans = 0;
while (x>>=1) ans++;
return ans;
}
int RMQUtil(int index1, int ss1, int se1, int qs1, int qe1, int *st1){
if (qs1 <= ss1 && qe1 >= se1)
return st1[index1];
else if (se1 < qs1 || ss1 > qe1)
return -1;
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;
}
int RMQ(int *st1, int n, int qs1, int qe1){
if (qs1 < 0 || qe1 > n-1 || qs1 > qe1){
printf("Invalid Input");
return -1;
}
return RMQUtil(0, 0, n-1, qs1, qe1, st1);
}
void constructSTUtil(int si1, int ss1, int se1, int arr1[], int *st1){
if (ss1 == se1) st1[si1] = ss1;
else{
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];
}
}
int *constructST(int arr1[], int n){
int x = Log2(n)+1;
int max_size = 2*(1<<x) - 1;
int *st1 = new int[max_size];
constructSTUtil(0, 0, n-1, arr1, st1);
return st1;
}
void eulerTour(Node1 *root, int l){
if (root){
euler1[ind] = root->key;
level1[ind] = l;
ind++;
if (firstOccurrence1[root->key] == -1)
firstOccurrence1[root->key] = ind-1;
if (root->left){
eulerTour(root->left, l+1);
euler1[ind]=root->key;
level1[ind] = l;
ind++;
}
if (root->right) {
eulerTour(root->right, l+1);
euler1[ind]=root->key;
level1[ind] = l;
ind++;
}
}
}
int findLCA(Node1 *root, int u1, int v1){
memset(firstOccurrence1, -1, sizeof(int)*(V+1));
ind = 0;
eulerTour(root, 0);
int *st1 = constructST(level1, 2*V-1);
if (firstOccurrence1[u1]>firstOccurrence1[v1])
std::swap(u1, v1);
int qs1 = firstOccurrence1[u1];
int qe1 = firstOccurrence1[v1];
int index1 = RMQ(st1, 2*V-1, qs1, qe1);
return euler1[index1];
}
int main(){
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.