博客详情 - oirush

admin 的博客
字典树 (Trie Tree)
admin SU @ 2026-6-7 20:01:09

一、算法概述

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

Trie 的核心特点是：

根节点不包含字符，除根节点外每个节点只包含一个字符
从根节点到某一节点的路径上的字符连接起来，即为该节点对应的字符串
每个节点的所有子节点包含的字符都不同

二、核心思想

字典树的核心思想是共享公共前缀。例如，存储 "cat"、"car" 和 "dog" 时：

        root
       /    \
      c      d
     /        \
    a          o
   / \          \
  t   r          g

"cat" 和 "car" 共享前缀 "ca"，因此它们共用 root → c → a 这条路径
在分支节点 a 处，它们分别走向 t 和 r，形成不同的字符串

这种结构使得：

插入：沿着字符串每个字符逐层向下，不存在则创建新节点
查找：沿着字符串每个字符逐层向下，路径存在且终点标记为单词结尾则找到
前缀匹配：找到前缀对应的节点后，其子树中的所有单词都以该前缀开头

三、算法步骤 / 伪代码

数据结构定义

struct TrieNode:
    children: array[26] of TrieNode  // 指向子节点的指针数组
    isEnd: bool                       // 标记是否为单词结尾
    count: int                        // 以该节点为结尾的单词数量

插入操作 (Insert)

function insert(word):
    node = root
    for each char c in word:
        index = c - 'a'
        if node.children[index] is null:
            node.children[index] = new TrieNode()
        node = node.children[index]
    node.isEnd = true
    node.count = node.count + 1

查找操作 (Search)

function search(word):
    node = root
    for each char c in word:
        index = c - 'a'
        if node.children[index] is null:
            return false
        node = node.children[index]
    return node.isEnd

前缀查找 (StartsWith)

function startsWith(prefix):
    node = root
    for each char c in prefix:
        index = c - 'a'
        if node.children[index] is null:
            return false
        node = node.children[index]
    return true

统计前缀单词数 (CountPrefix)

function countPrefix(prefix):
    node = root
    for each char c in prefix:
        index = c - 'a'
        if node.children[index] is null:
            return 0
        node = node.children[index]
    return dfsCount(node)  // 递归统计该子树中 isEnd=true 的节点数

四、C++ 代码实现

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Trie {
private:
    struct TrieNode {
        TrieNode* children[26];  // 26 个小写字母
        bool isEnd;              // 是否为单词结尾
        int wordCount;           // 以该节点结尾的单词数（支持重复插入）

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

    TrieNode* root;

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

    // ========== 插入单词 ==========
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
        node->wordCount++;
    }

    // ========== 查找单词是否完整存在 ==========
    bool search(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                return false;
            }
            node = node->children[idx];
        }
        return node->isEnd;
    }

    // ========== 判断是否存在以 prefix 为前缀的单词 ==========
    bool startsWith(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                return false;
            }
            node = node->children[idx];
        }
        return true;
    }

    // ========== 统计以 prefix 为前缀的单词数量 ==========
    int countPrefix(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (node->children[idx] == nullptr) {
                return 0;
            }
            node = node->children[idx];
        }
        return countWordsInSubtree(node);
    }

private:
    // DFS 统计子树中完整单词的数量
    int countWordsInSubtree(TrieNode* node) {
        if (node == nullptr) return 0;
        int total = node->wordCount;
        for (int i = 0; i < 26; i++) {
            if (node->children[i] != nullptr) {
                total += countWordsInSubtree(node->children[i]);
            }
        }
        return total;
    }
};

