Menu
CoddyTech
Bắt đầu học

Trie (cây tiền tố)

Cập nhật lần cuối

Trie (đọc là "try"), hay cây tiền tố (prefix tree), lưu một tập chuỗi theo các ký tự của chúng: mỗi cạnh được gắn nhãn bằng một ký tự, và một đường đi từ gốc ghép thành một tiền tố. Các từ có chung tiền tố dùng chung các nút, nên "car", "card" và "care" đều tái sử dụng đường đi c-a-r. Nhấn Phát ở trên để xem các từ được chèn vào từng ký tự một, chỉ rẽ nhánh ở chỗ chúng khác nhau.

Vì mỗi lần tra cứu đi qua một nút cho mỗi ký tự, tìm một từ có độ dài m tốn thời gian O(m) bất kể trie chứa bao nhiêu từ. Điều đó khiến trie lý tưởng cho tự động hoàn thành (autocomplete), kiểm tra chính tả và tìm kiếm theo tiền tố.

Độ phức tạp thời gian và không gian

Thao tácĐộ phức tạpGhi chú
ChènO(m)m = độ dài của từ
Tìm kiếmO(m)Mỗi ký tự một bước
Truy vấn tiền tốO(m)Đi đến nút của tiền tố
Không gianO(total chars)Tiền tố chung chỉ lưu một lần

Từng bước (chèn)

BướcĐiều gì xảy ra
1Bắt đầu ở nút gốc.
2Với mỗi ký tự trong từ, tìm cạnh con khớp với ký tự đó.
3Nếu có, đi theo cạnh đó (tái sử dụng tiền tố chung).
4Nếu không, tạo một nút con mới cho ký tự đó.
5Sau ký tự cuối cùng, đánh dấu nút đó là kết thúc từ.

Ví dụ minh họa

Chèn ["car", "card", "care"] vào một trie rỗng:

BướcCấu trúcThao tác
Chèn carroot → c → a → r✓Chưa có nút con nào khớp, nên tạo c, a, r và đánh dấu r là kết thúc từ.
Chèn cardroot → c → a → r✓ → d✓Tái sử dụng đường đi c-a-r có sẵn, rồi tạo một nút con mới d và đánh dấu nó là kết thúc từ.
Chèn careroot → c → a → r✓ → {d✓, e✓}Tái sử dụng c-a-r, rẽ nhánh từ r với một nút con mới e, và đánh dấu e là kết thúc từ.
Tìm careroot → c → a → r → e✓Đi qua c, a, r, e; nút cuối được đánh dấu kết thúc từ, nên care có trong trie.
Tìm caroot → c → aĐường đi tồn tại nhưng a không được đánh dấu kết thúc từ, nên ca là một tiền tố chứ không phải từ đã lưu.

Khi nào nên dùng trie

Nên dùng khiTránh dùng khi
Bạn cần truy vấn tiền tố hoặc tự động hoàn thành trên một tập chuỗi.Bạn chỉ cần tra cứu theo nguyên khóa: bảng băm nhanh và nhẹ hơn.
Nhiều từ được lưu có chung tiền tố, nên các nút được tái sử dụng.Các khóa dài và hiếm khi trùng nhau, gây lãng phí một nút cho mỗi ký tự.
Bạn muốn nhận các khóa theo thứ tự đã sắp xếp khi duyệt.Bộ nhớ hạn hẹp: con trỏ đến các nút con ở mỗi nút làm tăng đáng kể chi phí bộ nhớ.
Chi phí tra cứu phải phụ thuộc vào độ dài khóa, không phải kích thước dữ liệu.Bảng chữ cái rất lớn (ví dụ toàn bộ Unicode) và các nút con được lưu dày đặc.

Code Trie (Prefix Tree)

Một cách cài đặt Trie (Prefix Tree) gọn gàng, chạy được ngay bằng Python, JavaScript, Java, C++, C. Chọn một ngôn ngữ, sao chép code hoặc mở sẵn trong Coddy Playground.

Code Trie (Prefix Tree) bằng Python

