当前位置：首页 > news >正文

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

news 2025/12/6 21:24:33

字典树(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，不需要检查是否是endreturn true;
}

例题示例 🚀

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

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

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

按顺序读取点名的名字。

对每个名字输出：

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;elsecout << "REPEAT" << endl;}return 0;
}