I. Giới Thiệu Về Trie Tree
Trie (hay Cây Tiền Tố) là một cấu trúc dữ liệu dưới dạng cây, rất hữu ích trong việc quản lý tập hợp các xâu ký tự và có khả năng mở rộng cho các bài toán liên quan đến quản lý tập số nguyên (xem phần 2)
Cấu trúc của Trie rất đơn giản: Nó là một cây sử dụng các ký tự của xâu trên từng cạnh, cho phép lưu trữ các xâu có tiền tố giống nhau một cách hiệu quả. Mỗi đường đi từ gốc tới lá trong Trie biểu thị một xâu, chẳng hạn như trong minh họa, đường đi từ đỉnh gốc đến đỉnh lá biểu diễn xâu caaa và xâu cba.
II. Cài Đặt Trie và Ứng Dụng
1. Phương Pháp
Trie hỗ trợ thực hiện 3 thao tác chính với độ phức tạp tuyến tính:
- Thêm xâu vào tập hợp.
- Xóa một xâu khỏi tập hợp.
- Kiểm tra xem một xâu có nằm trong tập hợp hay không.
Ngoài mảng child, chúng ta cần giữ thêm hai biến exist và cnt:
exist: Số xâu mà đỉnh đó biểu diễn.cnt: Số xâu có tiền tố là xâu được thể hiện bởi đỉnh đó.
Thao Tác Thêm Xâu
Khi thêm xâu, bắt đầu từ đỉnh gốc, duyệt qua các ký tự và đi xuống cạnh tương ứng. Nếu cạnh chưa tồn tại, tạo đỉnh mới và cập nhật mảng child.
Thao Tác Xóa Xâu
Kiểm tra xem xâu cần xóa có tồn tại trong Trie không. Nếu có, giảm giá trị exist ở đỉnh tương ứng, nếu không thì đệ quy từ dưới lên để xóa các đỉnh dư thừa.
Thao Tác Tìm Xâu
Tương tự thao tác thêm, kiểm tra xem cạnh tương ứng với ký tự hiện tại có tồn tại không, nếu không thì dừng.
2. Kỹ Thuật Cài Đặt
Có hai cách để triển khai Trie: bằng mảng hoặc bằng con trỏ. Việc sử dụng con trỏ giúp tránh tính toán bộ nhớ lãng phí và dễ dàng quản lý.
Cài Đặt Bằng Mảng
cpp
const int max_nodes = ...;
struct Trie
{
struct Node
{
int child[26];
int exist, cnt;
} nodes[max_nodes];
...
}Cài Đặt Bằng Con Trỏ
cpp
struct Trie
{
struct Node
{
Node* child[26];
int exist, cnt;
};
...
}III. Các Ứng Dụng Cơ Bản
1. Sắp Xếp Danh Sách Xâu
Sử dụng Trie để sắp xếp danh sách xâu theo thứ tự từ điển trong thời gian tuyến tính.
2. Truy Vấn Tiền Tố Chung Dài Nhất
Trie hỗ trợ trả lời truy vấn tìm độ dài tiền tố chung dài nhất giữa hai xâu.
3. Tìm Xâu Có Thứ Tự Từ Điển Thứ K
Có thể tìm xâu có thứ tự từ điển thứ k bằng cách duyệt từ gốc của Trie.
IV. Một Số Bài Tập Khác
1. FSTR
Yêu cầu khảo sát hiệu năng tìm kiếm từ trong danh sách.
2. Perfect Matching
Tìm hoán vị giữa hai tập xâu sao cho tổng độ dài tiền tố chung dài nhất là lớn nhất.
V. Tài Liệu Tham Khảo
Để tiếp tục xem phần thứ 2 của bài viết, hãy nhấn vào đây.
source: viblo
