Bài 24.1. Khái niệm và cách tiếp cận LCA (Lowest Common Ancestor)

Chào mừng trở lại với series Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau lặn sâu vào một bài toán kinh điển và cực kỳ quan trọng khi làm việc với cấu trúc dữ liệu cây: Bài toán tìm Tổ tiên chung gần nhất (Lowest Common Ancestor - LCA). LCA không chỉ là một khái niệm lý thuyết hấp dẫn mà còn có muôn vàn ứng dụng thực tế trong nhiều lĩnh vực, từ sinh học đến hệ thống file hay thậm chí là mạng máy tính.

Hãy cùng khám phá xem LCA là gì và làm thế nào chúng ta có thể "bắt" được nó trong một cây nhé!

LCA là gì? Khái niệm cơ bản

Trong một cây (thường là cây có gốc - rooted tree), tổ tiên của một nút u là bất kỳ nút nào nằm trên đường đi từ gốc đến u (bao gồm cả u và gốc).

Cho hai nút u và v bất kỳ trên cây:

Tổ tiên chung (Common Ancestor) của u và v là một nút a sao cho a là tổ tiên của cả u và v.
Tổ tiên chung gần nhất (Lowest Common Ancestor - LCA) của u và v, ký hiệu là LCA(u, v), là tổ tiên chung của u và v nằm xa gốc nhất. Nói cách khác, nó là nút ở vị trí cao nhất trong cây (gần gốc nhất) mà vẫn là tổ tiên của cả u và v. Một cách diễn đạt khác là nó là nút ở vị trí thấp nhất (xa gốc nhất) trong cây mà có u và v nằm trong cây con của nó.

Ví dụ minh họa (Tưởng tượng cây có gốc 1):

Giả sử chúng ta có cây sau:

        1 (gốc)
       / \
      2   3
     / \   \
    4   5   6
   /       / \
  7       8   9

Tổ tiên của 7 là: 7, 4, 2, 1.
Tổ tiên của 9 là: 9, 6, 3, 1.
Tổ tiên chung của 7 và 9 là: 1. Tổ tiên chung gần nhất (LCA) của 7 và 9 là: 1.
Tổ tiên chung của 4 và 5 là: 2, 1. LCA(4, 5) = 2.
Tổ tiên chung của 8 và 9 là: 6, 3, 1. LCA(8, 9) = 6.
Tổ tiên chung của 7 và 4 là: 4, 2, 1. LCA(7, 4) = 4. (Khi một nút là tổ tiên của nút kia, nút tổ tiên chính là LCA).
LCA(4, 1) = 1.

Hiểu rõ khái niệm LCA là bước đầu tiên và quan trọng nhất. Bây giờ, làm thế nào để tìm nó một cách hiệu quả?

Các cách tiếp cận tìm LCA

Có nhiều thuật toán để tìm LCA, với độ phức tạp và yêu cầu tiền xử lý khác nhau. Chúng ta sẽ đi từ những phương pháp cơ bản đến kỹ thuật tối ưu hơn.

Cách tiếp cận 1: Sử dụng đường đi từ gốc (Naive)

Đây là ý tưởng đơn giản nhất:

Tìm đường đi từ gốc đến nút u.
Tìm đường đi từ gốc đến nút v.
So sánh hai đường đi này từ gốc trở xuống. Nút cuối cùng mà cả hai đường đi còn giống nhau chính là LCA(u, v).

Ví dụ: Tìm LCA(7, 9) trong cây trên.

Đường đi từ 1 đến 7: 1 -> 2 -> 4 -> 7
Đường đi từ 1 đến 9: 1 -> 3 -> 6 -> 9
So sánh: 1 (chung), tiếp theo 2 (khác 3). Nút chung cuối cùng là 1. Vậy LCA(7, 9) = 1.

Cách này dễ hiểu nhưng không hiệu quả cho lắm, đặc biệt khi cần tìm LCA cho nhiều cặp nút hoặc cây rất sâu (độ phức tạp có thể lên tới O(N) cho mỗi truy vấn LCA trong trường hợp xấu nhất, với N là số nút).

Cách tiếp cận 2: Sử dụng con trỏ cha và độ sâu

Nếu chúng ta biết được nút cha của mỗi nút và độ sâu của mỗi nút so với gốc, chúng ta có thể tìm LCA hiệu quả hơn một chút.

