Bài 8.1. Set và các thao tác tìm kiếm cơ bản

Chào mừng các bạn quay trở lại với series về Cấu trúc dữ liệu và Giải thuật! Sau khi tìm hiểu về các cấu trúc dữ liệu tuyến tính như Mảng, Danh sách liên kết hay cấu trúc phi tuyến tính như Cây, hôm nay chúng ta sẽ đào sâu vào một cấu trúc dữ liệu đặc biệt và cực kỳ hữu ích: Set (Tập hợp).

Hãy tưởng tượng bạn cần lưu trữ một bộ sưu tập các mục, nhưng với một quy tắc vàng: không được có bất kỳ mục nào bị trùng lặp. Nếu một mục đã tồn tại, việc cố gắng thêm nó lần nữa sẽ không làm thay đổi bộ sưu tập. Đây chính là lúc Set tỏa sáng!

Set là gì?

Theo định nghĩa toán học, một tập hợp là một bộ sưu tập các đối tượng phân biệt. Trong lập trình, Set là một cấu trúc dữ liệu trừu tượng (Abstract Data Type - ADT) thể hiện ý tưởng này. Nó lưu trữ một tập hợp các phần tử, đảm bảo rằng mọi phần tử trong Set là duy nhất.

Một điểm quan trọng nữa về Set là các phần tử không được lưu trữ theo một thứ tự cụ thể nào theo định nghĩa trừu tượng. Tuy nhiên, các cài đặt cụ thể (như trong C++) có thể duy trì thứ tự (ví dụ: sắp xếp) để phục vụ cho hiệu quả thao tác.

Đặc điểm chính của Set

Tính duy nhất (Uniqueness): Đây là đặc điểm quan trọng nhất. Mỗi phần tử chỉ xuất hiện tối đa một lần trong Set. Khi bạn cố gắng thêm một phần tử đã tồn tại, thao tác thêm sẽ được bỏ qua.
Không có thứ tự (Unordered - khái niệm trừu tượng): Về mặt lý thuyết, các phần tử trong Set không có chỉ mục (index) hay vị trí cố định như trong mảng hay danh sách. Bạn không truy cập phần tử bằng vị trí mà bằng giá trị của nó. (Lưu ý: Cài đặt std::set trong C++ có duy trì thứ tự sắp xếp, nhưng đó là chi tiết cài đặt, không phải bản chất của ADT Set).
Các thao tác hiệu quả: Set được thiết kế để thực hiện các thao tác thêm, xóa và kiểm tra sự tồn tại của phần tử (đây chính là tìm kiếm cơ bản) một cách rất hiệu quả.

Cài đặt Set trong C++: `std::set` và `std::unordered_set`

Thư viện chuẩn C++ cung cấp hai container phổ biến để triển khai Set:

std::set:
- Sử dụng cấu trúc dữ liệu cây tìm kiếm nhị phân cân bằng (thường là Red-Black Tree).
- Ưu điểm: Các phần tử được lưu trữ theo thứ tự đã sắp xếp. Các thao tác insert, erase, find có độ phức tạp thời gian là O(log N), trong đó N là số lượng phần tử trong set.
- Nhược điểm: Chậm hơn std::unordered_set đối với các thao tác trung bình, yêu cầu các phần tử có thể so sánh được (<).
std::unordered_set:
- Sử dụng cấu trúc dữ liệu bảng băm (Hash Table).
- Ưu điểm: Các phần tử không được lưu trữ theo thứ tự. Các thao tác insert, erase, find có độ phức tạp thời gian trung bình là O(1) (hằng số).
- Nhược điểm: Độ phức tạp trong trường hợp xấu nhất có thể là O(N) (dù hiếm gặp), yêu cầu các phần tử có hàm băm (hash function) và có thể so sánh bằng (==).

Trong bài này, chúng ta sẽ tập trung vào cách sử dụng và các thao tác cơ bản, đặc biệt là thao tác tìm kiếm (kiểm tra sự tồn tại), trên cả hai loại Set này.

Các thao tác cơ bản với Set trong C++

Hãy cùng xem cách thực hiện các thao tác thêm, xóa và kiểm tra sự tồn tại (tìm kiếm) với std::set và std::unordered_set thông qua các ví dụ minh họa bằng C++.

Để sử dụng std::set, bạn cần include header <set>. Để sử dụng std::unordered_set, bạn cần include header <unordered_set>.

#include <iostream>
#include <set>         // Cho std::set
#include <unordered_set> // Cho std::unordered_set
#include <string>

