字典树（Trie树）是一种以字符为节点、按字符串前缀分层存储的树形数据结构。它把多个字符串中相同的前缀压缩到同一条路径上，从而在批量字符串检索、前缀匹配等场景中显著降低时间开销。每个从根节点出发到某一节点的路径，都对应一个前缀或完整单词。
一、Trie树的基本结构
Trie树的核心思想是空间换时间。假设我们要存储“cat”“car”“dog”三个单词，传统数组或链表需要逐个比较字符，而Trie树会让“c”作为公共头节点，其下分出“a”，再在“a”下分出“t”和“r”，这样“cat”和“car”共享了前两段路径。这种结构使得查询某个单词时，只需顺着字符一层层向下走，时间复杂度稳定在 O(L)，L为单词长度，与字典总量无关。
在代码实现中，每个节点通常包含一个子节点数组（或哈希表）以及一个标记位，用来表示当前节点是否为某个单词的结尾。使用数组时，若只处理小写字母，可以用长度为26的数组；处理更通用字符则用哈希映射。标记位非常关键，因为一条路径可能是另一个单词的前缀，例如“car”是“cart”的前缀，仅看路径存在不能判定“car”被录入过。
#include <iostream>
#include <vector>
using namespace std;
const int ALPHABET = 26;
struct TrieNode {
vector<TrieNode*> children;
bool isEnd;
TrieNode() : children(ALPHABET, nullptr), isEnd(false) {}
};
class Trie {
public:
Trie() { root = new TrieNode(); }
TrieNode* root;
};
二、Trie树的插入操作
插入逻辑非常直观：从根节点出发，依次取出待插入单词的每个字符，计算其在子节点数组中的下标。若对应子节点为空，就新建一个节点；若已存在，则直接下移。当所有字符处理完毕后，把最后到达的节点标记为单词结尾。这个过程不会修改已有公共前缀的路径，只会按需延伸新分支，因此多个单词插入不会互相覆盖。
需要注意边界情况，例如插入空字符串或重复单词。对于空串，一般视业务而定，多数场景忽略；对于重复单词，第二次插入时由于路径已存在，只需再次确认结尾标记即可，不需要重建节点。此外，若使用动态分配内存，应考虑析构函数释放节点，防止内存泄漏。下面给出完整的插入函数示例。
void insert(TrieNode* root, const string& word) {
TrieNode* node = root;
for (char ch : word) {
int idx = ch - 'a'; // 假设仅包含小写字母
if (node->children[idx] == nullptr) {
node->children[idx] = new TrieNode();
}
node = node->children[idx];
}
node->isEnd = true; // 标记单词结束
}
从性能角度看，插入操作和查询一样是 O(L)。当字典规模很大但字符集较小时，数组实现比哈希表略快，因为下标访问没有哈希计算开销；但字符集大时数组会浪费空间，此时用 unordered_map 更合适。设计时应结合业务数据分布来选存储方式。
三、Trie树的查询操作
查询分为两种常见需求：精确查询某个单词是否存在，以及判断某个前缀是否存在。精确查询与插入路径遍历几乎一致，只是在走完所有字符后，除了要到达对应节点，还必须检查该节点的 isEnd 标记是否为真。若路径中途断开或结尾标记为假，都说明单词不在树中。前缀查询则更简单，只需走完前缀字符，路径未断即返回真，不关心结尾标记。
下面的代码同时展示了这两种查询。可以看到，查询函数没有任何写操作，纯读路径，因此多个线程并发读同一棵Trie树时是安全的，但若有并发插入则需加锁或使用无锁结构。Trie树的查询优势在前缀匹配上尤为明显，比如输入法联想、搜索引擎下拉提示，都依赖这种顺路即得的特性。
bool search(TrieNode* root, const string& word) {
TrieNode* node = root;
for (char ch : word) {
int idx = ch - 'a';
if (node->children[idx] == nullptr) return false;
node = node->children[idx];
}
return node->isEnd;
}
bool startsWith(TrieNode* root, const string& prefix) {
TrieNode* node = root;
for (char ch : prefix) {
int idx = ch - 'a';
if (node->children[idx] == nullptr) return false;
node = node->children[idx];
}
return true;
}
四、插入与查询的对比及适用场景
插入负责构建路径，查询负责消费路径，二者共同决定了Trie树的实用性。插入时多花一次建节点的时间，后续所有查询都能受益；若只查一次，Trie树不如直接哈希。但在词库固定、查询频繁的系统里，Trie树的前缀能力是哈希表无法替代的。例如屏蔽词检测，可以把敏感词建成Trie，文本扫描时边走边匹配，一旦发现完整路径即命中。
另一个常见误区是认为Trie树一定省内存。实际上，每个节点都带一个26长度指针数组时，若字符分布稀疏，空指针极多，内存反而膨胀。改进方案包括使用哈希子节点、压缩Trie（将单链合并）、或基于双数组的实现。理解插入和查询的原貌，再根据场景做裁剪，才能写出既正确又高效的代码。
| 操作 | 时间复杂度 | 核心动作 |
|---|---|---|
| 插入 | O(L) | 沿字符建节点并标尾 |
| 精确查询 | O(L) | 沿字符走并验尾标 |
| 前缀查询 | O(L) | 沿字符走不验尾标 |
五、小结
字典树通过字符路径共享前缀，把字符串集合变成可顺藤摸瓜的树。插入时按需扩节点，查询时顺路验证，二者都是线性于长度的操作。掌握节点标记、子节点存储方式以及前缀与精确查询的差异，就能在联想搜索、词频统计、路由匹配等场景中稳妥使用Trie树。后续还可延伸出删除、通配查询与压缩优化，但插入与查询始终是理解这棵树的起点。