Mô phỏng thuật toán Cây tiền tố · tra cứu

Trie · Search · Nhóm: Cấu trúc dữ liệu

Tra cứu một từ trong cây tiền tố bằng cách đi theo từng ký tự từ gốc; nếu đi hết từ và dừng đúng ở nút hết-từ thì từ đó có trong cây.

Ý tưởng

Đặt con trỏ tại nút gốc, xét lần lượt từng ký tự của từ cần tìm.

Nếu tại nút hiện tại không có cạnh cho ký tự đó thì kết luận không tìm thấy.

Đi hết mọi ký tự, kiểm tra nút cuối có phải nút hết-từ hay không để trả lời có hay không.

Vì sao đúng

Chỉ cần đi theo đúng một đường ứng với các ký tự nên chi phí tra cứu tỉ lệ với độ dài từ, không phụ thuộc số từ đã lưu trong cây.

Mã Python

def search(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return node.is_end

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.