int main() {
    // Ví dụ với std::set (lưu trữ có thứ tự)
    std::cout << "--- Su dung std::set (sap xep) ---" << std::endl;

    // 1. Khởi tạo một Set chứa các số nguyên
    std::set<int> mySet;
    std::cout << "Set ban dau: Rong" << std::endl;

    // 2. Thêm phần tử (Insert)
    // Thao tac insert() tra ve mot pair:
    // first: mot iterator tro den phan tu duoc chen hoac phan tu da ton tai
    // second: mot boolean cho biet phan tu co duoc chen moi hay khong

    std::cout << "\n--- Them phan tu ---" << std::endl;
    auto result1 = mySet.insert(10); // Them 10
    if (result1.second) {
        std::cout << "Da them phan tu 10 thanh cong." << std::endl;
    } else {
        std::cout << "Phan tu 10 da ton tai." << std::endl;
    }

    auto result2 = mySet.insert(20); // Them 20
     if (result2.second) {
        std::cout << "Da them phan tu 20 thanh cong." << std::endl;
    } else {
        std::cout << "Phan tu 20 da ton tai." << std::endl;
    }

    auto result3 = mySet.insert(10); // Them 10 lan nua -> se bi bo qua vi da ton tai
     if (result3.second) {
        std::cout << "Da them phan tu 10 thanh cong." << std::endl;
    } else {
        std::cout << "Phan tu 10 da ton tai." << std::endl;
    }

    mySet.insert(30);
    mySet.insert(5);
    mySet.insert(20); // Them 20 lan nua

    std::cout << "Set sau khi them: ";
    // Duyet Set - std::set duyet theo thu tu tang dan
    for (int val : mySet) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
    std::cout << "Kich thuoc cua Set: " << mySet.size() << std::endl; // Kich thuoc se la 4 (5, 10, 20, 30)

    // 3. Kiểm tra sự tồn tại của phần tử (Search / Membership Test)
    // Thao tac find(): tra ve iterator tro den phan tu neu tim thay,
    // hoac tra ve set.end() neu khong tim thay.
    // Day chinh la thao tac tim kiem co ban tren Set.

    std::cout << "\n--- Tim kiem phan tu ---" << std::endl;
    int searchValue1 = 20;
    if (mySet.find(searchValue1) != mySet.end()) {
        std::cout << "Phan tu " << searchValue1 << " ton tai trong Set." << std::endl;
    } else {
        std::cout << "Phan tu " << searchValue1 << " khong ton tai trong Set." << std::endl;
    }

    int searchValue2 = 15;
     if (mySet.find(searchValue2) != mySet.end()) {
        std::cout << "Phan tu " << searchValue2 << " ton tai trong Set." << std::endl;
    } else {
        std::cout << "Phan tu " << searchValue2 << " khong ton tai trong Set." << std::endl;
    }

    // Mot cach khac de kiem tra su ton tai la dung count()
    // Doi voi Set, count() tra ve 1 neu phan tu ton tai, va 0 neu khong.
    std::cout << "Su dung count() de kiem tra:" << std::endl;
    if (mySet.count(10) > 0) {
        std::cout << "Phan tu 10 ton tai (dung count())." << std::endl;
    }
    if (mySet.count(100) == 0) {
        std::cout << "Phan tu 100 khong ton tai (dung count())." << std::endl;
    }

    // 4. Xóa phần tử (Erase)
    // Thao tac erase(value): xoa phan tu co gia tri value neu no ton tai.
    // Tra ve so luong phan tu da xoa (doi voi Set la 0 hoac 1).

    std::cout << "\n--- Xoa phan tu ---" << std::endl;
    int eraseValue1 = 20;
    size_t erasedCount1 = mySet.erase(eraseValue1);
    if (erasedCount1 > 0) {
        std::cout << "Da xoa phan tu " << eraseValue1 << " thanh cong." << std::endl;
    } else {
        std::cout << "Phan tu " << eraseValue1 << " khong ton tai trong Set, khong xoa." << std::endl;
    }

    int eraseValue2 = 100;
    size_t erasedCount2 = mySet.erase(eraseValue2);
    if (erasedCount2 > 0) {
        std::cout << "Da xoa phan tu " << eraseValue2 << " thanh cong." << std::endl;
    } else {
        std::cout << "Phan tu " << eraseValue2 << " khong ton tai trong Set, khong xoa." << std::endl;
    }

    std::cout << "Set sau khi xoa: ";
    for (int val : mySet) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
    std::cout << "Kich thuoc cua Set: " << mySet.size() << std::endl; // Kich thuoc con 3 (5, 10, 30)


    // --- Ví dụ với std::unordered_set (lưu trữ không theo thứ tự) ---
    std::cout << "\n--- Su dung std::unordered_set (khong sap xep) ---" << std::endl;

    // 1. Khởi tạo một Unordered Set chứa các chuỗi
    std::unordered_set<std::string> myUnorderedSet;
    std::cout << "Unordered Set ban dau: Rong" << std::endl;

    // 2. Thêm phần tử (Insert)
    std::cout << "\n--- Them phan tu ---" << std::endl;
    myUnorderedSet.insert("apple");
    myUnorderedSet.insert("banana");
    myUnorderedSet.insert("orange");
    myUnorderedSet.insert("apple"); // Them "apple" lan nua -> bi bo qua

    std::cout << "Unordered Set sau khi them: ";
    // Duyet Unordered Set - thu tu co the khong giong thu tu them vao
    for (const std::string& str : myUnorderedSet) {
        std::cout << str << " ";
    }
    std::cout << std::endl;
    std::cout << "Kich thuoc cua Unordered Set: " << myUnorderedSet.size() << std::endl; // Kich thuoc la 3 ("apple", "banana", "orange")


    // 3. Kiểm tra sự tồn tại của phần tử (Search / Membership Test)
    // Tuong tu nhu std::set, dung find() hoac count().
    // find() tra ve iterator tro den phan tu hoac unordered_set.end().
    // count() tra ve 1 hoac 0.

    std::cout << "\n--- Tim kiem phan tu ---" << std::endl;
    std::string searchString1 = "banana";
    if (myUnorderedSet.count(searchString1) > 0) { // Su dung count() cho don gian
        std::cout << "Phan tu \"" << searchString1 << "\" ton tai trong Unordered Set." << std::endl;
    } else {
        std::cout << "Phan tu \"" << searchString1 << "\" khong ton tai trong Unordered Set." << std::endl;
    }

    std::string searchString2 = "grape";
     if (myUnorderedSet.count(searchString2) > 0) {
        std::cout << "Phan tu \"" << searchString2 << "\" ton tai trong Unordered Set." << std::endl;
    } else {
        std::cout << "Phan tu \"" << searchString2 << "\" khong ton tai trong Unordered Set." << std::endl;
    }

    // 4. Xóa phần tử (Erase)
    // Tuong tu nhu std::set, dung erase(value).

    std::cout << "\n--- Xoa phan tu ---" << std::endl;
    std::string eraseString1 = "orange";
    size_t erasedUnorderedCount1 = myUnorderedSet.erase(eraseString1);
     if (erasedUnorderedCount1 > 0) {
        std::cout << "Da xoa phan tu \"" << eraseString1 << "\" thanh cong." << std::endl;
    } else {
        std::cout << "Phan tu \"" << eraseString1 << "\" khong ton tai trong Unordered Set, khong xoa." << std::endl;
    }

    std::string eraseString2 = "kiwi";
    size_t erasedUnorderedCount2 = myUnorderedSet.erase(eraseString2);
     if (erasedUnorderedCount2 > 0) {
        std::cout << "Da xoa phan tu \"" << eraseString2 << "\" thanh cong." << std::endl;
    } else {
        std::cout << "Phan tu \"" << eraseString2 << "\" khong ton tai trong Unordered Set, khong xoa." << std::endl;
    }

    std::cout << "Unordered Set sau khi xoa: ";
    for (const std::string& str : myUnorderedSet) {
        std::cout << str << " ";
    }
    std::cout << std::endl;
    std::cout << "Kich thuoc cua Unordered Set: " << myUnorderedSet.size() << std::endl; // Kich thuoc con 2 ("apple", "banana")


    return 0;
}

