字典树 (Trie) - 数据结构

什么是字典树？

字典树（Trie，又称前缀树）是一种哈希树的变体。它的核心特点在于：

共享前缀：利用字符串的公共前缀来减少存储空间。
高检索速度：查找长度为 $L$ 的单词，时间复杂度仅为 $O(L)$，与字典中存储的单词总数量无关！
节点含义：节点自身一般不直接存储完整单词，而是根据其在树中的路径（字符连线）来隐式代表前缀。每个节点都附带一个 isEnd 标记，标示是否存在单词在此处结尾。

输入小写英文字母组成的单词（如 "cat", "car", "dog"），点击"插入单词"来观察它如何动态共享前缀并标记结尾。

C++ 核心代码对照

Trie (字典树) C++ 标准实现

class Trie {
private:
    struct TrieNode {
        TrieNode* children[26]; // 26个英文字母指针
        bool isEnd;             // 单词结尾标记

        TrieNode() {
            isEnd = false;
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
        }
    };

    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    // 插入单词
    void insert(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (curr->children[idx] == nullptr) {
                curr->children[idx] = new TrieNode(); // 动态分裂创建新节点
            }
            curr = curr->children[idx]; // 沿着路径向下走
        }
        curr->isEnd = true; // 标记单词结束
    }

    // 查询完整单词是否存在
    bool search(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (curr->children[idx] == nullptr) return false;
            curr = curr->children[idx];
        }
        return curr->isEnd; // 必须是完整的单词结尾
    }
};