字典树（Trie）¶

概述¶

字典树（Trie，又称前缀树）是一种树形数据结构，专门用于高效存储和检索**字符串集合**。它利用字符串的公共前缀来减少存储空间和查询时间，广泛应用于自动补全、拼写检查、IP路由等场景。

核心思想：字典树通过共享公共前缀来节省存储空间。每个节点代表一个字符，从根到节点的路径代表一个字符串前缀。查找、插入的时间复杂度仅与字符串长度有关，与字典大小无关。

字典树的重要性¶

graph TB
    subgraph "字典树的应用领域"
        A["字典树 Trie"] --> B["自动补全<br/>搜索引擎/输入法"]
        A --> C["拼写检查<br/>单词验证"]
        A --> D["IP路由<br/>最长前缀匹配"]
        A --> E["词频统计<br/>文本分析"]
        A --> F["字符串排序<br/>字典序遍历"]
    end
    
    style A fill:#E3F2FD,stroke:#2196F3,stroke-width:2px

Trie 结构详解¶

结构图示¶

存储字符串集合 {app, apple, apply, banana, band} 的字典树：

graph TB
    root["root"] --> a["a"]
    root --> b["b"]
    
    a --> p1["p"]
    p1 --> p2["p<br/>✓app"]
    p2 --> l1["l"]
    p2 --> l2["l"]
    l1 --> e["e<br/>✓apple"]
    l2 --> y["y<br/>✓apply"]
    
    b --> a2["a"]
    a2 --> n1["n"]
    n1 --> a3["a"]
    a3 --> n2["n<br/>✓banana"]
    n1 --> d["d<br/>✓band"]
    
    style root fill:#E3F2FD
    style p2 fill:#E8F5E9
    style e fill:#E8F5E9
    style y fill:#E8F5E9
    style n2 fill:#E8F5E9
    style d fill:#E8F5E9

✓ 标记：表示该节点是一个单词的结束。例如 p2 节点标记表示 "app" 是一个完整单词，而不仅仅是其他单词的前缀。

节点结构¶

每个 Trie 节点包含： - 子节点数组：指向下一层字符的指针（如 26 个字母） - 结束标记：标识从根到此节点是否构成单词

节点结构定义：

C
struct TrieNode {
    TrieNode* children[26];  // 子节点指针数组
    bool isEnd;              // 是否是单词结尾
    // 可选字段:
    // int count;    // 单词出现次数
    // void* value;  // 关联数据
};

内存布局示例（小写字母）：

TrieNode

children[0]: → 'a' 子节点

children[1]: → 'b' 子节点

children[2]: NULL (没有 'c' 开头的)

...

children[25]: → 'z' 子节点

isEnd: 0 或 1

Trie 特点¶

特点	说明	优势
公共前缀共享	前缀相同的单词共享节点	节省空间
高效查找	O(m) 查找，m 为字符串长度	与字典大小无关
空间换时间	每个节点存储多个指针	查找快速
前缀匹配	天然支持前缀操作	自动补全友好

核心操作详解¶

1. 插入操作¶

flowchart TB
    A["插入单词 word"] --> B["从根节点开始"]
    B --> C["遍历 word 的每个字符"]
    C --> D{"字符对应子节点存在?"}
    D -->|是| E["移动到该子节点"]
    D -->|否| F["创建新子节点"]
    F --> E
    E --> G{"还有字符?"}
    G -->|是| C
    G -->|否| H["标记当前节点为单词结尾<br/>isEnd = 1"]
    
    style H fill:#E8F5E9

插入示例：插入 "apple"

初始状态：空Trie，只有根节点

步骤1：处理字符 'a'

root 没有子节点 'a'，创建 → 当前位置: root → a

步骤2：处理字符 'p'

节点 'a' 没有子节点 'p'，创建 → 当前位置: root → a → p

步骤3：处理字符 'p'

节点 'p' 没有子节点 'p'，创建 → 当前位置: root → a → p → p

步骤4：处理字符 'l'

节点 'p' 没有子节点 'l'，创建 → 当前位置: root → a → p → p → l

步骤5：处理字符 'e'

节点 'l' 没有子节点 'e'，创建 → 当前位置: root → a → p → p → l → e

标记 isEnd = 1

✓ 完成！"apple" 已插入字典树