Giải thích chi tiết về code

Include Headers: Chúng ta cần <set> cho std::set và <unordered_set> cho std::unordered_set. <iostream> để in ra màn hình và <string> cho ví dụ với chuỗi.
Khởi tạo: std::set<int> mySet; và std::unordered_set<std::string> myUnorderedSet; tạo ra các Set rỗng sẵn sàng chứa các phần tử thuộc kiểu dữ liệu đã khai báo (int và string).
Thao tác insert():
- Đây là cách bạn thêm phần tử vào Set.
- mySet.insert(10); sẽ thêm số 10 vào mySet.
- Nếu phần tử đã tồn tại, insert() sẽ không thêm bản sao và Set vẫn giữ nguyên số lượng phần tử duy nhất.
- insert() trả về một std::pair. Phần tử .second của pair là một bool cho biết liệu việc thêm có thành công (thêm mới) hay không. Điều này rất hữu ích khi bạn cần biết liệu một phần tử đã tồn tại trước khi cố gắng thêm hay không.
- Đối với std::set, việc thêm phần tử duy trì thứ tự được sắp xếp. Với std::unordered_set, thứ tự thêm vào không ảnh hưởng đến thứ tự lưu trữ bên trong (thường là dựa vào hàm băm).
Thao tác find() (Tìm kiếm):
- Đây là thao tác tìm kiếm cơ bản trên Set.
- mySet.find(searchValue) tìm kiếm searchValue trong mySet.
- Nó trả về một iterator trỏ đến phần tử đó nếu tìm thấy.
- Nếu phần tử không tồn tại, nó sẽ trả về mySet.end().
- So sánh kết quả của find() với set.end() là cách tiêu chuẩn để kiểm tra xem một phần tử có trong Set hay không.
- Độ phức tạp của find() là O(log N) cho std::set và O(1) trung bình cho std::unordered_set.
Thao tác count() (Tìm kiếm/Kiểm tra sự tồn tại):
- Một cách khác, thường đơn giản hơn cho Set, để kiểm tra sự tồn tại.
- mySet.count(value) trả về số lần value xuất hiện trong Set. Vì Set chỉ chứa các phần tử duy nhất, count() sẽ chỉ trả về 1 nếu phần tử tồn tại và 0 nếu không tồn tại.
- Độ phức tạp tương tự find(): O(log N) cho std::set và O(1) trung bình cho std::unordered_set. Thường thích hợp hơn find() khi bạn chỉ cần biết sự tồn tại chứ không cần iterator đến phần tử.
Thao tác erase() (Xóa):
- mySet.erase(eraseValue) xóa phần tử có giá trị eraseValue khỏi Set nếu nó tồn tại.
- Nó trả về số lượng phần tử đã bị xóa (luôn là 0 hoặc 1 đối với Set).
- Độ phức tạp của erase() cũng là O(log N) cho std::set và O(1) trung bình cho std::unordered_set.
Thao tác size(): Trả về số lượng phần tử hiện có trong Set.
Duyệt (Iteration): Bạn có thể dùng vòng lặp dựa trên phạm vi (range-based for loop) hoặc iterator truyền thống để duyệt qua tất cả các phần tử trong Set.
- Với std::set, các phần tử sẽ được duyệt theo thứ tự đã sắp xếp.
- Với std::unordered_set, thứ tự duyệt là không xác định (dựa trên cấu trúc băm nội bộ).

