Trie: nút, cạnh, search, insert, remove, prefix

Giới thiệu

Bài này học Trie lưu từ điển bằng cách chia sẻ tiền tố. Cây này giúp tra từ và gợi ý rất nhanh.

Kiến thức cần nhớ

Trie là gì

• Trie là cây mà mỗi cạnh mang một ký tự.
• Mỗi nút đánh dấu có phải kết thúc từ không.
• Các từ chung tiền tố thì đi chung đoạn đường đầu.
• Ví dụ đời thường: ant và anthem chung đường a-n-t.

Tìm kiếm và chèn

• Tìm: đi từ gốc theo từng ký tự của khóa.
• Hết chuỗi mà nút có đánh dấu thì báo có từ.
• Chèn: đi theo đường cũ, thiếu tới đâu tạo nhánh mới.
• Ví dụ đời thường: tra từ điển bằng cách lật từng chữ.

# Tìm trong trie: đi theo từng ký tự
def tim(goc, tu):
    nut = goc  # bắt đầu từ gốc
    for ch in tu:  # xét từng ký tự
        if ch not in nut.con:  # không có cạnh
            return False  # từ không tồn tại
        nut = nut.con[ch]  # bước sang nút con
    return nut.het_tu  # phải là kết thúc từ

Xóa và gợi ý tiền tố

• Xóa: bỏ đánh dấu, rồi tỉa nhánh thừa từ lá lên.
• Dừng tỉa khi gặp nút còn dùng chung từ khác.
• Gợi ý: tới nút tiền tố rồi liệt kê cả cây con.
• Ví dụ đời thường: gõ "ant" hiện ra anthem, antler.

Ví dụ

• Input: trie có anthem, tra ant -> Output: False.
• Câu này phân biệt tiền tố với từ hoàn chỉnh.
• Input: xóa ant khỏi trie có ant và anthem -> Output: anthem còn nguyên.
• Câu này cho thấy nhánh chung không bị cắt nhầm.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-035/. Chỉ xét chữ thường a-z cho Bài 1-2.

Bài 1: Trie cơ bản

struct TrieNode { std::array<TrieNode*, 26> child{}; bool isEnd = false; int passCount = 0; };
class Trie {
 public:
  void insert(const std::string &w);
  bool search(const std::string &w) const;       // đúng từ
  bool startsWith(const std::string &p) const;   // có từ nào bắt đầu bằng p
  bool remove(const std::string &w);             // tỉa nhánh thừa, trả false nếu không có
  int  countPrefix(const std::string &p) const;  // số từ có tiền tố p, O(|p|) nhờ passCount
  size_t nodeCount() const;
  ~Trie();
};

insert ant, anthem, antique, bee
search("ant") -> true; search("anth") -> false; startsWith("anth") -> true
countPrefix("ant") -> 3
remove("ant") -> anthem, antique vẫn tìm thấy; search("ant") = false
remove("bee") -> nodeCount giảm đúng 3 nút (b, e, e)
remove("cat") -> false

Bài 2: Gợi ý theo tiền tố

std::vector<std::string> suggest(const std::string &prefix, int limit): trả tối đa limit từ theo thứ tự alphabet.

Nạp file từ điển tiếng Anh (khoảng 100.000 từ, ví dụ /usr/share/dict/words đã lọc chữ thường). In 10 gợi ý cho "pre", "xyl", "qqq".

So thời gian suggest với cách quét toàn bộ std::vector<std::string> đã sắp xếp (dùng lower_bound).

Bài 3: Trie cho Unicode và bộ nhớ (nâng cao)

1. Đổi child sang std::unordered_map<char32_t, TrieNode*> để hỗ trợ tiếng Việt có dấu. Chuyển UTF-8 sang char32_t trước khi chèn.
2. Nạp 10.000 từ tiếng Việt. In số nút và ước lượng bộ nhớ của 2 cách cài (mảng 26 và map).
3. Viết longestCommonPrefix() của mọi từ trong trie.

["flower", "flow", "flight"] -> "fl"
["đường", "đương", "đi"]     -> "đ"

✅ Tiêu chí hoàn thành

• Test mẫu pass, remove không làm hỏng từ dùng chung tiền tố.
• Bảng thời gian Bài 2 có số thật.
• Bài 3 xử lý đúng từ có dấu.
• Sanitizer sạch sau khi xóa hết từ.

❓ Câu hỏi ôn tập

• Trie chia sẻ tiền tố chung thế nào?
• Tìm kiếm đi theo ký tự ra sao?
• Chèn từ mới tạo nhánh lúc nào?
• Xóa từ mà giữ từ chung nhánh thế nào?

🌕 Bạn đã hoàn thành ngày 35. Làm hết bài tập phía trên rồi sang ngày tiếp theo.