Trie hay còn gọi là Prefix tree, là một cấu trúc dữ liệu dạng tree với root là một chuỗi rỗng dùng để lưu tập hợp của các chuỗi, nếu 2 chuỗi có cùng prefix thì nó sẽ có cùng các node cha.

Trong trường hợp bạn có rất nhiều chuỗi thì Trie là một cấu trúc rất dễ cho việc kiểm tra xem chuỗi đó có tồn tại trong data của bạn hay không. Trie cũng được dùng nhiều cho việc tìm kiếm prefix của chuỗi. Khi sử dụng Trie, độ phức tạp khi tìm kiếm được tối ưu đến mức bằng với độ dài của key ta muốn tìm kiếm.

Vậy cấu trúc của Trie như thế nào? Và ứng dụng của nó ra sao?

Cấu trúc:

TrieNode {
    map <Chacracter, ChildNode> children;
    boolean endOfWord;
}

Mỗi Trie node sẽ chứa 2 components chính:

  • map: chứa key là character và value là child node, dùng để khởi tạo mối quan hệ giữa node cha và node con.
  • boolean endOfWord dùng để kiểm tra child node hiện tại có phải là character cuối cùng của key hay không.

Ứng dụng:

Trie thường được sử dụng khi bạn có một tập hợp lớn các chuỗi ít có sự thay đổi và bạn muốn tìm kiếm nhanh trong các chuỗi đó theo prefix hoặc nguyên chuỗi.

Khi so sánh với Hash thì Trie có thể có tốc độ tìm kiếm không bằng Hash nhưng bù lại nó sẽ yêu cầu ít bộ nhớ hơn cho việc lưu trữ.

Để hiểu thêm chi tiết về Trie các bạn có thể tham khảo các link dưới đây:

http://r.grokking.org/videos-trie-1
http://r.grokking.org/videos-trie-2

Author: Lợi Nguyễn