Khi nào nên sử dụng Set?

Set là lựa chọn tuyệt vời khi bạn cần:

Lưu trữ một bộ sưu tập các mục duy nhất.
Thường xuyên cần kiểm tra xem một mục có tồn tại trong bộ sưu tập hay không (thao tác tìm kiếm).
Thường xuyên cần thêm hoặc xóa các mục.

Ví dụ thực tế:

Lưu trữ danh sách các email đăng ký duy nhất.
Tìm các từ duy nhất trong một văn bản.
Theo dõi các ID người dùng duy nhất đang hoạt động.
Xây dựng các thuật toán liên quan đến lý thuyết tập hợp (giao, hợp, hiệu - mặc dù các thao tác này là nâng cao hơn tìm kiếm cơ bản).

Lựa chọn giữa `std::set` và `std::unordered_set`

Chọn std::set nếu bạn cần các phần tử được sắp xếp và/hoặc độ phức tạp O(log N) là chấp nhận được (hoặc cần độ phức tạp worst-case được đảm bảo).
Chọn std::unordered_set nếu bạn không quan tâm đến thứ tự của các phần tử và cần hiệu suất trung bình O(1) cho các thao tác chính (thêm, xóa, tìm kiếm). Đây thường là lựa chọn nhanh hơn cho các thao tác đơn lẻ.

Bài tập ví dụ:

Dòng bí ẩn

Trong một buổi nghiên cứu lịch sử, FullHouse Dev được một nhà sử học nhờ giúp đỡ phân tích cây phả hệ của một vương quốc cổ. Với kinh nghiệm trong việc xử lý dữ liệu, FullHouse Dev đã nhận lời giúp đỡ để khám phá mối quan hệ tổ tiên giữa các thành viên hoàng tộc.

