Khóa học CTDL và GT

Bài 24.2. Thuật toán Naive và thuật toán Euler Tour

Chào mừng các bạn đã quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Trong bài viết hôm nay, chúng ta sẽ cùng đi sâu vào một lĩnh vực thú vị: giải quyết các bài toán trên cây. Cây là một cấu trúc dữ liệu đặc biệt quan trọng trong khoa học máy tính, xuất hiện trong rất nhiều ứng dụng thực tế, từ cấu trúc thư mục, hệ thống phân cấp tổ chức, đến các thuật toán phức tạp hơn như phân tích cú pháp hay tìm kiếm.

Khi làm việc với cây, chúng ta thường cần thực hiện các truy vấn (query) hoặc cập nhật (update) liên quan đến đường đi giữa hai nút, tổ tiên chung gần nhất (LCA - Lowest Common Ancestor), hoặc thông tin trên các cây con. Một số phương pháp đầu tiên xuất hiện trong đầu có thể khá đơn giản và trực quan – chúng ta gọi đó là phương pháp "Naive" (ngây thơ, đơn giản). Tuy nhiên, đối với các bài toán yêu cầu nhiều truy vấn lặp đi lặp lại, những phương pháp đơn giản này có thể trở nên cực kỳ kém hiệu quả.

Đây chính là lúc các kỹ thuật tiên tiến hơn tỏa sáng. Một trong những kỹ thuật mạnh mẽ và phổ biến để biến các bài toán trên cây thành các bài toán trên mảng (sequence) quen thuộc là Euler Tour (Chu trình Euler). Mặc dù tên gọi gợi nhớ đến chu trình Euler trong lý thuyết đồ thị tổng quát, kỹ thuật Euler Tour áp dụng cho cây mang một ý nghĩa hơi khác và cực kỳ hữu ích.

Hãy cùng khám phá sự khác biệt giữa phương pháp Naive và sức mạnh của Euler Tour thông qua các ví dụ cụ thể nhé!

1. Phương pháp "Naive" trên Cây

Như đã đề cập, phương pháp "naive" ở đây không phải là một thuật toán cụ thể có tên gọi "Naive Algorithm". Thay vào đó, nó chỉ cách tiếp cận trực tiếp, đơn giản nhất dựa trên định nghĩa của bài toán, thường sử dụng các phép duyệt cây cơ bản như DFS (Depth First Search) hoặc BFS (Breadth First Search), hoặc các thao tác di chuyển trực tiếp trên cây (như đi lên nút cha).

Chúng ta hãy xem xét một bài toán kinh điển trên cây: Tìm Tổ tiên chung gần nhất (LCA) của hai nút u và v. LCA của u và v là nút có độ sâu lớn nhất đồng thời là tổ tiên của cả u và v.

Bài toán ví dụ: Cho một cây có N nút. Cần trả lời Q truy vấn, mỗi truy vấn gồm hai nút u và v, yêu cầu tìm LCA của chúng.

Phương pháp Naive cho bài toán LCA:

Một cách đơn giản để tìm LCA của u và v là làm cho chúng có cùng độ sâu, sau đó cùng lúc đi dần lên nút cha từ cả hai nút cho đến khi gặp nhau. Nút gặp nhau đầu tiên chính là LCA.

Các bước thực hiện:

1. Tính độ sâu (depth) cho tất cả các nút: Có thể dùng DFS hoặc BFS xuất phát từ nút gốc (thường là nút 1). Lưu lại parent (nút cha) của mỗi nút để có thể đi ngược lên sau này.
2. Cân bằng độ sâu: Giả sử depth[u] > depth[v]. Ta sẽ di chuyển u lên depth[u] - depth[v] bước bằng cách đi theo liên kết parent cho đến khi u có cùng độ sâu với v.
3. Đồng thời đi lên: Bây giờ u và v có cùng độ sâu. Ta đồng thời di chuyển cả u và v lên nút cha của chúng trong mỗi bước (u = parent[u], v = parent[v]) cho đến khi u == v.
4. Kết quả: Nút mà u và v gặp nhau lần đầu tiên chính là LCA của chúng. Nếu ban đầu u là tổ tiên của v (hoặc ngược lại), bước 2 sẽ đưa nút có độ sâu lớn hơn lên đến vị trí của nút kia, và bước 3 sẽ kết thúc ngay lập tức khi chúng gặp nhau, trả về nút tổ tiên đó làm LCA (điều này là đúng theo định nghĩa).