Ý tưởng:

Đưa hai nút u và v về cùng độ sâu. Nút nào sâu hơn sẽ di chuyển dần lên phía gốc bằng cách nhảy đến nút cha của nó, cho đến khi cả hai có cùng độ sâu.
Sau khi cùng độ sâu, nếu u và v đã là cùng một nút, thì đó chính là LCA (trường hợp một nút là tổ tiên của nút kia).
Nếu chưa cùng một nút, đồng thời di chuyển cả u và v lên một bước (nhảy đến nút cha). Lặp lại bước này cho đến khi u và v trở thành cùng một nút.
Khi u và v gặp nhau, nút đó chính là LCA(u, v).

Để thực hiện cách này, chúng ta cần:

Tiền xử lý: Thực hiện một lần duyệt DFS (Depth First Search) từ gốc để tính độ sâu (depth[u]) và lưu nút cha trực tiếp (parent[u]) cho mọi nút. Độ phức tạp tiền xử lý: O(N).
Truy vấn LCA: Thực hiện các bước nhảy như mô tả ở trên. Độ phức tạp truy vấn: O(H) trong trường hợp xấu nhất, với H là chiều cao của cây (có thể lên tới O(N) với cây suy biến thành danh sách liên kết).

Mã C++ minh họa:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 1005; // Số nút tối đa

vector<int> adj[MAXN]; // Danh sách kề biểu diễn cây
int parent[MAXN];      // parent[i] là cha của nút i
int depth[MAXN];       // depth[i] là độ sâu của nút i (gốc có độ sâu 0)

// Hàm DFS để tính depth và parent
void dfs(int u, int p, int d) {
    parent[u] = p;
    depth[u] = d;
    for (int v : adj[u]) {
        if (v != p) { // Tránh đi ngược về nút cha
            dfs(v, u, d + 1);
        }
    }
}

// Hàm tìm LCA sử dụng parent pointer và depth
int find_lca_basic(int u, int v) {
    // 1. Đưa u và v về cùng độ sâu
    if (depth[u] < depth[v]) {
        swap(u, v); // Đảm bảo u luôn là nút sâu hơn hoặc bằng v
    }

    // Nâng nút sâu hơn (u) lên
    while (depth[u] > depth[v]) {
        u = parent[u];
    }

    // 2. Nếu u và v đã cùng nút (trường hợp 1 nút là tổ tiên của nút kia)
    if (u == v) {
        return u;
    }

    // 3. Đồng thời nâng cả u và v lên cho đến khi gặp nhau
    while (parent[u] != parent[v]) {
        u = parent[u];
        v = parent[v];
    }

    // 4. Nút cha chung đó chính là LCA
    return parent[u];
}

int main() {
    int n = 9; // Số nút trong ví dụ cây

    // Xây dựng cây ví dụ
    adj[1].push_back(2); adj[2].push_back(1);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[2].push_back(4); adj[4].push_back(2);
    adj[2].push_back(5); adj[5].push_back(2);
    adj[3].push_back(6); adj[6].push_back(3);
    adj[4].push_back(7); adj[7].push_back(4);
    adj[6].push_back(8); adj[8].push_back(6);
    adj[6].push_back(9); adj[9].push_back(6);

    // Tiền xử lý: Tính depth và parent (giả sử gốc là 1)
    dfs(1, -1, 0); // Gốc 1, cha giả -1, độ sâu 0

    // Kiểm tra LCA
    cout << "LCA(7, 9) = " << find_lca_basic(7, 9) << endl; // Expected: 1
    cout << "LCA(4, 5) = " << find_lca_basic(4, 5) << endl; // Expected: 2
    cout << "LCA(8, 9) = " << find_lca_basic(8, 9) << endl; // Expected: 6
    cout << "LCA(7, 4) = " << find_lca_basic(7, 4) << endl; // Expected: 4
    cout << "LCA(4, 1) = " << find_lca_basic(4, 1) << endl; // Expected: 1

    return 0;
}

Giải thích mã:

Mảng adj lưu danh sách kề của cây.
Mảng parent lưu nút cha trực tiếp của mỗi nút.
Mảng depth lưu độ sâu của mỗi nút.
Hàm dfs thực hiện duyệt cây để điền đầy đủ thông tin vào parent và depth. Nút gốc được gọi với cha là -1 và độ sâu 0.
Hàm find_lca_basic nhận hai nút u và v. Đầu tiên, nó đảm bảo u là nút sâu hơn hoặc bằng v bằng cách hoán đổi nếu cần. Sau đó, nó dùng vòng while để đưa u lên cùng độ sâu với v. Nếu sau khi nâng mà u == v, thì u (hoặc v) là LCA. Ngược lại, cả u và v được nâng đồng thời lên cho đến khi cha của chúng giống nhau. Nút cha chung đó chính là LCA.

Cách này hiệu quả hơn phương pháp đường đi khi cây không quá sâu. Tuy nhiên, trong trường hợp cây suy biến (ví dụ: một đường thẳng), độ phức tạp truy vấn vẫn là O(N).

Cách tiếp cận 3: Binary Lifting (Nâng nhị phân)

Đây là kỹ thuật mạnh mẽ và hiệu quả nhất cho bài toán LCA khi bạn cần thực hiện nhiều truy vấn trên cùng một cây. Nó sử dụng ý tưởng Quy hoạch động (Dynamic Programming) trên cây.

Ý tưởng chính là tiền xử lý một bảng tra cứu up[u][i] lưu trữ tổ tiên thứ $2^i$ của nút u. Tức là, up[u][i] là tổ tiên của u cách u một khoảng $2^i$ cạnh trên cây.

Để thực hiện cách này, chúng ta cần:

Tiền xử lý:
1. Tính độ sâu (depth[u]) và nút cha trực tiếp (parent[u]) cho mọi nút bằng DFS (tương tự cách 2). Lưu cha trực tiếp vào up[u][0].
2. Sử dụng bảng DP up[u][i] với i từ 1 đến LOGN - 1 (với LOGN là giá trị đủ lớn sao cho $2^{LOGN-1} \ge N$). Ta có công thức chuyển tiếp: up[u][i] = up[ up[u][i-1] ][ i-1 ] Công thức này nói rằng, tổ tiên thứ $2^i$ của u chính là tổ tiên thứ $2^{i-1}$ của nút tổ tiên thứ $2^{i-1}$ của u. Chúng ta lấp đầy bảng này bằng DFS hoặc BFS.
3. Độ phức tạp tiền xử lý: O(N log N), với N là số nút.
Truy vấn LCA(u, v):
1. Đưa u và v về cùng độ sâu. Tương tự cách 2, ta nâng nút sâu hơn lên. Tuy nhiên, thay vì nhảy từng bước một, ta sử dụng bảng up để nhảy một cách "nhị phân". Giả sử u sâu hơn v diff bước. Ta biểu diễn diff dưới dạng nhị phân. Ví dụ, nếu diff = 13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0. Ta sẽ nâng u lên $2^3$ bước, rồi $2^2$ bước, rồi $2^0$ bước. Việc này được thực hiện bằng cách duyệt i từ LOGN-1 xuống 0: nếu bit thứ i của diff là 1, tức là $2^i$ có mặt trong biểu diễn nhị phân của diff, ta nhảy u = up[u][i].
2. Sau khi cùng độ sâu, nếu u == v, trả về u.
3. Nếu u != v, đồng thời nâng u và v lên cho đến khi chúng trở thành con của LCA. Ta duyệt i từ LOGN-1 xuống 0. Nếu up[u][i] != up[v][i], điều đó có nghĩa là tổ tiên thứ $2^i$ của u và v khác nhau. Tức là, LCA của u và v phải nằm cao hơn (gần gốc hơn) tổ tiên thứ $2^i$ này. Do đó, ta an toàn nhảy cả u và v lên vị trí tổ tiên thứ $2^i$ đó: u = up[u][i], v = up[v][i]. Nếu up[u][i] == up[v][i], nghĩa là tổ tiên thứ $2^i$ của chúng đã giống nhau, tức là LCA nằm tại hoặc dưới nút up[u][i]. Ta không nhảy ở bước này để tránh "nhảy quá" LCA.
4. Sau khi vòng lặp kết thúc, u và v sẽ là hai nút khác nhau, nhưng cha của chúng chính là LCA. Ta trả về parent[u] (hoặc up[u][0]).
5. Độ phức tạp truy vấn: O(log N).

