Chuyển tới nội dung chính

Trie (cây tiền tố)

Bạn sẽ học được gì

Trie (cây tiền tố) lưu một tập từ theo cây ký tự — các từ cùng tiền tố dùng chung đường đi. Nó cho tìm từ và gợi ý theo tiền tố (autocomplete) cực nhanh, không phụ thuộc số lượng từ.

1. Trực quan: cây chia theo từng ký tự​

Mỗi cạnh là một ký tự; mỗi đường đi từ gốc tạo thành một tiền tố. Từ kết thúc được đánh dấu (★). Các từ cùng tiền tố chia sẻ phần đầu.

        (gốc)
          │ a
        ┌─┴─┐
        │ a │
        └─┬─┘
          │ n
        ┌─┴─┐
        │ an★│        "an" là một từ
        └─┬─┘
          │ d
        ┌─┴─┐
        │and★│        "and" cũng là từ; dùng chung "an"
        └───┘

"an" và "and" dùng chung nhánh "a → n" → tiết kiệm và cho phép tìm theo tiền tố.

🎬 Trực quan hóa tương tác — VisuAlgo
Trực quan hóa thêm từ và tìm kiếm theo tiền tố. Quan sát cây ký tự lớn dần và các nhánh dùng chung.
Nguồn: visualgo.net — Steven Halim, NUS. Dùng cho lớp học; ảnh chụp/video cần ghi nguồn URL.

2. Cài đặt: mỗi nút là một dict con​

Đang tải trình chạy code…

3. Chạy debug: tìm "and" trong trie​

Tìm = đi theo từng ký tự; tới cuối kiểm tra cờ kết thúc từ. Bước qua tìm "and":

🐞 Tìm "and" trong trie {an, and, ant}Bước 1/5
1nut = goc
2for c in "and":
3  if c not in nut.con:
4      return False
5  nut = nut.con[c]
6return nut.la_tu
Biến tại bước này
nutgốc
👉 Bắt đầu từ gốc.

4. Vì sao trie nhanh? O(L), không phụ thuộc N​

Tìm/thêm một từ dài L chỉ tốn O(L) — đi L bước theo cây — bất kể trie chứa bao nhiêu từ (N). So với duyệt danh sách N từ (O(N·L)) thì trie thắng lớn khi N lớn.

Thao tácTrieDuyệt danh sách
Tìm một từO(L)O(N·L)
Gợi ý theo tiền tốO(L + số kết quả)O(N·L)

5. Dùng trie để làm gì?​

  • Autocomplete / gợi ý gõ (gõ "an" → gợi "an, and, ant").
  • Kiểm tra từ điển / chính tả.
  • Tìm theo tiền tố (danh bạ, tìm kiếm).
  • IP routing, T9 trên điện thoại cũ.

Đánh đổi: trie tốn bộ nhớ hơn (nhiều nút nhỏ), nhưng tra cứu theo tiền tố thì vô địch.

6. Mẫu nhận diện​

  • "Gợi ý theo tiền tố", "autocomplete", "các từ bắt đầu bằng..." → trie.
  • Tập từ lớn + tra cứu/tiền tố nhiều → trie thắng danh sách/set thường.
  • Chỉ cần "từ này có trong tập không" (không cần tiền tố) → set đơn giản là đủ.

7. 🎮 Trò chơi: Hiểu trie​

🎮 Hiểu trieCâu 1/4· Điểm 0· 🔥 0

Trie: cây ký tự, từ cùng tiền tố dùng chung đường. Tìm = O(độ dài từ).

Trie phù hợp nhất cho bài nào?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Trie lưu dữ liệu theo?
2. Ưu thế lớn nhất của trie?
3. Cờ la_tu (kết thúc từ) dùng để?
📚 Đọc thêm & Luyện tập
🎬 Video
🏋️ Luyện tập

9. Hoàn thành​

…

☑️ Tiếp theo: 2.5.7 — Segment tree & Fenwick (nâng cao).