Để thực hiện bước 1 (tính độ sâu và cha) chỉ cần O(N) với một lần duyệt DFS. Tuy nhiên, bước 2 và 3 cho mỗi truy vấn LCA có thể mất đến O(H) thời gian, trong đó H là chiều cao của cây. Trong trường hợp xấu nhất (cây suy biến thành danh sách liên kết), H có thể bằng N. Do đó, mỗi truy vấn LCA tốn O(N) thời gian. Với Q truy vấn, tổng thời gian sẽ là O(N + Q*N). Nếu Q và N đều lớn, thuật toán này sẽ rất chậm.

Hãy minh họa bằng code C++ cho việc tính độ sâu và cha:

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

const int MAXN = 1005; // Giả sử số nút tối đa là 1000
std::vector<int> adj[MAXN];
int depth[MAXN];
int parent[MAXN];

// DFS để tính độ sâu và cha
void dfs_naive(int u, int p, int d) {
    depth[u] = d;
    parent[u] = p;
    for (int v : adj[u]) {
        if (v != p) {
            dfs_naive(v, u, d + 1);
        }
    }
}

// Hàm hỗ trợ để đi lên k bước
int go_up(int u, int k) {
    while (u != 0 && k > 0) { // Nút 0 là nút giả hoặc biểu thị không tồn tại cha
        u = parent[u];
        k--;
    }
    return u;
}

// Hàm tìm LCA Naive (cho 2 nút u, v có parent[0] = 0)
// Lưu ý: Nút gốc thường là 1, cha của nút gốc có thể coi là 0 hoặc -1 tùy quy ước
int find_lca_naive(int u, int v) {
    // Cân bằng độ sâu
    if (depth[u] < depth[v]) {
        std::swap(u, v); // Đảm bảo u luôn sâu hơn hoặc bằng v
    }

    u = go_up(u, depth[u] - depth[v]); // Nâng u lên cùng độ sâu với v

    if (u == v) { // Một nút là tổ tiên của nút kia
        return u;
    }

    // Đồng thời đi lên cho đến khi gặp nhau
    while (parent[u] != parent[v]) {
        u = parent[u];
        v = parent[v];
    }
    return parent[u]; // Nút cha của điểm gặp nhau là LCA
}

int main() {
    int N; // Số nút
    std::cin >> N;

    // Đọc cạnh, giả sử cây có N nút từ 1 đến N
    // Nút 1 là gốc, không có cha thực
    // adj[0] sẽ rỗng, depth[0] = -1 (hoặc tùy quy ước), parent[0] = 0
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Thực hiện DFS từ nút gốc (ví dụ nút 1), cha của nút gốc là 0
    dfs_naive(1, 0, 0);

    int Q; // Số truy vấn
    std::cin >> Q;

    for (int i = 0; i < Q; ++i) {
        int u, v;
        std::cin >> u >> v;
        int lca = find_lca_naive(u, v);
        std::cout << "LCA(" << u << ", " << v << ") = " << lca << std::endl;
    }

    return 0;
}

Giải thích code Naive:

• adj: Danh sách kề biểu diễn cây.
• depth: Mảng lưu độ sâu của mỗi nút (độ sâu gốc là 0).
• parent: Mảng lưu nút cha trực tiếp của mỗi nút.
• dfs_naive: Hàm DFS cơ bản để đi qua cây, tính toán depth và parent. Xuất phát từ nút gốc (ví dụ 1), cha của gốc là 0, độ sâu của gốc là 0.
• go_up: Hàm tiện ích giúp đi lên k bước từ một nút u.
• find_lca_naive: Hàm tìm LCA theo phương pháp Naive đã mô tả. Đầu tiên đảm bảo u có độ sâu lớn hơn hoặc bằng v bằng cách hoán đổi nếu cần. Sau đó, nâng u lên cùng độ sâu với v bằng hàm go_up. Nếu u và v chưa gặp nhau, đồng thời nâng cả hai lên nút cha cho đến khi chúng có cùng nút cha. Nút cha đó chính là LCA.

Như phân tích, thuật toán này có thể quá chậm nếu số lượng truy vấn Q lớn. Đây là động lực để tìm kiếm các kỹ thuật hiệu quả hơn, như Euler Tour.