Độ phức tạp tổng thể: O(N log N) tiền xử lý + O(log N) cho mỗi truy vấn. Đây là phương pháp tuyệt vời khi số lượng truy vấn Q lớn, bởi vì O(N log N + Q log N) sẽ tốt hơn nhiều so với O(Q * N) của các phương pháp trước.

Mã C++ minh họa:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAXN = 100005; // Số nút tối đa
const int LOGN = 18;     // ceil(log2(MAXN)) + 1, đủ lớn cho cây 10^5 nút (2^17 > 10^5)

vector<int> adj[MAXN]; // Danh sách kề
int depth[MAXN];       // Độ sâu
int up[MAXN][LOGN];    // up[u][i] là tổ tiên thứ 2^i của u

// Hàm DFS tiền xử lý: tính depth và up[u][0], sau đó điền up[u][i]
void dfs_lca(int u, int p, int d) {
    depth[u] = d;
    up[u][0] = p; // Tổ tiên thứ 2^0 (trực tiếp) của u là p

    // Điền bảng up cho i = 1 đến LOGN-1
    for (int i = 1; i < LOGN; ++i) {
        if (up[u][i-1] != -1) { // Nếu tổ tiên thứ 2^(i-1) tồn tại
            up[u][i] = up[ up[u][i-1] ][ i-1 ];
        } else { // Nếu không có tổ tiên thứ 2^(i-1), thì các tổ tiên cao hơn nữa cũng không tồn tại
            up[u][i] = -1;
        }
    }

    // Duyệt các con
    for (int v : adj[u]) {
        if (v != p) { // Tránh đi ngược về cha
            dfs_lca(v, u, d + 1);
        }
    }
}

// Hàm tìm LCA sử dụng Binary Lifting
int find_lca_binary_lifting(int u, int v) {
    // 1. Đưa u và v về cùng độ sâu
    if (depth[u] < depth[v]) {
        swap(u, v); // Đảm bảo u sâu hơn hoặc bằng v
    }

    // Nâng u lên (depth[u] - depth[v]) bước
    int diff = depth[u] - depth[v];
    for (int i = LOGN - 1; i >= 0; --i) {
        // Nếu bit thứ i của diff là 1, tức là cần nhảy 2^i bước
        if (((diff >> i) & 1) && up[u][i] != -1) {
            u = up[u][i];
        }
    }

    // 2. Nếu u và v đã cùng nút (trường hợp 1 nút là tổ tiên của nút kia)
    if (u == v) {
        return u;
    }

    // 3. Đồng thời nâng u và v lên cho đến khi cha của chúng giống nhau
    // Chúng ta nhảy dần lên bằng cách tìm tổ tiên lớn nhất ( xa gốc nhất )
    // mà vẫn khác nhau. Khi vòng lặp kết thúc, u và v sẽ là con của LCA
    for (int i = LOGN - 1; i >= 0; --i) {
        if (up[u][i] != up[v][i] && up[u][i] != -1 && up[v][i] != -1) {
            u = up[u][i];
            v = up[v][i];
        }
    }

    // 4. Nút cha chung đó chính là LCA
    return up[u][0]; // Hoặc up[v][0]
}

int main() {
    int n = 9; // Số nút trong ví dụ cây
    int root = 1; // Gốc của cây

    // Khởi tạo bảng up với giá trị -1
    for(int i = 0; i <= n; ++i) {
        for(int j = 0; j < LOGN; ++j) {
            up[i][j] = -1;
        }
    }

    // Xây dựng cây ví dụ (như trên)
    adj[1].push_back(2); adj[2].push_back(1);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[2].push_back(4); adj[4].push_back(2);
    adj[2].push_back(5); adj[5].push_back(2);
    adj[3].push_back(6); adj[6].push_back(3);
    adj[4].push_back(7); adj[7].push_back(4);
    adj[6].push_back(8); adj[8].push_back(6);
    adj[6].push_back(9); adj[9].push_back(6);

    // Tiền xử lý Binary Lifting
    dfs_lca(root, -1, 0); // Gốc, cha giả -1, độ sâu 0

    // Kiểm tra LCA
    cout << "LCA(7, 9) = " << find_lca_binary_lifting(7, 9) << endl; // Expected: 1
    cout << "LCA(4, 5) = " << find_lca_binary_lifting(4, 5) << endl; // Expected: 2
    cout << "LCA(8, 9) = " << find_lca_binary_lifting(8, 9) << endl; // Expected: 6
    cout << "LCA(7, 4) = " << find_lca_binary_lifting(7, 4) << endl; // Expected: 4
    cout << "LCA(4, 1) = " << find_lca_binary_lifting(4, 1) << endl; // Expected: 1
    cout << "LCA(5, 8) = " << find_lca_binary_lifting(5, 8) << endl; // Expected: 1
    cout << "LCA(6, 9) = " << find_lca_binary_lifting(6, 9) << endl; // Expected: 6


    return 0;
}

