【算法分享】字典树 —插入、查询与状态标记详解

字典树(Trie)：高效的字符串处理利器 🌳

在处理大量字符串数据时，我们经常需要进行前缀匹配、单词查找、自动补全等操作。如果使用普通的数组或者哈希表，虽然能够解决问题，但是效率都不是很理想。那我们来学习一种专门为字符串而设计的数据结构——字典树（Trie）。

什么是字典树？ 🤔

字典树，又称前缀树或单词查找树，是一种有序树结构，用于保存关联数组，其中的键通常是字符串。它的名字来源于retrieval（检索），因为它能够快速检索字符串。

字典树的特点 ✨

• 前缀共享 🔗：具有公共前缀的字符串会共享相同的路径
• 空间优化 💾：相比存储完整字符串，可以节省大量存储空间
• 查找高效 ⚡：查找时间复杂度为O(m)，其中m为字符串长度
• 支持前缀操作 🔍：天然支持前缀匹配、自动补全等功能

字典树的结构 🏗️

字典树是一个多叉树，每个节点包含：

• 指向子节点的指针数组（通常为26个，对应a-z）
• 一个标记位，表示该节点是否为某个单词的结尾

struct node {
bool end = false; // 标记位
int count = 0;
node *n[26] = {nullptr};
};

示例：插入单词 “cat”, “car”, “card”, “care”, “careful”

root
|
c
|
a
/ \\
t r
| |
(end)
/ \\
d e
| |
(end) (end)
|
f
|
u
|
l
|
(end)

字典树的基本操作 ⚙️

1. 插入操作 (Insert) ➕

从根节点开始，按照字符串的每个字符逐层向下构建路径。如果路径不存在，则创建新节点。

时间复杂度：O(m)，m为字符串长度 ⏱️

void add(node* root, string s) {
node *p = root;
for (char c : s) {
int i = c – 'a';

// 如果节点路径不存在，就创建一个新的节点
if (!p->n[i])
p->n[i] = new node();
p = p->n[i];
}
// 标记单词结尾
p->end = true;
}

2. 查找操作 (Search) 🔎

从根节点开始，沿着字符路径向下查找。只有当路径存在且最后节点标记为单词结尾时，才表示找到了完整单词。

时间复杂度：O(m) ⏱️

bool search(node* root, string s) {
node *p = root;
for (char c : s) {
int i = c – 'a';

// 单词路径不存在
if (!p->n[i])
return false;

// 继续往下一个节点走
p = p->n[i];
}

// 必须检查是否为单词结尾
return p->end;
}

3. 前缀查找 (StartsWith) 🔍

与完整单词查找类似，但不需要检查最后一个节点是否为单词结尾，只需要路径存在即可。

关键区别：

• 完整单词查找：return node->end – 必须是完整单词
• 前缀查找：return true – 只要路径存在即可

实际例子： 假设字典树中有单词：[“car”, “card”, “care”, “careful”]

• search("car") → true（"car"是完整单词）
• search("ca") → false（"ca"不是完整单词）
• startsWith("ca") → true（存在以"ca"开头的单词）
• startsWith("car") → true（存在以"car"开头的单词）

bool startsWith(node* root, string s) {
node *p = root;
for (char c : s) {
int i = c – 'a';
if (!p->n[i])
return false;
p = p->n[i];
}

// 只要能走完整个前缀路径就返回true，不需要检查是否是end
return true;
}

例题示例 🚀

题目概述（于是他错误的点名开始了）

题目背景 一个化学竞赛教练在点名时因一边玩游戏一边点名，导致连续点到同一同学两次。现在需要写程序判断点名是否正确。

具体需求 给定班级合法学生名单（名字互不相同）。

按顺序读取点名的名字。

对每个名字输出：

• OK：名字在名单中，且是第一次出现。
• REPEAT：名字在名单中，但已经出现过。
• WRONG：名字不在名单中。

代码实现 💻

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef unsigned long long ll;

// 定义结点结构
struct node {
bool end = false;
bool isre = false;
node *n[26] = {nullptr};
};

// 添加字符到结点
void add(node *root, string s) {
node *p = root;
for (char c : s) {
int i = c – 'a';
if (!p->n[i]) {
p->n[i] = new node();
}
p = p->n[i];
}
p->end = true;
}

// 查找
int search(node* root, string s) {
node *p = root;
for (char c : s) {
int i = c – 'a';
if (!p->n[i]) // 路径断了 -> 单词不存在
return 0;
p = p->n[i];
}

// 路径存在，但不是单词结尾
if (!p->end) {
return 0;
}

// 已经被查询过
if (p->isre) {
return 2;
}

p->isre = true;
return 1;
}

// 创建根节点
node* createT() {
return new node();
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

// 初始化 Trie 根节点
node *root = createT();

int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
add(root, s); // 插入单词到字典树
}

int m;
cin >> m;
while (m—) {
string s;
cin >> s;
int l = search(root, s);
if (l == 0)
cout << "WRONG" << endl;
else if (l == 1)
cout << "OK" << endl;
else
cout << "REPEAT" << endl;
}
return 0;
}

复杂度分析 📊

其中：

• m：字符串长度
• N：字典树中的单词数量
• M：单词的平均长度
• ALPHABET_SIZE：字符集大小（如26个英文字母）

总结 📝

字典树是一种非常实用的数据结构，特别适合处理字符串相关的问题。虽然在某些情况下可能占用较多内存，但其在前缀操作上的高效性能使其在很多场景下都是最佳选择。

理解和掌握字典树不仅能帮助我们解决实际问题，也为学习更复杂的字符串算法（如AC自动机、后缀树等）打下坚实基础。