2. Kỹ thuật Euler Tour trên Cây

Euler Tour trên cây là một kỹ thuật biến cấu trúc cây thành một chuỗi phẳng bằng cách ghi lại thứ tự các nút được thăm trong quá trình duyệt DFS. Ý tưởng là khi thực hiện DFS, chúng ta ghi lại nút mỗi khi bước vào nó lần đầu và mỗi khi bước ra khỏi nó sau khi đã thăm hết cây con của nó.

Hãy tưởng tượng bạn đi bộ trên cây, bắt đầu từ gốc. Mỗi khi bạn đi xuống một cạnh (vào một nút con), bạn ghi lại nút con đó. Sau khi thăm hết cây con của nút con đó, bạn đi ngược cạnh đó lên nút cha, và bạn cũng ghi lại nút con đó một lần nữa khi "rời khỏi" nó.

Quá trình này có thể được biểu diễn bằng một mảng (sequence) các nút.

Ví dụ: Xét cây đơn giản: 1 -> 2, 1 -> 3, 2 -> 4. Nút gốc là 1.

Một quá trình duyệt DFS có thể là:

• Vào 1 (ghi 1)
• Từ 1 vào 2 (ghi 2)
• Từ 2 vào 4 (ghi 4)
• Rời 4 lên 2 (ghi 4)
• Hết cây con 4, rời 2 lên 1 (ghi 2)
• Từ 1 vào 3 (ghi 3)
• Hết cây con 3, rời 3 lên 1 (ghi 3)
• Hết cây con 2,3,4, rời 1 (ghi 1)

Chuỗi các nút thu được là: [1, 2, 4, 4, 2, 3, 3, 1].

Đặc điểm của chuỗi Euler Tour:

1. Độ dài: Nếu cây có N nút, chuỗi Euler Tour (ghi lại cả vào và ra) sẽ có độ dài 2N-1. Mỗi cạnh (u, v) được đi qua hai lần (một lần xuống từ u sang v, một lần lên từ v về u), và nút gốc được thăm 1 lần duy nhất ban đầu. Tổng số bước đi qua cạnh là 2(N-1). Thêm 1 bước thăm gốc ban đầu. Tổng số lần ghi nút là 2(N-1) + 1 = 2N-1.
2. Mỗi nút xuất hiện: Mỗi nút trừ gốc xuất hiện đúng 2 lần (lúc vào và lúc ra). Nút gốc xuất hiện 1 lần đầu tiên và 1 lần cuối cùng (nếu coi việc kết thúc DFS tại gốc là "ra khỏi" gốc), hoặc chỉ 1 lần đầu nếu không ghi lại lần "ra" cuối cùng. Thông thường, người ta ghi lại 2N-1 lần.
3. Tính lồng nhau: Đoạn con trong chuỗi Euler Tour nằm giữa lần xuất hiện đầu tiên và lần xuất hiện cuối cùng của một nút u chứa tất cả các nút thuộc cây con gốc u, và chỉ các nút đó (theo thứ tự duyệt).
4. Quan hệ Tổ tiên/Con cháu: Nút u là tổ tiên của nút v khi và chỉ khi lần xuất hiện đầu tiên của u trong chuỗi Euler Tour nằm trước lần xuất hiện đầu tiên của v.

Tại sao Euler Tour lại hữu ích?

Euler Tour biến các mối quan hệ trên cây thành các mối quan hệ trên một mảng tuần tự. Điều này cho phép chúng ta áp dụng các kỹ thuật giải quyết bài toán trên mảng (như Segment Tree, Sparse Table, Fenwick Tree) vào các bài toán trên cây một cách hiệu quả.

Một ứng dụng quan trọng của Euler Tour là giải quyết bài toán LCA nhanh chóng.

Áp dụng Euler Tour cho bài toán LCA:

Nhắc lại chuỗi Euler Tour ví dụ: [1, 2, 4, 4, 2, 3, 3, 1]. Lưu thêm độ sâu tương ứng của các nút: [0, 1, 2, 2, 1, 1, 1, 0] (Nếu gốc có độ sâu 0).

Quan sát: Để tìm LCA(u, v), chúng ta tìm lần xuất hiện đầu tiên của u và v trong chuỗi Euler Tour. Giả sử lần xuất hiện đầu tiên của u là tại index idx_u và của v là tại index idx_v. Không mất tính tổng quát, giả sử idx_u < idx_v.

