Wiki › Cấu trúc dữ liệu › Cây › Trie (Cây tiền tố)

Trie (Cây tiền tố)

huunguyen Updated Tháng sáu 2, 2026

Trie (cây tiền tố, prefix tree) là cấu trúc dữ liệu dạng cây dùng để lưu một tập hợp các xâu, trong đó mỗi cạnh ứng với một ký tự và mỗi đường đi từ gốc xuống một node biểu diễn một tiền tố. Nhờ tổ chức này, các thao tác thêm xâu, kiểm tra tồn tại, hay đếm số xâu có tiền tố cho trước đều chạy trong $O (| s |)$ — chỉ phụ thuộc độ dài xâu, không phụ thuộc số xâu đã lưu. So với việc so sánh tuyến tính với từng xâu trong tập (mất $O (N \cdot | s |)$ ), Trie nhanh hơn rất nhiều khi tập lớn, và đặc biệt nó xử lý truy vấn theo tiền tố một cách tự nhiên mà set/unordered_set không làm được.

Một biến thể quan trọng là Trie nhị phân (01-Trie / XOR Trie): thay vì lưu ký tự, ta lưu số nguyên theo từng bit. Nó cho phép tìm số trong tập có XOR với một giá trị $x$ lớn nhất trong $O (\log V)$ .

Ý tưởng / Trực giác

Ý tưởng cốt lõi: các xâu có chung tiền tố thì dùng chung phần đầu đường đi. Ví dụ cat, car, card đều đi qua cùng các cạnh c -> a, rồi mới rẽ nhánh. Nhờ đó:

Khi đi từ gốc theo các ký tự của một xâu, ta luôn ở đúng node đại diện cho tiền tố đã đọc. Muốn biết một xâu có tồn tại không, chỉ cần đi theo nó tới cuối rồi kiểm tra node đó có được đánh dấu "kết thúc" không. Đó là lý do thao tác là $O (| s |)$ : mỗi ký tự đi đúng một bước.
Truy vấn theo tiền tố trở nên hiển nhiên: tất cả xâu có tiền tố $p$ nằm trong cây con gốc tại node ứng với $p$ . Nếu tại mỗi node ta lưu thêm cnt = số xâu đi qua node đó, thì "đếm số xâu có tiền tố $p$ " chỉ là đọc cnt tại node $p$ — $O (| p |)$ .

Với Trie nhị phân, trực giác là tham lam theo bit từ cao xuống thấp. Bit cao quyết định giá trị lớn hơn bit thấp gộp lại (vì $2^{k} > 2^{k - 1} + \dots + 2^{0}$ ). Nên để $x \oplus y$ lớn nhất, tại mỗi bit ta ưu tiên chọn nhánh có bit ngược với bit của $x$ (cho ra bit XOR bằng 1); nếu nhánh đó tồn tại trong cây thì luôn đi vào, vì lợi ích ở bit cao này áp đảo mọi tổn thất có thể ở các bit thấp hơn. Trie giúp ta "thử cả tập số cùng lúc": tại mỗi node, sự tồn tại của con 0/1 cho biết tập số còn lại có số nào hợp với lựa chọn của ta hay không.

Ví dụ chạy tay

Trie ký tự — chèn `{cat, car, card, dog}`

Chèn lần lượt, dùng chung tiền tố:

        (root)
        /    \
       c      d
       |      |
       a      o
      / \     |
     t   r    g*      <- "dog" kết thúc ở đây
     |   |
     *   *            <- "cat" và "car" kết thúc
         |
         d
         |
         *            <- "card" kết thúc

Dấu * đánh dấu node kết thúc của một xâu. Truy vấn has_prefix("ca"): đi root -> c -> a, node a tồn tại nên trả về true. Truy vấn search("ca"): tới node a nhưng nó không có dấu *, nên false — ca là tiền tố nhưng không phải một xâu đã chèn. Đếm số xâu có tiền tố ca: cây con tại a chứa cat, car, card → 3.

Trie nhị phân — `max_xor` với $x$

Giả sử đã chèn ${2, 5}$ với 3 bit: $2 = 010_{2}$ , $5 = 101_{2}$ . Cây (bit cao bên trên):

        (root)
        /    \
   bit0=0    bit1=1
      |         |
   bit1=1    bit2=0
      |         |
   bit2=0    bit3=1
   (số 2)    (số 5)

Tìm max_xor(3) với $3 = 011_{2}$ . Đi từ bit cao nhất (bit 2):

bit của 3	muốn (ngược)	có nhánh đó?	đi vào	XOR tại bit
$0$	$1$	có (nhánh tới 5)	$1$	$1 \to + 4$
$1$	$0$	có (5 có bit kế là 0)	$0$	$1 \to + 2$
$1$	$0$	không (5 có bit cuối 1) → đành đi $1$	$1$	$0$

