Cài đặt Trie (Cây tiền tố) trong C++

Trie (Prefix Tree) là cấu trúc dữ liệu cây dùng để lưu trữ và truy xuất chuỗi ký tự hiệu quả. Mỗi nút đại diện cho một ký tự, đường từ gốc đến nút tạo thành một tiền tố. Ứng dụng: tự động hoàn thành (autocomplete), kiểm tra chính tả, từ điển, routing IP.

Đặc điểm

• Thời gian tìm/chèn/xóa: O(L) với L là độ dài chuỗi.
• Không gian: O(ALPHABET_SIZE * N * L) (có thể nén bằng compressed trie).
• Hỗ trợ duyệt theo thứ tự từ điển (lexicographical).

Cấu trúc nút

struct TrieNode {
    TrieNode* children[ALPHABET_SIZE]; // Mảng con trỏ đến các nút con
    bool isEndOfWord;                  // Đánh dấu kết thúc từ
    TrieNode() : isEndOfWord(false) {
        fill(begin(children), end(children), nullptr);
    }
};

Các thao tác cơ bản

1. Chèn (Insert)

void insert(TrieNode* root, const string& key) {
    TrieNode* curr = root;
    for (char ch : key) {
        int index = ch - 'A'; // Giả sử chỉ chữ hoa A-Z
        if (!curr->children[index])
            curr->children[index] = new TrieNode();
        curr = curr->children[index];
    }
    curr->isEndOfWord = true;
}

2. Tìm kiếm (Search)

bool search(TrieNode* root, const string& key) {
    TrieNode* curr = root;
    for (char ch : key) {
        int index = ch - 'A';
        if (!curr->children[index]) return false;
        curr = curr->children[index];
    }
    return curr->isEndOfWord;
}

3. Xóa (Delete) - Đệ quy

bool isEmpty(TrieNode* root) {
    for (int i = 0; i < ALPHABET_SIZE; i++)
        if (root->children[i]) return false;
    return true;
}

TrieNode* deleteNode(TrieNode* root, const string& key, int depth = 0) {
    if (!root) return nullptr;
    
    if (depth == key.size()) {
        if (root->isEndOfWord) root->isEndOfWord = false;
        if (isEmpty(root)) {
            delete root;
            return nullptr;
        }
        return root;
    }
    
    int index = key[depth] - 'A';
    root->children[index] = deleteNode(root->children[index], key, depth + 1);
    
    // Nếu nút hiện tại không phải cuối từ và không có con → xóa
    if (isEmpty(root) && !root->isEndOfWord) {
        delete root;
        return nullptr;
    }
    return root;
}

Chương trình hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

const int ALPHA_SIZE = 26; // Chỉ A-Z

struct TrieNode {
    TrieNode* children[ALPHA_SIZE];
    bool isEndOfWord;
    TrieNode() : isEndOfWord(false) {
        fill(begin(children), end(children), nullptr);
    }
};

TrieNode* createNode() { return new TrieNode(); }

void insert(TrieNode* root, const string& key) {
    TrieNode* curr = root;
    for (char ch : key) {
        int idx = ch - 'A';
        if (!curr->children[idx]) curr->children[idx] = createNode();
        curr = curr->children[idx];
    }
    curr->isEndOfWord = true;
}

bool search(TrieNode* root, const string& key) {
    TrieNode* curr = root;
    for (char ch : key) {
        int idx = ch - 'A';
        if (!curr->children[idx]) return false;
        curr = curr->children[idx];
    }
    return curr && curr->isEndOfWord;
}

bool isEmpty(TrieNode* root) {
    for (int i = 0; i < ALPHA_SIZE; i++)
        if (root->children[i]) return false;
    return true;
}

TrieNode* deleteNode(TrieNode* root, const string& key, int depth = 0) {
    if (!root) return nullptr;
    if (depth == key.size()) {
        if (root->isEndOfWord) root->isEndOfWord = false;
        if (isEmpty(root)) { delete root; return nullptr; }
        return root;
    }
    int idx = key[depth] - 'A';
    root->children[idx] = deleteNode(root->children[idx], key, depth + 1);
    if (isEmpty(root) && !root->isEndOfWord) { delete root; return nullptr; }
    return root;
}

int main() {
    string keys[] = {"HELLOWORLD", "HI", "BYE", "THE", "THENA"};
    TrieNode* root = createNode();
    for (auto& k : keys) insert(root, k);
    
    cout << (search(root, "HELLOWORLD") ? "Tim thay" : "Khong tim thay") << " HELLOWORLD\n";
    cout << (search(root, "HE") ? "Tim thay" : "Khong tim thay") << " HE\n";
    
    root = deleteNode(root, "THEN"); // Không tồn tại
    cout << (search(root, "THE") ? "Tim thay" : "Khong tim thay") << " THE (sau khi xoa THEN)\n";
    
    // TODO: Giải phóng bộ nhớ đệ quy toàn cây
    return 0;
}

Kết quả

Tim thay HELLOWORLD
Khong tim thay HE
Tim thay THE (sau khi xoa THEN)

Mở rộng

• Hỗ trợ chữ thường: tolower(ch) - 'a' hoặc mở rộng ALPHA_SIZE = 52 / 128 (ASCII).
• Dùng unordered_map cho alphabet lớn/thưa (tiết kiệm bộ nhớ).
• Thêm int count tại nút để đếm tần suất từ / hỗ trợ prefix count.

Trie là cấu trúc dữ liệu cốt lõi cho xử lý chuỗi, nền tảng của nhiều thuật toán nâng cao (Aho-Corasick, suffix tree...).