Trie (Cây tiền tố)

Wiki › Cấu trúc dữ liệu › Cây

huunguyen · Last updated 3, Tháng 4, 2026, 20:31

Trie là cấu trúc dữ liệu dạng cây dùng để lưu tập hợp các xâu. Mỗi cạnh tương ứng với một ký tự; mỗi đường đi từ gốc đến một node kết thúc xác định một xâu trong tập.

Ứng dụng:

Kiểm tra tồn tại xâu, đếm xâu có tiền tố cho trước — $O (| s |)$
Tìm số nguyên trong tập có XOR với $x$ lớn nhất (Trie nhị phân)

Trie ký tự

const int MAXN = 1e6 + 5;
const int ALPHA = 26;

int trie[MAXN][ALPHA], end_cnt[MAXN], tot = 1;

void insert(const string& s) {
    int cur = 1;
    for (char c : s) {
        int ch = c - 'a';
        if (!trie[cur][ch]) trie[cur][ch] = ++tot;
        cur = trie[cur][ch];
    }
    end_cnt[cur]++;
}

// Kiểm tra xâu s có tồn tại không
bool search(const string& s) {
    int cur = 1;
    for (char c : s) {
        int ch = c - 'a';
        if (!trie[cur][ch]) return false;
        cur = trie[cur][ch];
    }
    return end_cnt[cur] > 0;
}

// Kiểm tra có xâu nào trong tập bắt đầu bằng tiền tố s không
bool has_prefix(const string& s) {
    int cur = 1;
    for (char c : s) {
        int ch = c - 'a';
        if (!trie[cur][ch]) return false;
        cur = trie[cur][ch];
    }
    return true;
}

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0  # số xâu kết thúc tại node này

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, s):
        cur = self.root
        for c in s:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.count += 1

    def search(self, s):
        cur = self.root
        for c in s:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.count > 0

    def has_prefix(self, s):
        cur = self.root
        for c in s:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True

Trie nhị phân (XOR Trie)

Lưu số nguyên theo từng bit từ bit cao xuống thấp. Dùng để tìm XOR lớn nhất trong tập hợp với một số cho trước.

const int MAXN = 3e5 + 5;
const int BITS = 30;  // điều chỉnh theo giá trị tối đa

int trie[MAXN * BITS][2], tot = 1;

void insert(int x) {
    int cur = 1;
    for (int i = BITS - 1; i >= 0; i--) {
        int bit = (x >> i) & 1;
        if (!trie[cur][bit]) trie[cur][bit] = ++tot;
        cur = trie[cur][bit];
    }
}

// Tìm y đã insert sao cho x XOR y lớn nhất, trả về giá trị XOR
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 = 1 - bit;  // muốn bit ngược để XOR = 1
        if (trie[cur][want]) {
            res |= (1 << i);
            cur = trie[cur][want];
        } else {
            cur = trie[cur][bit];
        }
    }
    return res;
}

Ví dụ: Cho mảng $A$ , tìm cặp $(i, j)$ có $A [i] \oplus A [j]$ lớn nhất.

int ans = 0;
for (int x : A) {
    ans = max(ans, max_xor(x));  // tìm XOR tốt nhất với các phần tử đã insert
    insert(x);
}

So sánh với các cấu trúc khác

	Trie	Hash Map (`unordered_map`)
Tìm xâu chính xác	$O (‖ s ‖)$	$O (‖ s ‖)$ trung bình
Tìm theo tiền tố	$O (‖ s ‖)$ — tự nhiên	Khó, cần xử lý thêm
Bộ nhớ	Nhiều hơn ( $O (‖ s ‖ \cdot ALPHA)$ )	Ít hơn
XOR tối đa	Trie nhị phân: $O (\log V)$	Không hỗ trợ trực tiếp

Bình luận

Không có bình luận tại thời điểm này.