Bài toán

FullHouse Dev nhận được một cây gia phả hoàng tộc, được biểu diễn dưới dạng cấu trúc cây. Cây chứa thông tin về nhiều thế hệ tổ tiên và hậu duệ. Nhiệm vụ của nhóm là trả lời một loạt các truy vấn để xác định mối quan hệ tổ tiên. Với mỗi truy vấn gồm hai cái tên, gọi là Person \(u\) và Person \(v\), trong đó Person \(u\) là gốc của cây gia phả. Nhóm cần xác định xem Person \(u\) có phải là tổ tiên của Person \(v\) hay không. Nếu Person \(u\) là tổ tiên của Person \(v\), cần trả lời "YES", ngược lại trả lời "NO".

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(N\) - số lượng nút trong cây gia phả
Dòng thứ hai chứa số nguyên \(Q\) - số lượng truy vấn
\(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) thể hiện mối quan hệ tổ tiên giữa nút \(x\) và \(y\) trong cây gia phả
\(Q\) dòng cuối cùng, mỗi dòng chứa hai số nguyên \(u\) và \(v\) biểu thị truy vấn cần xác định mối quan hệ

OUTPUT FORMAT:

Với mỗi truy vấn, in ra "YES" nếu Person \(u\) là tổ tiên của Person \(v\), hoặc "NO" nếu không phải

Ràng buộc:

\(1 \leq N \leq 10^5\)
\(1 \leq Q \leq 10^5\)

Ví dụ

INPUT

OUTPUT

YES
NO
NO

Giải thích

Ở truy vấn 1: 1 là tổ tiên của 3
Ở truy vấn 2: 6 không phải là tổ tiên của 5
Ở truy vấn 3: 2 không phải là tổ tiên của 3

Tuyệt vời, bài toán này là một ứng dụng kinh điển của việc duyệt cây (DFS) và sử dụng thời gian thăm nút.

Đây là hướng giải ngắn gọn bằng C++:

Biểu diễn cây: Sử dụng danh sách kề (adjacency list) để lưu trữ cây. Vì đề bài cho x y thể hiện x là tổ tiên của y, ta có thể hiểu x là cha và y là con. Xây dựng danh sách kề mà adj[x] chứa các con trực tiếp của x.
Xác định tổ tiên bằng thời gian thăm: Một nút u là tổ tiên của nút v trong cây khi và chỉ khi nút v nằm trong cây con (subtree) gốc u. Ta có thể kiểm tra điều này hiệu quả bằng cách sử dụng thời gian thăm (entry time - tin) và thời gian rời (exit time - tout) của mỗi nút khi thực hiện duyệt cây DFS từ gốc.
- Thực hiện một lần duyệt DFS toàn bộ cây bắt đầu từ gốc (thường là nút 1 hoặc nút duy nhất không là con của ai).
- Dùng một bộ đếm thời gian (timer). Khi bắt đầu thăm một nút i, gán tin[i] = ++timer. Khi kết thúc thăm nút i và toàn bộ cây con của nó, gán tout[i] = ++timer.
Kiểm tra truy vấn: Với mỗi truy vấn u và v, u là tổ tiên của v nếu và chỉ nếu tin[u] <= tin[v] và tout[u] >= tout[v].
- Điều kiện tin[u] <= tin[v] nghĩa là u được thăm trước hoặc cùng lúc với v.
- Điều kiện tout[u] >= tout[v] nghĩa là quá trình duyệt cây con của u kết thúc sau hoặc cùng lúc với quá trình duyệt cây con của v.
- Cả hai điều kiện này cùng đúng khi và chỉ khi v nằm trong cây con của u, tức là u là tổ tiên của v.

Tóm lại các bước:

Đọc N, Q.
Khởi tạo danh sách kề adj, mảng tin, tout kích thước N+1, và biến timer = 0.
Đọc N-1 cạnh, thêm y vào danh sách kề của x: adj[x].push_back(y).
Chạy DFS từ gốc (thường là nút 1): dfs(1). Trong hàm dfs(u):
- tin[u] = ++timer;
- Duyệt qua các con v của u: dfs(v);
- tout[u] = ++timer;
Đọc Q truy vấn u, v.
Với mỗi truy vấn, kiểm tra if (tin[u] <= tin[v] && tout[u] >= tout[v]).
In "YES" hoặc "NO" tương ứng.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.