Định lý: Nút có độ sâu nhỏ nhất trong đoạn chuỗi Euler Tour từ idx_u đến idx_v chính là LCA của u và v.

• Tại sao lại như vậy? Khi đi từ lần thăm đầu tiên của u đến lần thăm đầu tiên của v trong chuỗi Euler Tour, ta phải đi ngược lên từ u đến tổ tiên chung của u và v, sau đó đi xuống đến v. Nút có độ sâu nhỏ nhất trên đường đi này phải là tổ tiên chung gần nhất. Các nút khác trên đường đi ngược lên từ u sẽ có độ sâu nhỏ dần, nhưng nút sâu nhất trong số các tổ tiên chung chính là LCA. Mọi nút khác trên đường đi từ LCA xuống v sẽ có độ sâu lớn hơn LCA. Do đó, nút nông nhất (độ sâu nhỏ nhất) trên đoạn chuỗi đó chính là LCA.

Quy trình tìm LCA bằng Euler Tour + RMQ:

1. Xây dựng Euler Tour: Thực hiện DFS từ gốc. Khi bước vào một nút u, ghi nhận u vào chuỗi Euler Tour, lưu lại entry_time[u] (index lần đầu tiên thăm u), và ghi nhận độ sâu của u. Khi bước ra khỏi u (sau khi thăm hết cây con của nó), lại ghi nhận u vào chuỗi Euler Tour.
2. Xây dựng mảng độ sâu: Tạo một mảng mới chỉ chứa độ sâu của các nút theo thứ tự xuất hiện trong chuỗi Euler Tour.
3. Xây dựng cấu trúc dữ liệu RMQ: Xây dựng một cấu trúc dữ liệu Range Minimum Query (Truy vấn Minimum trên một đoạn) trên mảng độ sâu này. Các cấu trúc phổ biến là Sparse Table (O(N log N) tiền xử lý, O(1) truy vấn) hoặc Segment Tree (O(N) tiền xử lý, O(log N) truy vấn).
4. Trả lời truy vấn LCA(u, v): Tìm idx_u = entry_time[u] và idx_v = entry_time[v]. Giả sử idx_u < idx_v. Sử dụng cấu trúc RMQ đã xây dựng để tìm index min_idx của phần tử có giá trị nhỏ nhất (độ sâu nhỏ nhất) trong mảng độ sâu trên đoạn từ idx_u đến idx_v. Nút tại vị trí min_idx trong chuỗi Euler Tour chính là LCA của u và v.

Độ phức tạp:

• Xây dựng Euler Tour: O(N) bằng DFS.
• Xây dựng mảng độ sâu và entry_time: O(N).
• Xây dựng cấu trúc RMQ: O(N log N) cho Sparse Table, O(N) cho Segment Tree (phiên bản đặc biệt).
• Truy vấn LCA: O(1) với Sparse Table, O(log N) với Segment Tree.

Tổng cộng, sau O(N log N) hoặc O(N) tiền xử lý, mỗi truy vấn LCA chỉ tốn O(1) hoặc O(log N) thời gian. Điều này hiệu quả hơn rất nhiều so với O(N) cho mỗi truy vấn của phương pháp Naive khi Q lớn.

Hãy xem code C++ minh họa cách tạo chuỗi Euler Tour và lưu trữ thông tin cần thiết:

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

const int MAXN = 1005; // Giả sử số nút tối đa là 1000
std::vector<int> adj[MAXN];

// --- Thông tin cần thiết cho Euler Tour ---
std::vector<int> euler_tour_nodes; // Chuỗi các nút trong Euler Tour
std::vector<int> euler_tour_depths; // Độ sâu tương ứng
int entry_time[MAXN]; // Index lần đầu tiên xuất hiện của nút trong euler_tour_nodes
int timer = 0; // Biến đếm thời gian/index trong tour
int node_at_euler_index[MAXN * 2]; // Nút tại index i trong euler_tour_nodes

// DFS để xây dựng Euler Tour
void dfs_euler(int u, int p, int d) {
    euler_tour_nodes.push_back(u);
    euler_tour_depths.push_back(d);
    entry_time[u] = timer;
    node_at_euler_index[timer] = u;
    timer++;

    for (int v : adj[u]) {
        if (v != p) {
            dfs_euler(v, u, d + 1);
            // Khi đi hết cây con của v và quay về u, ghi lại v
            euler_tour_nodes.push_back(u); // Ghi lại nút cha (u) khi quay về từ con (v)
            euler_tour_depths.push_back(d);
            node_at_euler_index[timer] = u;
            timer++;
        }
    }
}