C
void insert(Trie *trie, const char *word) {
    TrieNode *curr = trie->root;
    
    for (int i = 0; word[i]; i++) {
        int index = word[i] - 'a';  // 计算字符索引
        
        if (curr->children[index] == NULL) {
            curr->children[index] = createNode();  // 创建新节点
        }
        
        curr = curr->children[index];  // 移动到子节点
    }
    
    curr->isEnd = 1;  // 标记单词结束
}

2. 查找操作¶

flowchart TB
    A["查找单词 word"] --> B["从根节点开始"]
    B --> C["遍历 word 的每个字符"]
    C --> D{"字符对应子节点存在?"}
    D -->|否| E["返回 false<br/>单词不存在"]
    D -->|是| F["移动到该子节点"]
    F --> G{"还有字符?"}
    G -->|是| C
    G -->|否| H{"isEnd == 1?"}
    H -->|是| I["返回 true<br/>单词存在"]
    H -->|否| J["返回 false<br/>只是前缀"]
    
    style E fill:#FFCDD2
    style I fill:#E8F5E9
    style J fill:#FFF3E0

C
int search(Trie *trie, const char *word) {
    TrieNode *curr = trie->root;
    
    for (int i = 0; word[i]; i++) {
        int index = word[i] - 'a';
        
        if (curr->children[index] == NULL) {
            return 0;  // 字符不存在，单词不存在
        }
        
        curr = curr->children[index];
    }
    
    return curr->isEnd;  // 返回是否是完整单词
}

3. 前缀匹配¶

检查是否存在以某前缀开头的单词：

C
int startsWith(Trie *trie, const char *prefix) {
    TrieNode *curr = trie->root;
    
    for (int i = 0; prefix[i]; i++) {
        int index = prefix[i] - 'a';
        
        if (curr->children[index] == NULL) {
            return 0;  // 前缀不存在
        }
        
        curr = curr->children[index];
    }
    
    return 1;  // 前缀存在
}

4. 删除操作¶

删除操作需要考虑多种情况：

flowchart TB
    A["删除单词 word"] --> B["找到单词末端节点"]
    B --> C{"单词存在?"}
    C -->|否| D["返回，无需删除"]
    C -->|是| E["取消单词标记<br/>isEnd = 0"]
    E --> F{"节点有子节点?"}
    F -->|是| G["保留节点<br/>删除完成"]
    F -->|否| H["删除节点"]
    H --> I["向上回溯"]
    I --> J{"父节点是其他单词或<br/>有其他子节点?"}
    J -->|是| K["停止删除"]
    J -->|否| L["删除父节点"]
    L --> I
    
    style G fill:#E8F5E9
    style K fill:#E8F5E9

C
int isEmpty(TrieNode *node) {
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->children[i] != NULL) {
            return 0;
        }
    }
    return 1;
}

TrieNode* delete(TrieNode *node, const char *word, int depth) {
    if (node == NULL) return NULL;
    
    // 到达单词末端
    if (word[depth] == '\0') {
        if (node->isEnd) {
            node->isEnd = 0;  // 取消单词标记
        }
        
        // 如果节点无子节点，可以删除
        if (isEmpty(node)) {
            free(node);
            node = NULL;
        }
        
        return node;
    }
    
    // 递归删除
    int index = word[depth] - 'a';
    node->children[index] = delete(node->children[index], word, depth + 1);
    
    // 回溯时检查是否可以删除当前节点
    if (isEmpty(node) && !node->isEnd) {
        free(node);
        node = NULL;
    }
    
    return node;
}

可视化演示¶

完整操作示例¶

操作序列：

insert("app"), insert("apple"), insert("apply"), search("app"), search("ap"), startsWith("app")

insert("app")

root → a → p → p^*

isEnd=1，标记为单词结尾

insert("apple") - 共享前缀 "app"

root → a → p → p^* → l → e^*

共享节点 "app"，不重复创建

insert("apply") - 共享前缀 "appl"

root → a → p → p^* → l → e^*

└ → y^*

查询结果：

• search("app") = true (isEnd=1)

• search("ap") = false (isEnd=0，只是前缀)

• startsWith("app") = true

自动补全功能¶

flowchart TB
    A["输入前缀 prefix"] --> B["找到前缀对应节点"]
    B --> C{"前缀存在?"}
    C -->|否| D["返回空列表"]
    C -->|是| E["DFS遍历子树"]
    E --> F["收集所有完整单词"]
    F --> G["返回补全列表"]
    
    style G fill:#E8F5E9

