Tổng quan
Trie, hay cây tiền tố (prefix tree), là cấu trúc dữ liệu dạng cây được khóa theo các ký tự của chuỗi. Các từ có chung tiền tố sẽ chia sẻ cùng một đường đi từ gốc, nên cấu trúc lưu cả một từ điển một cách gọn gàng.
Mỗi cạnh biểu diễn một ký tự và mỗi nút đánh dấu liệu có một từ kết thúc tại đó. Vì việc tra cứu đi từng ký tự một, chi phí phụ thuộc vào độ dài từ, không phụ thuộc số từ mà trie chứa.
Trie (Cây tiền tố) hoạt động thế nào?
- Bắt đầu từ gốc và đi theo cạnh con mang nhãn là ký tự đầu tiên của từ.
- Với mỗi ký tự còn lại, đi xuống nút con khớp, tạo mới nếu chưa tồn tại.
- Đánh dấu nút cuối là điểm kết thúc từ để tìm kiếm phân biệt được một từ đã lưu với một tiền tố đơn thuần.
- Tìm kiếm và truy vấn tiền tố đi cùng một đường; thiếu một cạnh nghĩa là từ hoặc tiền tố không có.
Khi nào nên dùng?
- Gợi ý tự động hoàn thành (autocomplete), liệt kê mọi từ nằm dưới một tiền tố đã gõ.
- Bộ kiểm tra chính tả và từ điển cần tra cứu tiền tố và thành viên nhanh.
- Bảng định tuyến IP và các trò chơi chữ, khi tiền tố chung tiết kiệm bộ nhớ và thời gian.
Phân tích độ phức tạp
Chèn và tìm kiếm đều chạy trong O(L), với L là độ dài từ, không phụ thuộc số từ đã lưu. Bộ nhớ có thể lớn — tới O(tổng số ký tự × kích thước bảng chữ cái) — nhưng tiền tố chung giảm đáng kể trong thực tế.
Câu hỏi thường gặp
Trie tốt hơn tập băm cho autocomplete ở điểm nào?
Tập băm kiểm tra được thành viên chính xác nhưng không liệt kê được mọi từ có một tiền tố cho trước; trie đi thẳng tới nút tiền tố và liệt kê mọi thứ bên dưới.
Tra cứu trên trie có chậm đi khi thêm nhiều từ không?
Không. Chi phí tra cứu là O(L) chỉ theo độ dài truy vấn, nên một trie triệu từ tìm kiếm không chậm hơn một trie trăm từ.