Kết quả $= 4 + 2 = 6$ , đúng bằng $3 \oplus 5 = 011 \oplus 101 = 110_{2} = 6$ (lớn hơn $3 \oplus 2 = 1$ ).

Cài đặt

Trie ký tự

Dùng mảng tĩnh để tránh chi phí cấp phát động (nhanh và an toàn trong thi đấu). tot là số node đã tạo; node $1$ là gốc.

const int MAXN = 1e6 + 5;   // tổng độ dài tất cả các xâu + 5
const int ALPHA = 26;

int trie[MAXN][ALPHA];      // trie[u][c] = node con theo ký tự c (0 = không có)
int end_cnt[MAXN];          // số xâu KẾT THÚC tại node này
int pass_cnt[MAXN];         // số xâu ĐI QUA node này (để đếm theo tiền tố)
int tot = 1;                // node 1 là gốc

void insert(const string& s) {
    int cur = 1;
    for (char c : s) {
        int ch = c - 'a';
        if (!trie[cur][ch]) trie[cur][ch] = ++tot;  // tạo node mới khi cần
        cur = trie[cur][ch];
        pass_cnt[cur]++;                            // mỗi xâu đi qua node này
    }
    end_cnt[cur]++;                                 // đánh dấu kết thúc
}

// Xâu s có nằm trong tập không?
bool search(const string& s) {
    int cur = 1;
    for (char c : s) {
        int ch = c - 'a';
        if (!trie[cur][ch]) return false;           // đứt đường -> không có
        cur = trie[cur][ch];
    }
    return end_cnt[cur] > 0;                         // phải có xâu KẾT THÚC ở đây
}

// Số xâu trong tập có tiền tố p
int count_prefix(const string& p) {
    int cur = 1;
    for (char c : p) {
        int ch = c - 'a';
        if (!trie[cur][ch]) return 0;
        cur = trie[cur][ch];
    }
    return pass_cnt[cur];                            // mọi xâu đi qua node p
}

Bản Python (dùng dict, gọn nhưng chậm hơn — hợp cho bảng chữ cái lớn/thưa):

class Trie:
    def __init__(self):
        self.children = {}   # ánh xạ ký tự -> Trie con
        self.end = 0         # số xâu kết thúc tại đây
        self.passing = 0     # số xâu đi qua đây

    def insert(self, s):
        cur = self
        for c in s:
            if c not in cur.children:
                cur.children[c] = Trie()
            cur = cur.children[c]
            cur.passing += 1
        cur.end += 1

    def count_prefix(self, p):
        cur = self
        for c in p:
            if c not in cur.children:
                return 0
            cur = cur.children[c]
        return cur.passing

Trie nhị phân (XOR Trie)

const int MAXN = 2e5 + 5;
const int BITS = 30;                 // đủ cho giá trị < 2^30 (~1e9)

int trie[MAXN * BITS][2];            // 2 con: bit 0 và bit 1
int tot = 1;

void insert(int x) {
    int cur = 1;
    for (int i = BITS - 1; i >= 0; i--) {     // từ bit CAO xuống thấp
        int bit = (x >> i) & 1;
        if (!trie[cur][bit]) trie[cur][bit] = ++tot;
        cur = trie[cur][bit];
    }
}

// Trả về giá trị (x XOR y) lớn nhất với y nào đó đã insert
int max_xor(int x) {
    int cur = 1, res = 0;
    for (int i = BITS - 1; i >= 0; i--) {
        int bit = (x >> i) & 1;
        int want = bit ^ 1;                   // muốn bit ngược để XOR ra 1
        if (trie[cur][want]) {
            res |= (1 << i);                  // chiếm được bit này
            cur = trie[cur][want];
        } else {
            cur = trie[cur][bit];             // đành đi nhánh cùng bit
        }
    }
    return res;
}

Ví dụ ứng dụng kinh điển: tìm cặp $(i, j)$ có $A_{i} \oplus A_{j}$ lớn nhất — chèn dần và truy vấn:

int ans = 0;
insert(0);                       // hoặc bắt đầu với phần tử đầu
for (int x : A) {
    ans = max(ans, max_xor(x));  // XOR tốt nhất với các số đã thấy
    insert(x);
}

Độ phức tạp

Thao tác	Thời gian	Lý do
`insert` (ký tự)	$O (\| s \|)$	đi đúng một bước cho mỗi ký tự
`search` / `count_prefix`	$O (\| s \|)$	tương tự, chỉ duyệt theo xâu
Xây toàn bộ Trie	$O (\sum \| s_{i} \|)$	mỗi ký tự của mỗi xâu xử lý đúng một lần
`insert` / `max_xor` (nhị phân)	$O (\log V)$	đi qua đúng `BITS` tầng