C
void collectWords(TrieNode *node, char *prefix, int depth, 
                  char result[][100], int *count) {
    // 当前节点是单词结束，添加到结果
    if (node->isEnd) {
        prefix[depth] = '\0';
        strcpy(result[*count], prefix);
        (*count)++;
    }
    
    // 递归收集所有子树中的单词
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->children[i] != NULL) {
            prefix[depth] = 'a' + i;
            collectWords(node->children[i], prefix, depth + 1, result, count);
        }
    }
}

int autocomplete(Trie *trie, const char *prefix, char result[][100]) {
    // 找到前缀对应节点
    TrieNode *curr = trie->root;
    for (int i = 0; prefix[i]; i++) {
        int index = prefix[i] - 'a';
        if (curr->children[index] == NULL) {
            return 0;  // 前缀不存在
        }
        curr = curr->children[index];
    }
    
    // 收集所有以 prefix 开头的单词
    char buffer[100];
    strcpy(buffer, prefix);
    int count = 0;
    collectWords(curr, buffer, strlen(prefix), result, &count);
    return count;
}

自动补全示例：

Trie 包含：{app, apple, apply, application}

输入前缀	补全结果
"app"	["app", "apple", "apply", "application"]
"appl"	["apple", "apply", "application"]
"appli"	["application"]

C++ 实现¶

C++
#include <string>
#include <vector>
#include <memory>

class Trie {
private:
    struct Node {
        std::vector<std::unique_ptr<Node>> children;
        bool isEnd;
        Node() : children(26), isEnd(false) {}
    };
    
    std::unique_ptr<Node> root;
    
    void collectAll(Node* node, std::string& prefix, std::vector<std::string>& result) {
        if (node->isEnd) result.push_back(prefix);
        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                prefix.push_back('a' + i);
                collectAll(node->children[i].get(), prefix, result);
                prefix.pop_back();
            }
        }
    }
    
public:
    Trie() : root(std::make_unique<Node>()) {}
    
    void insert(const std::string& word) {
        Node* curr = root.get();
        for (char c : word) {
            int index = c - 'a';
            if (!curr->children[index]) {
                curr->children[index] = std::make_unique<Node>();
            }
            curr = curr->children[index].get();
        }
        curr->isEnd = true;
    }
    
    bool search(const std::string& word) {
        Node* curr = root.get();
        for (char c : word) {
            int index = c - 'a';
            if (!curr->children[index]) return false;
            curr = curr->children[index].get();
        }
        return curr->isEnd;
    }
    
    bool startsWith(const std::string& prefix) {
        Node* curr = root.get();
        for (char c : prefix) {
            int index = c - 'a';
            if (!curr->children[index]) return false;
            curr = curr->children[index].get();
        }
        return true;
    }
    
    std::vector<std::string> autocomplete(const std::string& prefix) {
        Node* curr = root.get();
        for (char c : prefix) {
            int index = c - 'a';
            if (!curr->children[index]) return {};
            curr = curr->children[index].get();
        }
        
        std::vector<std::string> result;
        std::string p = prefix;
        collectAll(curr, p, result);
        return result;
    }
};

复杂度分析¶

操作	时间复杂度	空间复杂度	说明
插入	O(m)	O(m)	m 为字符串长度
查找	O(m)	O(1)	不需要额外空间
删除	O(m)	O(1)	可能删除多个节点
前缀匹配	O(m)	O(1)	同查找
自动补全	O(m + k)	O(k)	k 为补全结果数量

空间复杂度分析：

情况	空间复杂度	说明
最坏情况	O(N × M × 26)	所有字符串无公共前缀
最好情况	O(M × 26)	所有字符串共享前缀

N = 字符串数量，M = 最大字符串长度

实际应用中，公共前缀使得空间效率较高

应用场景¶

应用	说明	优势
自动补全	搜索引擎、IDE、输入法	实时响应前缀查询
拼写检查	检查单词是否存在	O(m) 快速验证
IP路由	最长前缀匹配	高效路由查找
词频统计	统计单词出现次数	节点存储计数
字符串排序	字典序遍历	DFS 自然有序
敏感词过滤	快速匹配敏感词	前缀匹配

参考资料¶

《算法导论》字符串匹配章节
《数据结构与算法分析》第12章
Wikipedia - Trie