Tìm LCA trong cây nhị phân dùng RMQ (Range Minimum Query) trong C++

Khái niệm

Lowest Common Ancestor (LCA) của hai nút a, b trong cây có gốc là nút xa gốc nhất mà có cả a, b là hậu duệ. Bài viết giảm bài toán LCA thành bài toán RMQ (Range Minimum Query) trên mảng.

Ý tưởng: Duyệt Euler tour (DFS preorder) trên cây, ghi lại:

• Mảng euler: thứ tự nút thăm.
• Mảng level: độ sâu của nút tương ứng.
• Mảng firstOccurrence: chỉ số lần đầu xuất hiện của mỗi nút trong Euler tour.

Ví dụ (C++)

#include<bits/stdc++.h>
#define V 9
int euler1[2*V-1], level1[2*V-1], firstOccurrence1[V+1], ind;

struct Node1{ int key; Node1 *left, *right; };
Node1* newNode1(int k){ /* ... */ }

int Log2(int x){ int ans=0; while(x>>=1) ans++; return ans; }

int RMQUtil(int idx, int ss, int se, int qs, int qe, int* st){
    if (qs<=ss && qe>=se) return st[idx];
    if (se<qs || ss>qe) return -1;
    int mid=(ss+se)/2;
    int q1=RMQUtil(2*idx+1,ss,mid,qs,qe,st);
    int q2=RMQUtil(2*idx+2,mid+1,se,qs,qe,st);
    if(q1==-1) return q2; if(q2==-1) return q1;
    return (level1[q1]<level1[q2])?q1:q2;
}

int RMQ(int* st, int n, int qs, int qe){ /* ... */ }
void constructSTUtil(int si, int ss, int se, int arr[], int* st){ /* ... */ }
int* constructST(int arr[], int n){ /* ... */ }

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* st=constructST(level1,2*V-1);
    if(firstOccurrence1[u1]>firstOccurrence1[v1]) swap(u1,v1);
    int qs=firstOccurrence1[u1], qe=firstOccurrence1[v1];
    int idx=RMQ(st,2*V-1,qs,qe);
    return euler1[idx];
}

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;
}

Đầu ra

The LCA of node 4 and node 9 is node 2.