// Để đơn giản hóa ví dụ này, chúng ta sẽ không code hoàn chỉnh Sparse Table hay Segment Tree
// mà chỉ dừng lại ở việc tạo ra chuỗi Euler Tour và mảng độ sâu.
// Việc tìm RMQ trên euler_tour_depths_array[entry_time[u] ... entry_time[v]]
// là bước tiếp theo sử dụng cấu trúc dữ liệu RMQ.

int main() {
    int N; // Số nút
    std::cin >> N;

    // Đọc cạnh, giả sử cây có N nút từ 1 đến N
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Thực hiện DFS từ nút gốc (ví dụ nút 1), độ sâu của gốc là 0
    // parent của gốc không cần thiết cho Euler Tour này
    dfs_euler(1, 0, 0); // Gốc 1, cha giả định 0, độ sâu 0

    // In ra chuỗi Euler Tour và độ sâu
    std::cout << "Euler Tour Nodes: ";
    for (int node : euler_tour_nodes) {
        std::cout << node << " ";
    }
    std::cout << std::endl;

    std::cout << "Euler Tour Depths: ";
    for (int d : euler_tour_depths) {
        std::cout << d << " ";
    }
    std::cout << std::endl;

    std::cout << "Entry Times (first appearance index):" << std::endl;
    for (int i = 1; i <= N; ++i) {
        std::cout << "Node " << i << ": " << entry_time[i] << std::endl;
    }

    // Ví dụ về cách tìm LCA(u, v) sau khi có Euler Tour và RMQ:
    // int u, v; cin >> u >> v;
    // int start_idx = min(entry_time[u], entry_time[v]);
    // int end_idx = max(entry_time[u], entry_time[v]);
    // int index_of_min_depth = query_rmq(start_idx, end_idx); // Hàm query_rmq từ cấu trúc RMQ
    // int lca_node = node_at_euler_index[index_of_min_depth];
    // cout << "LCA(" << u << ", " << v << ") = " << lca_node << endl;


    // Phần code cho truy vấn LCA thực tế sẽ cần thêm cài đặt Sparse Table hoặc Segment Tree
    // trên mảng euler_tour_depths. Phần này không được bao gồm ở đây để giữ ví dụ tập trung vào Euler Tour.

    return 0;
}

Giải thích code Euler Tour:

• euler_tour_nodes: Vector lưu trữ chuỗi các nút theo thứ tự duyệt.
• euler_tour_depths: Vector lưu trữ độ sâu tương ứng của các nút trong euler_tour_nodes.
• entry_time: Mảng lưu trữ chỉ số (index) lần đầu tiên một nút xuất hiện trong euler_tour_nodes.
• timer: Biến đếm tăng dần, dùng làm chỉ số cho euler_tour_nodes và euler_tour_depths.
• node_at_euler_index: Mảng giúp tra ngược từ chỉ số trong chuỗi Euler Tour ra nút tương ứng.
• dfs_euler: Hàm DFS chính để tạo Euler Tour.
  • Khi thăm nút u lần đầu (if (v != p)), ta push_back(u) vào euler_tour_nodes, push_back(d) vào euler_tour_depths, ghi nhận entry_time[u] = timer, và node_at_euler_index[timer] = u. Sau đó tăng timer.
  • Đệ quy gọi dfs_euler(v, u, d + 1) để thăm cây con của v.
  • Quan trọng: Sau khi lời gọi đệ quy cho v kết thúc (tức là đã thăm hết cây con của v), ta lại push_back(u) vào euler_tour_nodes và push_back(d) vào euler_tour_depths, node_at_euler_index[timer] = u, và tăng timer. Đây là lúc "bước ra" khỏi cây con của v và quay về u.
• Code main chỉ minh họa việc đọc input và gọi dfs_euler, sau đó in kết quả của chuỗi Euler Tour và entry_time. Phần sử dụng Euler Tour để trả lời truy vấn LCA thực tế (tìm RMQ trên mảng độ sâu) được mô tả bằng comment vì nó yêu cầu cài đặt thêm cấu trúc dữ liệu RMQ.

3. So sánh: Khi nào dùng gì?