Trie là gì?

Trie (phát âm là “try”, viết tắt của retrieval, nghĩa là truy xuất) là một cấu trúc dữ liệu dạng cây, được xây dựng để lưu trữ và tìm kiếm chuỗi theo từng ký tự. Mỗi cạnh trong cây được gắn nhãn bằng một ký tự, và mỗi đường đi từ nút gốc đến một nút được đánh dấu sẽ tạo thành một từ đã lưu.

Cấu trúc này giúp truy vấn tiền tố cực kỳ nhanh. Kiểm tra xem trie có chứa từ nào bắt đầu bằng "car" hay không chỉ cần tra cứu ba ký tự từ nút gốc, bất kể có hàng nghìn từ được lưu trữ. Trie là nền tảng cho các tính năng như tự động hoàn thành, kiểm tra chính tả và bảng định tuyến IP.

Mỗi nút trong trie lưu hai trạng thái:

• children: một ánh xạ từ ký tự đến TrieNode tiếp theo.
• isEndOfWord: một cờ có giá trị true khi đường đi từ nút gốc đến nút này tạo thành một từ hoàn chỉnh đã được thêm vào.

Năm thao tác chính trên trie là:

1. Thêm: Thêm một từ, tạo các nút còn thiếu trên đường đi.
2. Tìm kiếm: Kiểm tra xem một từ hoàn chỉnh có được lưu hay không.
3. Bắt đầu bằng: Kiểm tra xem có từ nào đã lưu bắt đầu bằng tiền tố đã cho hay không.
4. Xóa: Xóa một từ và loại bỏ các nhánh không còn cần thiết.
5. Đếm từ: Đếm số từ riêng biệt được lưu trữ.

Hãy xây dựng một lớp Trie!