Bộ nhớ: với Trie ký tự dùng mảng tĩnh, mỗi node tốn một hàng ALPHA con, nên tổng là $O (số node \cdot ALPHA)$ , mà số node $\leq 1 + \sum | s_{i} |$ . Đây là điểm tốn kém: với ALPHA = 26 và tổng độ dài $10^{6}$ , mảng int trie[10^6][26] đã là khoảng $26 \cdot 10^{6}$ số nguyên (~100 MB) — phải tính sát giới hạn bộ nhớ. Nếu bảng chữ cái lớn hoặc thưa, chuyển sang map/unordered_map mỗi node để tiết kiệm, đổi lấy hằng số chậm hơn. Trie nhị phân tốn $O (N \cdot BITS)$ node.

⚠️ Lỗi thường gặp

Nhầm "tồn tại tiền tố" với "tồn tại xâu". search phải kiểm tra end_cnt[cur] > 0 ở node cuối; nếu chỉ kiểm tra "đi tới được node cuối" thì ca sẽ bị báo có dù chỉ cat được chèn. Đây là lỗi off-by-meaning phổ biến nhất.
Mảng node quá nhỏ → ghi đè bộ nhớ. MAXN phải $\geq 1 + tổng độ dài tất cả các xâu$ , không phải số xâu. Đặt thiếu gây lỗi ngầm (truy cập ngoài mảng, sai kết quả không đoán được). Trie nhị phân cần $N \cdot BITS$ node, dễ quên nhân BITS.
Sai số bit BITS trong Trie nhị phân. Phải đủ lớn để chứa giá trị tối đa: $10^{9} < 2^{30}$ nên cần BITS = 30 (bit 0..29). Nếu giá trị tới $2^{31}$ hoặc dùng XOR tiền tố có thể lớn hơn, phải tăng BITS và dùng long long, đồng thời 1LL << i để tránh tràn số khi dịch bit vượt 31.
Duyệt bit sai chiều. Phải đi từ bit cao xuống thấp; nếu lặp từ bit thấp lên, chiến lược tham lam sai hoàn toàn vì không còn tính chất "bit cao áp đảo".
Quên reset giữa các test case. Nếu chương trình chạy nhiều bộ test, phải đặt lại tot = 1 và xoá (memset) phần mảng đã dùng — nhưng memset cả mảng khổng lồ mỗi test có thể TLE; chỉ nên reset đúng vùng [0, tot] đã chạm.
Dùng node 0 làm gốc. Vì trie[u][c] == 0 được quy ước là "không có con", node gốc phải đánh số khác 0 (ở đây là 1). Lấy gốc là 0 sẽ khiến không phân biệt được "con thật" với "không có con".

Biến thể / Mở rộng

Đếm/xoá có trọng số: lưu pass_cnt và end_cnt để hỗ trợ xoá xâu (giảm đếm dọc đường) và đếm theo tiền tố.
Truy vấn XOR với điều kiện: kết hợp Trie nhị phân với lưu thêm chỉ số/thời điểm tại node để trả lời "XOR lớn nhất với phần tử trong một khoảng" (persistent trie).
Aho–Corasick: mở rộng Trie với liên kết hậu tố (suffix link) để khớp nhiều mẫu cùng lúc trong một văn bản.
XOR mảng con: đặt $P_{i} = A_{1} \oplus \dots \oplus A_{i}$ (tiền tố XOR); khi đó XOR đoạn $[l, r] = P_{r} \oplus P_{l - 1}$ , đưa bài toán XOR mảng con lớn nhất về tìm cặp tiền tố XOR cho XOR lớn nhất — đúng bài toán của Trie nhị phân.

Bài tập luyện

Gợi ý từ (autocompletes) — (Intermediate) Tìm từ thứ $K$ theo thứ tự từ điển trong các từ có tiền tố cho trước — luyện chèn xâu + đếm theo tiền tố trên Trie.
XOR Mảng Con Lớn Nhất (xorsubarray) — (Advanced) Dùng tiền tố XOR rồi 01-Trie để tìm XOR đoạn lớn nhất — bài chuẩn cho Trie nhị phân.
Xếp đầu tiên (first) — (Veteran) Xác định xâu nào có thể đứng đầu theo một hoán vị bảng chữ cái — xây Trie rồi suy ra ràng buộc thứ tự ký tự giữa các nhánh anh em.
Số Điện Thoại (phonenums22) — (Expert) Kết hợp Trie với quy hoạch động trên tập từ điển — bài nâng cao tổng hợp.