前缀树(字典树)
本文主要介绍前缀树的概念以及其引用, 并且提供C++的前缀树实现.
概念介绍
前缀树(Trie)也称为字典树, 其基本结构是N叉树, 常用来存储字符串, 也可存储其他的数据类型. 前缀树中根节点不存储前缀(字符串), 其余每一个节点存储一个前缀, 一个节点对应的字符串是通过该节点的所有前缀组成的字符串.
前缀树名称的由来是树中任意节点的所有后代有共同的前缀.
前缀树有着广泛的应用, 例如自动补全, 拼写检查, 词频统计, IP 路由 (最长前缀匹配),
复杂度分析
再分析一下时间复杂度, n为输入字符串的长度, m为已插入字符串的数量.
- 插入字符串: O(n)
- 查询某字符串或某前缀: O(n)
与其他数据结构的对比
也有其他的数据结构可以用来存储字符串, 例如哈希表, 平衡树.
哈希表
哈希表可以在O(1)内查询特定字符串, 但在表增大之后会出现大量的冲突，使其时间复杂度增加到O(m), m为已插入字符串的数量
前缀树在存储有相同前缀的单词时会节省存储空间
哈希表无法高效的找到有相同前缀的所有字符串
哈希表无法按字典序枚举所有字符串
平衡树
- 平衡树中查找字符串的时间复杂度为 O(mlogn)
前缀树实现 (C++)
这里实现的前缀树只处理26个小写英文字母组成的串, 可以方便的扩展到更大的范围.
下面代码中实现了三个方法, 分别是:
- 插入字符串
- 查询字符串的数量
- 查询有某前缀的所有字符串的数量
此外, 本文这里使用定长数组来存储子节点的指针, 每个节点只存储1个字符, 其运算效率高, 但在字符集较大时会存在很大的存储开销. 另一种思路是利用哈希表存储前缀和对应子节点的关系, 这样可以节省空间.
此外还可以补充实现其他一些方法:
- 删除字符串
- 查询具有某前缀的所有字符串
- 按照字典序枚举所有字符串
// 前缀树
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class TrieNode{
private:
int count;
int prefix;
TrieNode* nextNode[26];
public:
TrieNode(){
this->count=0; // 以当前节点为结尾的单词数量
this->prefix=0; // 包含该前缀的单词数量
}
// 插入新单词
void insert(string str){
TrieNode* root = this;
// 注意：this指针可能为nullptr
if(root==nullptr || str.empty()){
return;
}
for(int i=0; i<str.size(); i++){
if(root->nextNode[str[i]-'a']==nullptr){
root->nextNode[str[i]-'a'] = new TrieNode();
}
root = root->nextNode[str[i]-'a'];
root->prefix++;
}
root->count++;
}
// 查询单词的数量
int search(string str){
TrieNode* root = this;
if(root==nullptr || str.empty()){
return 0;
}
for(int i=0; i<str.size(); i++){
if(root->nextNode[str[i]-'a']==nullptr){
return 0;
}
root = root->nextNode[str[i]-'a'];
}
return root->count;
}
// 查询以str为前缀的单词的数量
int searchPrefix(string str){
TrieNode* root = this;
if(root==nullptr || str.empty()){
return 0;
}
for(int i=0; i<str.size(); i++){
if(root->nextNode[str[i]-'a']==nullptr){
return 0;
}
root = root->nextNode[str[i]-'a'];
}
return root->prefix;
}
};
int main(){
TrieNode* trie = new TrieNode();
vector<string> test = {
"hello", "hello", "helloworld", "", "hello",
};
for(string t: test){
trie->insert(t);
}
cout<<trie->search("hello")<<" "<<trie->searchPrefix("hello")<<'\n';
return 0;
}
LeetCode相关题目
208. 实现 Trie (前缀树) - 力扣（LeetCode）
参考
数据结构与算法：字典树（前缀树） - 知乎 (zhihu.com)