কনসেপ্ট
এই আর্টিকেলে বাইনারি ট্রিতে দুটি নোডের LCA খুঁজে বের করার সমস্যাকে RMQ (Range Minimum Query) সমস্যায় রিডিউস করার পদ্ধতি ব্যাখ্যা করা হয়েছে।
উদাহরণ
Lowest Common Ancestor (LCA) হল রুট থেকে সবচেয়ে দূরে অবস্থিত সেই নোড যাকে দুটি নোড a এবং b উভয়ই ডিসেন্ডেন্ট হিসেবে আছে।
নিচের ডায়াগ্রাম অনুযায়ী, নোড D এবং I-এর LCA হল নোড B।
LCA সমাধানের অনেক পদ্ধতি আছে। এখানে Segment Tree ভিত্তিক RMQ পদ্ধতি ব্যাখ্যা করা হয়েছে। প্রিপ্রসেসিং টাইম O(n), কুয়েরি টাইম O(log n), এক্সট্রা স্পেস O(n)।
LCA কে RMQ-তে রিডাকশন
ট্রিকে রুট থেকে অয়লার টুর (Euler tour) দিয়ে ট্রাভার্স করুন, যা DFS-এর一種 প্রি-অর্ডার ট্রাভার্সাল।
অবজারভেশন − D এবং I-এর LCA হল B, যা D এবং I-এর ভিজিটের মধ্যে সবচেয়ে রুটের কাছে অবস্থিত নোড। অর্থাৎ, অয়লার টুরে D এবং I-এর যেকোনো দুটি কনsekutিভ অক্যুরেন্সের মাঝপথে ন্যূনতম লেভেলের নোডটিই LCA।
ইমপ্লিমেন্টেশনের জন্য তিনটি অ্যারে লাগবে:
- অয়লার টুর অনুযায়ী ভিজিট করা নোডها।
- প্রতিটি নোডের লেভেল অয়লার টুরে।
- নোডের প্রথম অক্যুরেন্স ইন্ডেক্স অয়লার টুরে।
পদ্ধতি
- অয়লার টুর করে euler, level, firstOccurrence অ্যারে ফিল করুন।
- firstOccurrence দিয়ে দুটি নোডের ইন্ডেক্স বের করুন, সেটি level অ্যারেতে RMQ-এর রেঞ্জ হবে।
- RMQ আর্গোরিদম ন্যূনতম লেভেলের ইন্ডেক্স রিটার্ন করলে, অয়লার টুর অ্যারে থেকে LCA নোড বের করুন।
উদাহরণ
#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<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.
