Cấu trúc dữ liệu chuỗi

🌳 Trie / Prefix Tree: Lưu chuỗi theo tiền tố

Trie là cây ký tự giúp lưu nhiều từ có chung tiền tố một cách trực quan và hiệu quả. Bài này tập trung vào insert, search, startsWith, đếm số từ theo prefix và cách nhìn cấu trúc Trie khi làm bài thi.

insertThêm từ vào cây
searchTìm từ hoàn chỉnh
prefixKiểm tra tiền tố
pass/endĐếm và đánh dấu từ
Mục tiêuÝ tưởngMô phỏngCodeỨng dụngLỗiBài tậpQuiz

Mục tiêu bài học Trie

Học xong cần làm được

  • Hiểu Trie là cây lưu chuỗi theo từng ký tự.
  • Cài đặt được insert, search, startsWith.
  • Phân biệt end và pass.
  • Biết dùng Trie cho bài từ điển, prefix, autocomplete.

Ví dụ đời sống

  • Gõ “ca” thì điện thoại gợi ý “cat”, “car”, “cart”.
  • Từ điển cần kiểm tra từ có tồn tại hay không.
  • Hệ thống tìm kiếm cần đếm số từ bắt đầu bằng một tiền tố.

1. Trie hoạt động như thế nào?

child

Mỗi nút có các cạnh tới ký tự tiếp theo, thường lưu bằng dictionary/map hoặc mảng 26 phần tử.

end

Đánh dấu một từ hoàn chỉnh kết thúc tại nút hiện tại.

pass

Đếm có bao nhiêu từ đi qua nút này, dùng để đếm prefix.

Ý tưởng cốt lõi: các từ có chung tiền tố sẽ dùng chung đường đi trong cây, giúp tiết kiệm so sánh và truy vấn prefix nhanh.
Không nhầm: search("ca") có thể sai nếu “ca” chưa phải từ hoàn chỉnh, nhưng startsWith("ca") đúng nếu có “cat”, “car”.

2. Mô phỏng cấu trúc Trie

Cách đọc mô phỏng:
Nút có dấu ✓ nghĩa là end = true. Chỉ số pass cho biết có bao nhiêu từ đi qua nút đó.
Nhấn “Dựng Trie” để xem cây ký tự.

Bảng thông tin nút

3. Code Trie rõ ràng

class TrieNode:
    def __init__(self):
        self.child = {}
        self.end = False
        self.pass_count = 0


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, s):
        node = self.root
        node.pass_count += 1
        for c in s:
            if c not in node.child:
                node.child[c] = TrieNode()
            node = node.child[c]
            node.pass_count += 1
        node.end = True

    def search(self, s):
        node = self.root
        for c in s:
            if c not in node.child:
                return False
            node = node.child[c]
        return node.end

    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.child:
                return False
            node = node.child[c]
        return True

    def count_prefix(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.child:
                return 0
            node = node.child[c]
        return node.pass_count


trie = Trie()
for word in ["cat", "car", "cart", "dog"]:
    trie.insert(word)

print(trie.search("car"))       # True
print(trie.starts_with("ca"))   # True
print(trie.count_prefix("ca"))  # 3
#include 
using namespace std;

struct Trie {
    struct Node {
        int child[26];
        bool end;
        int pass;
        Node() {
            memset(child, -1, sizeof(child));
            end = false;
            pass = 0;
        }
    };

    vector nodes;

    Trie() {
        nodes.push_back(Node());
    }

    void insert(const string& s) {
        int cur = 0;
        nodes[cur].pass++;
        for (char ch : s) {
            int c = ch - 'a';
            if (nodes[cur].child[c] == -1) {
                nodes[cur].child[c] = nodes.size();
                nodes.push_back(Node());
            }
            cur = nodes[cur].child[c];
            nodes[cur].pass++;
        }
        nodes[cur].end = true;
    }

    bool search(const string& s) {
        int cur = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (nodes[cur].child[c] == -1) return false;
            cur = nodes[cur].child[c];
        }
        return nodes[cur].end;
    }

    bool startsWith(const string& prefix) {
        int cur = 0;
        for (char ch : prefix) {
            int c = ch - 'a';
            if (nodes[cur].child[c] == -1) return false;
            cur = nodes[cur].child[c];
        }
        return true;
    }

    int countPrefix(const string& prefix) {
        int cur = 0;
        for (char ch : prefix) {
            int c = ch - 'a';
            if (nodes[cur].child[c] == -1) return 0;
            cur = nodes[cur].child[c];
        }
        return nodes[cur].pass;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("cart");
    trie.insert("dog");

    cout << trie.search("car") << "
";
    cout << trie.startsWith("ca") << "
";
    cout << trie.countPrefix("ca") << "
";
    return 0;
}

4. Ứng dụng Trie

Dạng bàiCách dùng TrieLưu ý
Kiểm tra từ trong từ điểninsert tất cả từ, sau đó search.Cần end để phân biệt từ hoàn chỉnh.
Kiểm tra tiền tốDuyệt theo prefix, nếu đi được hết thì tồn tại prefix.Không nhất thiết node cuối có end.
Đếm số từ có prefixLưu pass_count ở mỗi node.Tăng pass khi insert.
AutocompleteTìm node prefix rồi DFS từ node đó.Cần giới hạn số gợi ý để tránh quá nhiều kết quả.

5. Lỗi hay nhầm

Nhầm search và startsWith.
search cần từ hoàn chỉnh, startsWith chỉ cần đường đi prefix tồn tại.
Quên end.
Không có end thì không biết node nào là kết thúc từ.
Quên pass_count khi đếm prefix.
Nếu chỉ có end, muốn đếm prefix sẽ phải DFS lại.
Dùng mảng 26 cho dữ liệu không chỉ gồm a-z.
Nếu có chữ hoa, số, ký tự đặc biệt, nên dùng map/dictionary hoặc chuẩn hóa input.

6. Bài tập Trie phân tầng

📘 Cơ bản

  1. Thêm danh sách từ và kiểm tra một từ có tồn tại không.
  2. Kiểm tra có từ nào bắt đầu bằng prefix p không.
  3. Đếm số từ có cùng tiền tố.

📗 Trung bình

  1. In tất cả từ có prefix p.
  2. Kiểm tra danh sách số điện thoại có số nào là prefix của số khác không.
  3. Đếm số từ khác nhau sau khi thêm nhiều từ.

📙 Nâng cao

  1. Autocomplete: in tối đa 10 từ gợi ý.
  2. Trie có xóa từ.
  3. Đếm số cặp chuỗi có prefix chung dài nhất.

🐉 HSG

  1. Bitwise Trie tìm XOR lớn nhất.
  2. Persistent Trie định hướng nâng cao.
  3. Trie kết hợp DP trên chuỗi.

7. Quiz Trie

Câu 1. Biến end dùng để làm gì?
Câu 2. Nếu có “cat”, “car”, thì startsWith("ca") trả về gì?
⬅️ Quay lại chương 11