Python
1class TrieNode:2    def __init__(self):3        self.children = {}4        self.is_word = False5
6
7class Trie:8    def __init__(self):9        self.root = TrieNode()10
11    def insert(self, word):12        node = self.root13        for ch in word:14            node = node.children.setdefault(ch, TrieNode())15        node.is_word = True16
17    def search(self, word):18        node = self._walk(word)19        return node is not None and node.is_word20
21    def starts_with(self, prefix):22        return self._walk(prefix) is not None23
24    def _walk(self, s):25        node = self.root26        for ch in s:27            if ch not in node.children:28                return None29            node = node.children[ch]30        return node31
32
33trie = Trie()34for word in ["car", "card", "care", "dog"]:35    trie.insert(word)36
37print("search(card):     ", trie.search("card"))38print("search(ca):       ", trie.search("ca"))39print("starts_with(ca):  ", trie.starts_with("ca"))40print("starts_with(do):  ", trie.starts_with("do"))41print("starts_with(cat): ", trie.starts_with("cat"))
Chạy code này trong Playground Python

Câu hỏi thường gặp về trie

Trie dùng để làm gì?

Trie là nền tảng của các tính năng dựa trên tiền tố: tự động hoàn thành và gợi ý tìm kiếm, kiểm tra chính tả, bảng định tuyến IP và tra từ điển. Ở bất cứ đâu bạn cần truy vấn nhanh kiểu "có từ nào đã lưu bắt đầu bằng tiền tố này không?", trie đều phát huy thế mạnh.

Độ phức tạp thời gian của trie là bao nhiêu?
Chèn, tìm kiếm và truy vấn tiền tố đều chạy trong thời gian O(m), trong đó m là độ dài của từ hoặc tiền tố, không phụ thuộc vào số từ đã lưu. Cái giá phải trả là bộ nhớ: trie có thể tốn nhiều không gian, dù các tiền tố chung chỉ được lưu một lần.
Trie khác bảng băm như thế nào?
Bảng băm cho phép tra cứu nguyên khóa trung bình O(1) nhưng không trả lời được truy vấn tiền tố. Trie chậm hơn một chút mỗi lần tra cứu nhưng hỗ trợ tự nhiên tìm kiếm theo tiền tố, duyệt theo thứ tự và tự động hoàn thành, đó là lý do nó được ưu tiên cho những trường hợp này.
Khi nào nên dùng trie thay vì cây tìm kiếm nhị phân?
Hãy dùng trie khi khóa là chuỗi và bạn cần tra cứu theo tiền tố: mỗi thao tác chạy trong O(m) theo độ dài khóa, trong khi một BST cân bằng tốn O(m log n) vì mỗi phép so sánh phải quét chuỗi và có log n phép so sánh như vậy. BST là lựa chọn tốt hơn khi khóa không phải dạng chuỗi hoặc khi chi phí bộ nhớ quan trọng hơn tốc độ tìm tiền tố.
Làm sao xử lý điểm kết thúc của một từ trong trie?
Mỗi nút mang một cờ kết thúc từ, chỉ được bật khi một từ đầy đủ đã chèn kết thúc tại đó. Nếu không có cờ này, bạn không phân biệt được từ đã lưu với một tiền tố đơn thuần: ví dụ sau khi chèn card, nút của car tồn tại nhưng chỉ được coi là một từ nếu car cũng đã được chèn.
Trie có luôn tiết kiệm bộ nhớ nhờ dùng chung tiền tố không?

Không phải lúc nào cũng vậy. Dùng chung chỉ có ích khi nhiều khóa trùng nhau; với các khóa dài và khác biệt, trie có thể tốn bộ nhớ hơn nhiều so với hash set, vì mỗi ký tự trở thành một nút riêng kèm các con trỏ đến nút con. Nếu không gian là vấn đề, radix tree nén sẽ gộp các chuỗi nút chỉ có một con để giảm chi phí đó.

Tài nguyên liên quan

Thêm mô phỏng trực quan

Hình minh họa các ngôn ngữ lập trình của Coddy

Thành thạo thuật toán cùng Coddy

Bắt đầu