Trie (Prefix Tree or Digital Tree)
Một cấu trúc dữ liệu dạng cây được thiết kế để lưu trữ và tìm kiếm các chuỗi ký tự (như từ điển hoặc danh sách)
Đặc điểm nổi bật
Cấu trúc
Mỗi nút trong Trie đại diện cho một ký tự.
Đường đi từ gốc đến một nút lá biểu diễn một chuỗi ký tự.
Mỗi nút có thể chứa nhiều nhánh, mỗi nhánh đại diện cho một ký tự khác nhau.
Lưu trữ
Không lưu trữ toàn bộ chuỗi tại một nút, mà mỗi ký tự của chuỗi sẽ được lưu ở một nút khác nhau.
Hiệu quả
Tìm kiếm một chuỗi ký tự dài m trong Trie mất O(m), không phụ thuộc vào số lượng từ.
Thành phần
Nút gốc (Root): Là điểm bắt đầu, không lưu trữ ký tự nào.
Nút con (Children): Là các nút đại diện cho ký tự con.
Cờ kết thúc (End-of-word flag): Đánh dấu nút kết thúc của một chuỗi ký tự.
Các thao tác với Trie
Thêm từ vào Trie
Bắt đầu từ nút gốc.
Duyệt qua từng ký tự của chuỗi:
Nếu ký tự không tồn tại ở nút hiện tại, tạo một nút mới.
Di chuyển đến nút con tương ứng với ký tự.
Đánh dấu nút cuối cùng là kết thúc của từ.
Tìm kiếm từ trong Trie
Bắt đầu từ nút gốc.
Duyệt qua từng ký tự của chuỗi:
Nếu ký tự không tồn tại trong nút con, trả về "không tìm thấy".
Nếu tồn tại, di chuyển đến nút con.
Kiểm tra cờ kết thúc tại nút cuối:
Nếu cờ kết thúc là True, từ tồn tại.
Nếu không, từ không tồn tại.
Xóa từ khỏi Trie
Duyệt qua cây theo các ký tự của chuỗi.
Nếu nút cuối cùng không còn từ nào khác phụ thuộc, xóa nút đó.
Lặp lại ngược từ nút lá về gốc, kiểm tra và xóa các nút không cần thiết.
Tìm kiếm theo tiền tố
Duyệt qua các ký tự của tiền tố trong Trie.
Nếu tìm thấy, trả về tất cả các từ bắt đầu bằng tiền tố đó từ vị trí hiện tại.
Ứng dụng
Từ điển và tìm kiếm theo tiền tố:
Gợi ý từ trong ứng dụng gõ văn bản (autocomplete).
Kiểm tra chính tả.
Xử lý văn bản:
Tìm kiếm và lưu trữ các mẫu trong dữ liệu lớn.
Hệ thống phân tán:
Nén và lưu trữ dữ liệu hiệu quả.
Ưu và nhược điểm
Ưu điểm
Tìm kiếm nhanh, đặc biệt với các bài toán liên quan đến tiền tố.
Có thể lưu trữ nhiều từ chung ký tự mà không lặp lại dữ liệu.
Nhược điểm
Tốn bộ nhớ khi số lượng ký tự hoặc từ lớn.
Phức tạp hơn các cấu trúc dữ liệu khác như Hash Table cho các bài toán không liên quan đến tiền tố.