Bài 4: Trie — Cấu Trúc Từ Điển Cho Autocomplete

Ở Bài 3 chúng ta đã đua các giải thuật sắp xếp mảng số. Bài này chuyển sang một bài toán rất khác: tìm kiếm chuỗi theo tiền tố — nền tảng của autocomplete trên thanh tìm kiếm, gợi ý gõ chữ trên điện thoại (T9), và bộ kiểm tra chính tả.

1. Vì sao Hash Table không đủ cho tìm kiếm tiền tố?

Hash Table cho tra cứu chính xác cực nhanh — $O(1)$ trung bình để kiểm tra một từ có tồn tại hay không. Nhưng thử hỏi: "liệt kê tất cả các từ trong từ điển bắt đầu bằng 'ca'"? Hash Table không có khái niệm "gần nhau" giữa các khóa đã băm — bạn buộc phải quét toàn bộ $n$ từ trong từ điển và kiểm tra từng từ một, tốn $O(n)$ dù từ điển đã được băm sẵn.

Trie (đọc là "try", từ chữ retrieval — tra cứu) giải quyết đúng vấn đề này: các từ có chung tiền tố sẽ chia sẻ chung một nhánh cây, nên tìm tất cả từ theo tiền tố chỉ cần đi tới đúng node tiền tố rồi duyệt nhánh con của nó — không cần quét cả từ điển.

2. Cấu trúc Trie: Node chia sẻ tiền tố chung

Mỗi node Trie đại diện cho một ký tự, có một tập con trỏ tới các node ký tự tiếp theo, và một cờ đánh dấu "đây có phải điểm kết thúc một từ hoàn chỉnh hay không":

class TrieNode {
  constructor() {
    this.children = new Map(); // ký tự -> TrieNode con
    this.isEndOfWord = false;  // true nếu có từ kết thúc tại đây
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
}

3. Chèn & Tìm kiếm trong Trie

Chèn một từ dài $L$ ký tự chỉ cần đi qua tối đa $L$ node, tạo mới node nào chưa tồn tại. Độ phức tạp luôn là $O(L)$ — không phụ thuộc vào việc từ điển có bao nhiêu từ khác:

Trie.prototype.insert = function (word) {
  let node = this.root;
  for (const ch of word) {
    if (!node.children.has(ch)) {
      node.children.set(ch, new TrieNode());
    }
    node = node.children.get(ch);
  }
  node.isEndOfWord = true; // đánh dấu điểm kết thúc từ
};

Trie.prototype.search = function (word) {
  let node = this.root;
  for (const ch of word) {
    if (!node.children.has(ch)) return false;
    node = node.children.get(ch);
  }
  return node.isEndOfWord; // PHẢI kiểm tra cờ này, không chỉ node tồn tại!
};

Trie.prototype.startsWith = function (prefix) {
  let node = this.root;
  for (const ch of prefix) {
    if (!node.children.has(ch)) return false;
    node = node.children.get(ch);
  }
  return true; // chỉ cần đường đi tồn tại, không cần isEndOfWord
};

4. Autocomplete: Duyệt DFS từ node tiền tố

Để gợi ý autocomplete, ta chỉ cần đi tới node cuối của tiền tố người dùng gõ, rồi duyệt DFS toàn bộ cây con bên dưới, thu thập mọi node có isEndOfWord = true:

Trie.prototype.autocomplete = function (prefix) {
  let node = this.root;
  for (const ch of prefix) {
    if (!node.children.has(ch)) return []; // không có từ nào khớp tiền tố
    node = node.children.get(ch);
  }

  const results = [];
  function dfs(node, path) {
    if (node.isEndOfWord) results.push(prefix.slice(0, -1) === '' ? path : prefix + path.slice(prefix.length));
    for (const [ch, child] of node.children) {
      dfs(child, path + ch);
    }
  }
  dfs(node, prefix);
  return results;
};

Độ phức tạp autocomplete là $O(L + k)$ với $L$ là độ dài tiền tố và $k$ là tổng số ký tự trong tất cả kết quả trả về — nhanh hơn rất nhiều so với quét toàn bộ $n$ từ trong từ điển khi $n$ lớn.

5. So sánh Trie với Hash Table và BST

Sân chơi tương tác: Trie Autocomplete Visualizer

Thêm từ vào từ điển, rồi gõ vào ô "Autocomplete" để xem đường đi trong cây được tô sáng và danh sách gợi ý cập nhật theo từng ký tự bạn gõ.