// ==================== 测试主函数 ====================
int main() {
    Trie trie;

    // 插入单词
    trie.insert("apple");
    trie.insert("apple");   // 重复插入
    trie.insert("app");
    trie.insert("application");
    trie.insert("banana");
    trie.insert("band");
    trie.insert("bandage");

    // 测试 search
    cout << "=== search 测试 ===" << endl;
    cout << "search(\"apple\"): "      << trie.search("apple")       << " (期望: 1)" << endl;
    cout << "search(\"app\"): "        << trie.search("app")         << " (期望: 1)" << endl;
    cout << "search(\"appl\"): "       << trie.search("appl")        << " (期望: 0)" << endl;
    cout << "search(\"banana\"): "     << trie.search("banana")      << " (期望: 1)" << endl;
    cout << "search(\"bandit\"): "     << trie.search("bandit")      << " (期望: 0)" << endl;

    // 测试 startsWith
    cout << "\n=== startsWith 测试 ===" << endl;
    cout << "startsWith(\"app\"): "    << trie.startsWith("app")     << " (期望: 1)" << endl;
    cout << "startsWith(\"ban\"): "    << trie.startsWith("ban")     << " (期望: 1)" << endl;
    cout << "startsWith(\"cat\"): "    << trie.startsWith("cat")     << " (期望: 0)" << endl;
    cout << "startsWith(\"banda\"): "  << trie.startsWith("banda")   << " (期望: 1)" << endl;

    // 测试 countPrefix
    cout << "\n=== countPrefix 测试 ===" << endl;
    cout << "countPrefix(\"app\"): "   << trie.countPrefix("app")    << " (期望: 3)" << endl;  // apple*2 + app + application
    cout << "countPrefix(\"ban\"): "   << trie.countPrefix("ban")    << " (期望: 3)" << endl;  // banana + band + bandage
    cout << "countPrefix(\"b\"): "     << trie.countPrefix("b")      << " (期望: 3)" << endl;
    cout << "countPrefix(\"cat\"): "   << trie.countPrefix("cat")    << " (期望: 0)" << endl;
    cout << "countPrefix(\"\"): "      << trie.countPrefix("")       << " (期望: 7)" << endl;  // 所有单词

    return 0;
}

五、复杂度分析

操作	时间复杂度	空间复杂度
插入 (Insert)	O(L)	O(L × Σ)
查找 (Search)		O(1)
前缀判断 (StartsWith)		O(1)
前缀计数 (CountPrefix)	O(L + K)	O(K) 递归栈

其中：

L：操作的字符串长度
Σ：字符集大小（本文为 26 个小写字母）
K：前缀子树中的节点总数
插入和查询均为 O(L)：每处理一个字符仅需一次数组索引操作，与 Trie 中已存储的单词数量无关
空间复杂度：最坏情况 O(总字符数 × Σ)，但在实际应用中因共享前缀远小于此值

六、应用场景

场景	说明
自动补全 / 搜索建议	输入前缀后，快速找出所有以该前缀开头的候选词
拼写检查	快速判断一个单词是否在词典中
IP 路由（最长前缀匹配）	路由器查找与目标 IP 地址匹配的最长前缀
词频统计	统计大量文本中各单词的出现频率
字符串排序	对 Trie 进行先序遍历即可按字典序输出所有字符串
异或最大值问题	二进制 Trie（0/1 Trie）可高效求解最大异或对等问题
基因组序列匹配	处理仅有 A/C/G/T 四种字符的长序列匹配

七、经典例题

LeetCode 208 - 实现 Trie (前缀树)

题目：实现一个 Trie 类，包含 insert、search 和 startsWith 三个方法。

本文第四节的 C++ 代码已完整实现该题的所有功能。核心要点回顾：

定义 TrieNode 结构体，包含 26 个子节点指针和 isEnd 标记
insert：逐字符向下遍历，遇到空节点则创建，最后标记 isEnd = true
search：逐字符向下遍历，若路径中断返回 false，否则返回最终节点的 isEnd
startsWith：与 search 类似，但不要求最终节点是单词结尾

变式练习：

实现 delete 方法删除单词（需要考虑共享前缀节点的引用计数）
实现通配符匹配（如 c.t 匹配 "cat" 和 "cot"）
使用 0/1 Trie 解决 LeetCode 421 - 数组中两个数的最大异或值

字典树 (Trie Tree)

一、算法概述

二、核心思想

三、算法步骤 / 伪代码

数据结构定义

插入操作 (Insert)

查找操作 (Search)

前缀查找 (StartsWith)

统计前缀单词数 (CountPrefix)

四、C++ 代码实现

五、复杂度分析

六、应用场景

七、经典例题

LeetCode 208 - 实现 Trie (前缀树)

状态

开发

支持

关于

字典树 (Trie Tree)

一、算法概述

二、核心思想

三、算法步骤 / 伪代码

数据结构定义

插入操作 (Insert)

查找操作 (Search)

前缀查找 (StartsWith)

统计前缀单词数 (CountPrefix)

四、C++ 代码实现

五、复杂度分析

六、应用场景

七、经典例题

LeetCode 208 - 实现 Trie (前缀树)

状态

开发

支持

关于

还没有账户？

登录