หา LCA ใน Binary Tree ด้วย RMQ (Range Minimum Query) ใน C++

แนวคิด

Lowest Common Ancestor (LCA) ของโหนด a และ b ใน rooted tree T คือโหนดที่อยู่ห่างจากรากมากที่สุด ที่มีทั้ง a และ b เป็น descendants

วิธีการ: ลดปัญหา LCA ให้กลายเป็น RMQ (Range Minimum Query) โดยใช้ Euler Tour ของต้นไม้

ขั้นตอนการแก้ปัญหา

1. ทำ Euler Tour (DFS preorder) บันทึก:
   • euler[]: โหนดที่เยี่ยมตามลำดับ
   • level[]: ระดับของโหนดใน tour
   • firstOccurrence[]: index แรกของแต่ละโหนดใน euler
2. สร้าง Segment Tree บน array level[] เพื่อ RMQ
3. หา LCA(u,v): ใช้ firstOccurrence หา range ใน level[], query RMQ หา index ที่ level ต่ำสุด, ใช้ index นั้นหาโหนดใน euler[]

ตัวอย่างโค้ด C++

#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){ ... }

int Log2(int x){ ... }
int RMQUtil(int index1, int ss1, int se1, int qs1, int qe1, int *st1){ ... }
int RMQ(int *st1, int n, int qs1, int qe1){ ... }
void constructSTUtil(int si1, int ss1, int se1, int arr1[], int *st1){ ... }
int *constructST(int arr1[], int n){ ... }

void eulerTour(Node1 *root, int l){ ... }
int findLCA(Node1 *root, int u1, int v1){ ... }

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.