Trie Tree (phần 2) - Trie Nhị Phân

Đây là bài viết số 222 trong series về cấu trúc dữ liệu Trie Tree. Để hiểu bài viết này, hãy tham khảo bài viết trước đó về Trie Tree Cơ Bản tại đây: Trie Tree phần 1.

I. Giới thiệu chung

Trie là một cấu trúc dữ liệu dạng cây rất hiệu quả trong việc quản lý danh sách các chuỗi ký tự. Tuy nhiên, ít ai biết rằng Trie còn có một ứng dụng quan trọng khác, đó là quản lý tập hợp các số nguyên. Bằng cách diễn đạt mỗi số nguyên dưới dạng chuỗi nhị phân, ta có thể áp dụng Trie để xử lý hiệu quả các bài toán liên quan đến số nguyên.

Ví dụ: Trie nhị phân sẽ giúp quản lý tập hợp các số nguyên như {0, 1, 2, 4, 6}.

Đặc điểm của Trie Nhị Phân:

• Mỗi số được thêm vào Trie sẽ được chuyển đổi sang dạng nhị phân. Độ dài của các chuỗi nhị phân này thường được quy định là log(max(ai)), với ai là các số trong tập hợp. Để đảm bảo tất cả các chuỗi có độ dài bằng nhau, có thể thêm các bit 0 vào đầu.
• Một số nguyên được phản ánh qua các bit trên đường đi từ nút gốc đến nút lá của Trie.
• Các bit được thêm vào Trie theo chiều từ trái sang phải.

II. Cài đặt và Ứng dụng

1. Cài đặt

Ứng dụng của Trie trên các chuỗi cũng tương tự như trên Trie nhị phân. Một số thao tác cơ bản bao gồm:

• Thêm một nút vào Trie.
• Thêm một số vào Trie.
• Xóa một số khỏi Trie.
• Kiểm tra một số có nằm trong Trie hay không.

Cài đặt bằng mảng:

const int MAX_NODES = ...;
const int LOG = ...; // Giá trị lớn nhất của log(a[i]).

struct Trie { ... }

Cài đặt bằng con trỏ:

const int LOG = ...;

struct Trie { ... }

2. Xử lý truy vấn tìm XOR lớn nhất với giá trị được cho

Trie nhị phân là một công cụ mạnh mẽ cho các bài toán xử lý bit.

Đề bài: Cho n số nguyên không âm và m truy vấn, mỗi truy vấn yêu cầu tìm giá trị:

max⁡(ai⊕x) với x là số nguyên không âm, ⊕ là toán tử XOR.

Yêu cầu: Xử lý tất cả các truy vấn?

III. Bài tập áp dụng

1. GCD, XOR & SUM

Đề bài: Có một mảng rỗng, và thực hiện hai loại truy vấn. Nhiệm vụ là tìm giá trị lớn nhất có thể của một số v trong mảng thỏa mãn các điều kiện cho trước.

IV. Tài liệu tham khảo

• VNOI
• Lê Duy Thức
  source: viblo