Có một Trie trong Java không?

Question

thể trùng lặp:
Where do I find a standard Trie based map implementation in Java?

Tôi muốn sử dụng Trie trong Java, có một thực hiện tôi có thể sử dụng không? (Tôi đã cố gắng tìm một nhưng tôi không tìm thấy nó).

Answer 1

Không có cấu trúc dữ liệu trie trong các thư viện Java lõi. Điều này có thể là do cố gắng thường được thiết kế để lưu trữ chuỗi ký tự, trong khi cấu trúc dữ liệu Java tổng quát hơn, thường giữ bất kỳ Object (xác định bình đẳng và hoạt động băm), mặc dù đôi khi chúng được giới hạn ở các đối tượng Comparable (xác định đơn đặt hàng)). Không có trừu tượng chung cho "một chuỗi các ký hiệu", mặc dù CharSequence phù hợp với các chuỗi ký tự và tôi cho rằng bạn có thể làm điều gì đó với Iterable cho các loại biểu tượng khác.

Đây là một điểm cần xem xét: khi cố gắng triển khai một trie thông thường trong Java, bạn nhanh chóng đối mặt với thực tế là Java hỗ trợ Unicode. Để có bất kỳ loại hiệu quả không gian nào, bạn phải hạn chế các chuỗi trong trie của bạn thành một số tập con biểu tượng, hoặc từ bỏ cách tiếp cận thông thường để lưu trữ các nút con trong một mảng được lập chỉ mục bằng ký hiệu. Đây có thể là một lý do khác khiến các cố gắng không được coi là đủ mục đích chung để đưa vào thư viện cốt lõi và một cái gì đó cần lưu ý nếu bạn triển khai hoặc sử dụng thư viện của bên thứ ba.