Trie
本文讲解了字典树的结构和实现方法。字典树是一种用于处理字符串集合的数据结构，特别适用于前缀查询和自动补全等应用。
概述
字典树（Trie）是一种树形数据结构，用于高效地存储和检索字符串集合中的键。每个节点代表一个字符，边表示字符之间的连接。字典树的根节点通常是空的，叶子节点代表一个完整的字符串。
字典树的主要操作包括插入、删除和查找。通过逐字符插入或查找,字典树能够在 O(L) 时间复杂度内完成操作,其中 L 是字符串的长度。
示例说明：上图展示了一个包含 "apple"、"and"、"cat"、"card" 四个单词的字典树。绿色节点标记了单词的结束位置,每条路径代表一个字符序列。
常用操作
插入（Insert）
功能：将一个字符串插入到 Trie 中。
实现思路：
- 从根节点开始，逐字符遍历字符串。
- 对于每个字符，如果对应的子节点不存在，则创建一个新的子节点。
- 遍历完所有字符后，标记当前节点为字符串的结束节点，并更新计数。
2. 删除（Delete）
功能：从 Trie 中移除一个字符串。
实现思路：
- 从根节点开始，逐字符遍历字符串，同时记录路径上的节点。
- 如果字符串存在，减少计数并取消结束标记。
- 回溯路径，删除不再需要的节点（即没有子节点且不是其他字符串的结束节点）。
3. 查找（Search）
功能：判断一个字符串是否存在于 Trie 中。
实现思路：
- 从根节点开始，逐字符遍历字符串。
- 如果某个字符的子节点不存在，则字符串不存在。
- 遍历完所有字符后，检查当前节点是否为字符串的结束节点。
4. 前缀查询（Prefix Search）
功能：判断 Trie 中是否存在以某个前缀开头的字符串。
实现思路：
- 从根节点开始，逐字符遍历前缀字符串。
- 如果某个字符的子节点不存在，则不存在以该前缀开头的字符串。
- 如果成功遍历整个前缀，说明存在至少一个以该前缀开头的字符串。
代码示例
示例代码中仅仅实现了插入和查找。
使用哈希表维护下一层节点
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
// Define the TreeNode structure
struct TreeNode {
unordered_map<char, TreeNode*> children; // Map each character to its child node
int count; // Store the number of strings that end at this node
TreeNode() : count(0) {} // Constructor to initialize count to 0
};
// Trie class for better encapsulation
class Trie {
private:
TreeNode* root;
public:
Trie() {
root = new TreeNode(); // Initialize root node
}
// Insert a string into the Trie
void insert(const string& str) {
TreeNode* node = root;
for (char c : str) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TreeNode();
}
node = node->children[c];
}
node->count++; // Mark the end of a string
}
// Query the count of a specific string in the Trie
int query(const string& str) {
TreeNode* node = root;
for (char c : str) {
if (node->children.find(c) == node->children.end()) {
return 0; // String not found
}
node = node->children[c];
}
return node->count; // Return the count of strings that end at this node
}
// Destructor to free allocated memory
~Trie() {
destroy(root);
}
private:
// Helper function to recursively delete nodes
void destroy(TreeNode* node) {
for (auto& child : node->children) {
destroy(child.second);
}
delete node;
}
};使用数组模拟
- 数组的一行存储树的一层，层之间的跳转关系存储在每行的具体位置上。
#include <iostream>
using namespace std;
const int N = 100010;
// trie树是一棵字典树 其最大深度为N 每一行都有26个可用节点
// cnt 存储以某个标号结尾的字符有多少个 idx是字符
int tree[N][26] , cnt[N] , idx;
char str[N];
void insert(char str[])
{
int p = 0;
for(int i = 0 ; str[i] ; i++)
{
int u = str[i] - 'a';
// 如果该位置没有标号 那么赋一个新的标号给它
// 如果这个位置有标号 那么重复利用该标号
if(!tree[p][u]) tree[p][u] = ++idx;
p = tree[p][u]; // 进入树的下一层 层次是由标号确定的。
}
cnt[p]++;
}
int query(char str[])
{
int p = 0;
for(int i = 0 ; str[i] ; i++)
{
int u = str[i] - 'a';
if(!tree[p][u]) return 0;
else p = tree[p][u];
}
return cnt[p];
}
int main()
{
int n;
cin >> n;
char op;
while(n--)
{
cin >> op;
scanf("%s" , str);
if(op == 'I') insert(str);
else cout << query(str) << endl;
}
}版权所有
版权归属：