一、Trie 树定位
Trie 树（前缀树 / 字典树）是专为字符串设计的树形结构，核心价值是通过 “前缀共享” 减少内存冗余，同时实现 O (k)（k 为字符串长度）的插入 / 查询效率，尤其适合 “前缀相关场景”（如自动补全、拼写检查）。
二、核心结构：节点设计与前缀共享
1. 节点结构体
Trie 的最小单元是节点，需存储子节点映射和单词结尾标记，C++ 中用结构体实现最简洁：
1
2
3
4
5
6
7
8
9
| struct TrieNode {
// 子节点：两种实现方案（按需选择）
// 方案1：数组（仅适用于固定小字符集，如小写字母，速度快）
TrieNode* children[26] = {nullptr};
// 方案2：哈希表（字符集不确定时用，如含数字/符号，灵活）
// unordered_map<char, TrieNode*> children;
bool isEnd = false; // 标记当前节点是否为某单词的结尾（避免前缀误判）
};
|
根节点是TrieNode* root = new TrieNode()，不存储实际字符，仅作为所有字符串的入口。
2. 前缀共享机制（核心优势）
多个字符串的公共前缀共用一套节点，例如 “apple” 和 “app”：
共用节点路径：root -> 'a' -> 'p' -> 'p'
“app” 在第三个'p'节点标记isEnd=true
“apple” 继续延伸：'p' -> 'l' -> 'e'，在'e'标记isEnd=true
相比哈希表存储完整字符串，Trie 可大幅减少重复前缀的内存开销。
三、核心操作：插入与查询（O (k) 复杂度）
所有操作均按 “字符遍历路径” 执行，逻辑线性且无冲突。
1. 插入操作（Insert）
流程：按字符串字符逐个遍历，无节点则新建，最后标记单词结尾。
1
2
3
4
5
6
7
8
9
10
11
| void insert(TrieNode* root, const string& word) {
TrieNode* curr = root;
for (char c : word) {
int idx = c - 'a'; // 仅适配方案1（数组子节点），方案2直接用c作为key
if (!curr->children[idx]) { // 路径不存在，新建节点
curr->children[idx] = new TrieNode();
}
curr = curr->children[idx]; // 移动到下一层节点
}
curr->isEnd = true; // 标记当前字符串结束
}
|
2. 查询操作（Search）
核心注意：需判断 “路径存在” 且 “终点是单词结尾”（避免将前缀误判为完整单词，如 “app” 是单词，“apple” 的前缀 “app” 不是完整单词）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| // 精准查询：判断word是否是Trie中的完整单词
bool search(TrieNode* root, const string& word) {
TrieNode* curr = root;
for (char c : word) {
int idx = c - 'a';
if (!curr->children[idx]) return false; // 路径断裂，不存在
curr = curr->children[idx];
}
return curr->isEnd; // 路径存在≠单词存在，需确认结尾标记
}
// 前缀查询：判断是否存在以prefix开头的单词（自动补全核心）
bool startsWith(TrieNode* root, const string& prefix) {
TrieNode* curr = root;
for (char c : prefix) {
int idx = c - 'a';
if (!curr->children[idx]) return false;
curr = curr->children[idx];
}
return true; // 只要路径存在，无论是否是单词结尾
}
|
四、与哈希表（unordered_map）的场景对比
Trie 不是哈希表的 “替代品”，而是 “互补品”，核心差异在前缀能力：
| 特性 |
Trie 树 |
哈希表（unordered_map） |
| 时间复杂度 |
O (k)（稳定，与数据量无关） |
平均 O (1)，最坏 O (n)（冲突时） |
| 前缀查询 |
原生支持（高效遍历子节点） |
不支持（需遍历所有 key，低效） |
| 内存占用 |
前缀共享，小字符集占优 |
存储完整 key，冗余度高 |
| 冲突风险 |
无冲突（路径唯一） |
需处理哈希冲突（链地址 / 红黑树） |
| 适用场景 |
前缀相关（自动补全、拼写检查、敏感词过滤） |
精准单键查询（如配置项读取、缓存） |
五、C++ 实现注意事项
内存管理：
动态节点（new创建）需手动销毁，避免内存泄漏，建议写递归销毁函数：
1
2
3
4
5
6
7
8
9
| void destroy(TrieNode* node) {
if (!node) return;
// 方案1：遍历数组销毁子节点
for (int i = 0; i < 26; ++i) destroy(node->children[i]);
// 方案2：遍历哈希表销毁子节点
// for (auto& [_, child] : node->children) destroy(child);
delete node;
}
// 使用后调用：destroy(root);
|
字符集适配：
空节点优化：
高频场景可改用 “节点池”（预先分配一批节点）减少new/delete开销，但基础实现无需过度设计。
六、典型应用场景
搜索引擎关键词提示：输入 “cloud”，快速遍历 “cloud” 节点的所有子节点，返回 “cloud computing”“cloud storage” 等；
单词拼写检查：输入 “appel”，查询时路径断裂，提示 “是否要输入 apple？”；
多模式匹配：敏感词过滤（一次遍历文本，匹配所有敏感词，比多正则匹配高效）。
总结
Trie 树的核心是 “前缀共享 + 路径遍历”，C++ 实现的关键是节点设计（数组 / 哈希表子节点）和内存管理。它在 “前缀相关场景” 中无可替代，与哈希表搭配可覆盖大部分字符串处理需求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| class Trie {
private:
// 1. 嵌套定义Trie节点结构体（仅类内部可见）
struct TrieNode {
TrieNode* children[26] = {nullptr}; // 子节点：适配小写字母（a-z）
bool isEnd = false; // 标记当前节点是否为单词结尾
};
TrieNode* root; // 根节点（所有单词的入口）
// 2. 辅助函数：递归销毁节点（用于析构和删除操作）
void destroyNode(TrieNode* node) {
if (!node) return; // 空节点直接返回
// 先递归销毁所有子节点（后序遍历）
for (int i = 0; i < 26; ++i) {
destroyNode(node->children[i]);
}
delete node; // 销毁当前节点，避免内存泄漏
}
// 3. 辅助函数：递归删除单词（核心逻辑：判断节点是否可回溯删除）
// 返回值：true=当前节点可删除（无其他子节点且不是其他单词结尾），false=不可删除
bool eraseHelper(TrieNode* node, const string& word, int index) {
// 递归终止条件1：已处理完单词所有字符
if (index == word.size()) {
if (!node->isEnd) return false; // 单词不存在，直接返回
node->isEnd = false; // 取消单词结尾标记
// 检查当前节点是否有子节点：有则不可删除
for (int i = 0; i < 26; ++i) {
if (node->children[i]) return false;
}
return true; // 无子孙节点，可删除
}
// 递归处理：计算当前字符的数组索引
int charIdx = word[index] - 'a';
// 递归终止条件2：路径断裂（单词不存在）
if (!node->children[charIdx]) return false;
// 递归删除子节点，并判断子节点是否可删除
bool canDeleteChild = eraseHelper(node->children[charIdx], word, index + 1);
if (canDeleteChild) {
// 子节点可删除：释放内存并置空指针
delete node->children[charIdx];
node->children[charIdx] = nullptr;
// 判断当前节点是否可删除：无其他子节点 + 不是其他单词结尾
if (!node->isEnd) {
for (int i = 0; i < 26; ++i) {
if (node->children[i]) return false;
}
return true;
}
}
return false; // 子节点不可删除，或当前节点是其他单词结尾
}
public:
// 4. 构造函数：初始化根节点
Trie() {
root = new TrieNode();
}
// 5. 析构函数：释放所有节点内存
~Trie() {
destroyNode(root);
}
// 6. 插入单词（支持仅小写字母，含非法字符容错）
void insert(const string& word) {
TrieNode* curr = root;
for (char c : word) {
int charIdx = c - 'a';
// 容错：仅允许小写字母（避免数组越界）
if (charIdx < 0 || charIdx >= 26) {
throw invalid_argument("Trie only supports lowercase letters (a-z).");
}
// 路径不存在则新建节点
if (!curr->children[charIdx]) {
curr->children[charIdx] = new TrieNode();
}
// 移动到下一层节点
curr = curr->children[charIdx];
}
curr->isEnd = true; // 标记单词结尾
}
// 7. 精准查询：判断单词是否完整存在于Trie中
bool search(const string& word) {
TrieNode* curr = root;
for (char c : word) {
int charIdx = c - 'a';
if (charIdx < 0 || charIdx >= 26) return false; // 非法字符直接返回不存在
if (!curr->children[charIdx]) return false; // 路径断裂，单词不存在
curr = curr->children[charIdx];
}
return curr->isEnd; // 路径存在≠单词存在，需验证结尾标记
}
// 8. 前缀查询：判断是否存在以prefix开头的单词
bool startsWith(const string& prefix) {
TrieNode* curr = root;
for (char c : prefix) {
int charIdx = c - 'a';
if (charIdx < 0 || charIdx >= 26) return false;
if (!curr->children[charIdx]) return false;
curr = curr->children[charIdx];
}
return true; // 只要路径存在，前缀就存在
}
// 9. 删除单词：返回是否成功删除（单词不存在则返回false）
bool erase(const string& word) {
// 从根节点开始，从第0个字符递归删除
return eraseHelper(root, word, 0);
}
};
|
