Thuật toán LCA (Lowest Common Ancestor): Lý thuyết và cài đặt trong C++

Từ khóa chính: thuật toán LCA, Lowest Common Ancestor, cây nhị phân, cây tổng quát, C++, truy vấn tổ tiên chung

🔗 Xem thêm:
Cây trong cấu trúc dữ liệu (Wikipedia)
Tổ tiên chung gần nhất (Wikipedia)
Hướng dẫn chi tiết LCA trong lập trình

Mục lục

1. LCA là gì?

LCA (Lowest Common Ancestor – tổ tiên chung gần nhất) của hai đỉnh u và v trong một cây là đỉnh sâu nhất mà cả hai đỉnh u và v đều là hậu duệ. Bài toán LCA là một trong những bài toán cơ bản và quan trọng trong lĩnh vực lý thuyết đồ thị và cấu trúc dữ liệu.

1.1 Ứng dụng thực tế

Truy vấn trong cây nhị phân hoặc cây tổng quát.
So sánh phả hệ trong hệ thống tổ chức hoặc cây gene.
Truy xuất dữ liệu tổ tiên trong cây phân cấp thư mục.
Tối ưu hóa tìm đường đi ngắn nhất giữa hai đỉnh trong cây.
Hỗ trợ các thuật toán phân tích cây, xây dựng hệ thống phân quyền trong tổ chức.
Trong hệ thống mạng máy tính, việc truy vết cây kết nối cũng có thể sử dụng LCA để giảm độ sâu truyền dữ liệu.

2. Các phương pháp giải bài toán LCA

Tuỳ thuộc vào số lượng truy vấn và tính chất của cây, ta có các cách tiếp cận khác nhau để giải bài toán này:

Duyệt ngược bằng cha (brute-force): đơn giản, mỗi truy vấn chạy O(N), không thích hợp với nhiều truy vấn.
Binary Lifting (Nâng cấp nhị phân): sử dụng bảng tổ tiên theo lũy thừa 2, cho phép truy vấn O(logN) sau tiền xử lý O(NlogN).
Euler Tour + Segment Tree hoặc Sparse Table: xây dựng tour Euler, lưu độ sâu và vị trí xuất hiện đầu tiên để tìm LCA qua RMQ.

3. LCA bằng Binary Lifting

Phương pháp Binary Lifting sử dụng mảng cha cấp 2^k để nhảy lùi lên tổ tiên, nhờ đó truy vấn LCA chỉ cần O(logN) thời gian. Đây là lựa chọn tốt nhất nếu số lượng truy vấn rất lớn và không thay đổi cấu trúc cây.

3.1 Ý tưởng

Ta xây dựng mảng up[u][k] là tổ tiên của đỉnh u ở mức 2^k. Sau đó, để tìm LCA(u, v):

Nếu độ sâu của u khác v, ta đưa u lên bằng v bằng cách nhảy nhị phân.
Tiếp tục nhảy đồng thời u và v đến khi chúng gặp nhau ở tổ tiên chung.

3.2 Cài đặt cấu trúc

const int MAXN = 100005;
const int LOG = 20;
vector adj[MAXN];
int up[MAXN][LOG], depth[MAXN];

void dfs(int u, int p) {
    up[u][0] = p;
    for (int i = 1; i < LOG; ++i)
        up[u][i] = up[up[u][i-1]][i-1];
    for (int v : adj[u]) {
        if (v != p) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

3.3 Hàm truy vấn LCA

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG-1; i >= 0; --i)
        if (depth[u] - (1 << i) >= depth[v])
            u = up[u][i];
    if (u == v) return u;
    for (int i = LOG-1; i >= 0; --i)
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
}

4. Ví dụ minh họa và thực hành

Cho cây gồm 7 đỉnh với các cạnh: (1-2), (1-3), (2-4), (2-5), (3-6), (3-7). Hình cây có dạng:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

Truy vấn LCA(4, 5) = 2, LCA(4, 6) = 1. Ta có thể thực hiện bằng cách gọi hàm lca(u, v) sau khi tiền xử lý bằng DFS.

5. Tối ưu hóa và mở rộng

5.1 Tính khoảng cách giữa hai đỉnh

Khi đã có LCA, khoảng cách giữa u và v là:

dist(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]

5.2 LCA trên cây nhị phân

Nếu cây là nhị phân, ta vẫn áp dụng Binary Lifting như bình thường. Ngoài ra còn có cách sử dụng DFS timestamp và parent trực tiếp.

5.3 LCA trong bài toán truy vấn động

Nếu cây thay đổi, cần dùng các cấu trúc như Link-Cut Tree hoặc Heavy-Light Decomposition.

6. Kết luận

Thuật toán LCA là một kỹ thuật nền tảng, đặc biệt quan trọng trong các hệ thống phân cấp và xử lý truy vấn cây. Với các thuật toán như Binary Lifting, bạn có thể xử lý hàng triệu truy vấn trong thời gian rất ngắn. Bài toán này không chỉ quan trọng trong thi lập trình mà còn có ứng dụng rộng rãi trong các hệ thống dữ liệu phức tạp.

Việc làm chủ LCA giúp mở ra nhiều cánh cửa đến với các thuật toán cao cấp hơn như RMQ, HLD, hay Centroid Decomposition. Nên luyện tập các dạng bài từ cơ bản đến nâng cao để thuần thục kỹ năng này.