Giải thích mã Binary Lifting:

MAXN và LOGN: Định nghĩa kích thước mảng đủ lớn cho số nút và số bậc nhị phân (logarit cơ số 2 của số nút). LOGN cần đủ lớn sao cho $2^{LOGN-1}$ lớn hơn số nút lớn nhất có thể.
up[MAXN][LOGN]: Mảng 2 chiều lưu up[u][i], tổ tiên thứ $2^i$ của nút u. Giá trị -1 thường dùng để biểu thị không có tổ tiên (ví dụ: đã lên đến gốc hoặc vượt quá gốc).
dfs_lca: Hàm DFS này đồng thời tính depth, lưu cha trực tiếp vào up[u][0], và sau đó sử dụng vòng lặp để điền các cột i > 0 của bảng up dựa vào công thức quy hoạch động up[u][i] = up[ up[u][i-1] ][ i-1 ].
find_lca_binary_lifting:
- Đầu tiên, nó nâng nút sâu hơn lên bằng với độ sâu của nút còn lại. Việc nâng được thực hiện bằng cách duyệt các bit của hiệu độ sâu diff. Nếu bit thứ i của diff là 1, tức là ta cần nhảy lên $2^i$ bước, ta sử dụng up[u][i]. Thao tác (diff >> i) & 1 kiểm tra bit thứ i.
- Nếu sau khi cùng độ sâu mà u == v, ta trả về u.
- Nếu u != v, ta bắt đầu vòng lặp từ i = LOGN-1 xuống 0. Ta muốn nhảy cả u và v lên càng cao càng tốt mà chúng vẫn khác nhau. Nếu up[u][i] và up[v][i] khác nhau, điều đó có nghĩa là LCA phải nằm cao hơn (tổ tiên của up[u][i] và up[v][i]). Vì vậy, ta nhảy cả u và v lên vị trí up[u][i] và up[v][i]. Nếu up[u][i] và up[v][i] đã giống nhau, ta không nhảy ở bước này vì LCA có thể là chính nút up[u][i] hoặc nằm dưới đó.
- Sau khi vòng lặp kết thúc, u và v đã được đưa lên vị trí là hai con của LCA. Do đó, cha của u (hoặc v), tức là up[u][0], chính là LCA.

So sánh các cách tiếp cận

Đường đi từ gốc:
- Độ phức tạp tiền xử lý: O(N) để tìm đường đi (nếu cần lưu).
- Độ phức tạp truy vấn: O(N) trong trường hợp xấu nhất.
- Ưu điểm: Đơn giản, dễ hiểu.
- Nhược điểm: Rất kém hiệu quả cho nhiều truy vấn trên cây sâu.
Con trỏ cha & Độ sâu:
- Độ phức tạp tiền xử lý: O(N) (DFS).
- Độ phức tạp truy vấn: O(H) (chiều cao cây), có thể O(N) trong trường hợp xấu nhất.
- Ưu điểm: Khá đơn giản, hiệu quả hơn phương pháp đường đi.
- Nhược điểm: Vẫn kém hiệu quả cho nhiều truy vấn trên cây sâu/suy biến.
Binary Lifting:
- Độ phức tạp tiền xử lý: O(N log N).
- Độ phức tạp truy vấn: O(log N).
- Ưu điểm: Cực kỳ hiệu quả cho nhiều truy vấn LCA. Thời gian truy vấn rất nhanh.
- Nhược điểm: Yêu cầu tiền xử lý và cài đặt phức tạp hơn hai phương pháp trên.

Comments

There are no comments at the moment.