一、什么是Trie？

Trie（发音为"try"），也称为字典树、前缀树，是一种多叉树结构，专门用于高效存储和检索字符串集合。其核心特点是共享字符串的公共前缀，从而大幅减少冗余存储，同时加快查询速度。

例如，存储字符串 “apple”、“app”、“apricot” 时，Trie会共享前缀 “ap”，结构如下（简化示意）：

根节点
|
a
|
p
/ \
p   r
|   |
l   i
|   |
e  ...

二、Trie的结构

Trie的基本组成单位是节点（Node），每个节点包含：

子节点指针数组：用于指向后续字符（如存储26个小写字母时，数组大小为26）。
结束标志（isEnd）：布尔值，标记当前节点是否为某个字符串的结尾。

根节点是特殊节点，不存储任何字符，仅作为所有字符串的起始点。

从根节点到任意一个标记为isEnd = true的节点的路径，构成一个完整的字符串。

三、Trie的基本操作

Trie的核心操作包括插入（insert）、查找（search） 和前缀查询（startsWith），三者的时间复杂度均为 $O (L)$ ，其中 $L$ 是字符串的长度。

1. 插入（Insert）

目标：将字符串s插入Trie中。

步骤：

从根节点开始遍历。
对字符串s的每个字符c：

计算字符在数组中的索引（如 c - 'a'，假设为小写字母）。
若当前节点的子节点中不存在c，则创建新节点。
移动到对应子节点。

遍历结束后，将最后一个节点的isEnd标记为true（表示该节点是字符串的结尾）。

2. 查找（Search）

目标：判断字符串s是否在Trie中。

步骤：

从根节点开始遍历。
对字符串s的每个字符c：

若当前节点的子节点中不存在c，直接返回false。
移动到对应子节点。

遍历结束后，返回最后一个节点的isEnd值（只有isEnd = true才表示完整字符串存在）。

3. 前缀查询（StartsWith）

目标：判断Trie中是否存在以字符串s为前缀的字符串。

步骤：

与查找操作类似，从根节点开始遍历每个字符。
若任何字符不存在，返回false。
遍历结束后，直接返回true（无需检查isEnd，因为前缀本身不需要是完整字符串）。

四、时间复杂度分析

插入：遍历字符串的每个字符，时间复杂度为 $O (L)$ （ $L$ 为字符串长度）。
查找：同样遍历每个字符，时间复杂度为 $O (L)$ 。
前缀查询：与查找相同，时间复杂度为 $O (L)$ 。

相比哈希表（平均 $O (1)$ ，但最坏 $\cdot L)$ ， $N$ 为字符串数量），Trie在前缀匹配场景（如自动补全）中更高效，且时间复杂度更稳定。

五、C++代码实现

1. 节点结构定义

struct TrieNode {// 子节点数组：假设只存储小写字母，共26个TrieNode* children[26];// 标记当前节点是否为字符串的结尾bool isEnd;// 构造函数：初始化子节点为nullptr，isEnd为falseTrieNode() {for (int i = 0; i < 26; ++i) {children[i] = nullptr;}isEnd = false;}
};

2. Trie类实现

3. 使用示例

#include <iostream>
int main() {Trie trie;// 插入字符串trie.insert("apple");trie.insert("app");// 查找测试cout << trie.search("apple") << endl;   // 输出1（true）cout << trie.search("app") << endl;     // 输出1（true）cout << trie.search("ap") << endl;      // 输出0（false，不是完整字符串）// 前缀查询测试cout << trie.startsWith("ap") << endl;  // 输出1（true，有"apple"和"app"）cout << trie.startsWith("banana") << endl;  // 输出0（false）return 0;
}