Trie树、字典树、前缀树
个人认为这种树最好的叫法叫前缀树,比较好理解。
前缀树一般用来处理string查找问题,是一种高效的处理字符串相关问题的树形数据结构。
典型应用场景
trie树本人见过的最典型的应用就是在web路由匹配查找上,路由一般包括了很多字符串,并且需要和路由对应的处理函数绑定,请求也非常频繁,所以用trie树来处理还是比较高效的。
原理以及代码实现
trie树有一个根节点,这个节点一般不放任何数据。每个节点都有26个孩子,对应26个英文字母,节点存放的数据为一个一个英文字母。当当前节点到根节点能组成一个单词时做上标记,代表这是一个单词的结尾。每个string可以共享节点。
节点结构体
struct Node{
string word;
int count; //记录相同单词的个数
Node* child[26]; //孩子节点 26个字母
};
//初始化
void Clear(Node* node){
for(int i=0;i<26;i++){
node->child[i]=NULL;
}
node->count=0;
node->word="";
}
插入单词
//插入单词
void Insert(Node* root,string word){
Node* node = root;
for(int i=0;i<word.length();i++){
if(node->child[word[i]-'a']==NULL){
node->child[word[i]-'a'] = new Node;
Clear(node->child[word[i]-'a']);
}
node = node->child[word[i]-'a'];
}
node->word = word;
node->count+=1;
}
寻找带有前缀的单词节点
//寻找前缀节点
Node* search_pre(Node* root,string pre){
Node* node = root;
for(int i=0;i<pre.length();i++){
if(node->child[pre[i]-'a']==NULL)
return NULL;
node = node->child[pre[i]-'a']; //移到孩子节点上继续遍历
}
return node;
}
计算单词出现的次数
//寻找单词 返回单词数量 (是寻找前缀的一个特例)
int search_word(Node* root,string word){
Node* node = search_pre(root,word);
if(node!=NULL)
return node->count;
else
return 0;
}
打印单词
//根据节点打印全部单词
void print_all(Node* node){
if(node==NULL)
return;
if(node->count>0)
cout<<node->word<<endl;
//继续递归打印子节点
for(int i=0;i<26;i++){
print_all(node->child[i]);
}
}
//根据前缀打印全部单词
void print_pre(Node* root,string pre){
Node* node = root;
for(int i=0;i<pre.length();i++){
if(node->child[pre[i]-'a']==NULL){
cout<<"没有前缀"<<endl;
return;
}
node = node->child[pre[i]-'a'];
}
print_all(node);
}
删除单词
删除单词有两种情况
- 如果此单词尾部节点没有其他单词需要共享的节点,直接删除,节省空间
- 有其他单词共享字母节点,那就只清除单词标记
bool has_child(Node* node){
for(int i=0;i<26;i++){
if(node->child[i]!=NULL)
return true;
}
return false;
}
void DeleteWord(Node* node,string word,int lv){
if(lv==word.length() && node){
//清空节点
node->word="";
if(node->count==0){
cout<<"没有单词";
return;
}
node->count-=1;
if(!has_child(node)){
// delete node;
node = NULL;
}
}else{
DeleteWord(node->child[word[lv]-'a'],word,lv+1);
//清空单词标记
if(node){
node->word="";
node->count-=0;
if(!has_child(node)){
//delete node; //象征性的删除
node = NULL;
}
}
}
}
完整可运行代码
#include<iostream>
using namespace std;
struct Node{
string word;
int count; //记录相同单词的个数
Node* child[26]; //孩子节点 26个字母
};
void Clear(Node* node){
for(int i=0;i<26;i++){
node->child[i]=NULL;
}
node->count=0;
node->word="";
}
//插入单词
void Insert(Node* root,string word){
Node* node = root;
for(int i=0;i<word.length();i++){
if(node->child[word[i]-'a']==NULL){
node->child[word[i]-'a'] = new Node;
Clear(node->child[word[i]-'a']);
}
node = node->child[word[i]-'a'];
}
node->word = word;
node->count+=1;
}
//寻找前缀节点
Node* search_pre(Node* root,string pre){
Node* node = root;
for(int i=0;i<pre.length();i++){
if(node->child[pre[i]-'a']==NULL)
return NULL;
node = node->child[pre[i]-'a']; //移到孩子节点上继续遍历
}
return node;
}
//寻找单词 返回单词数量 (是寻找前缀的一个特例)
int search_word(Node* root,string word){
Node* node = search_pre(root,word);
if(node!=NULL)
return node->count;
else
return 0;
}
//根据节点打印全部单词
void print_all(Node* node){
if(node==NULL)
return;
if(node->count>0)
cout<<node->word<<endl;
//继续递归打印子节点
for(int i=0;i<26;i++){
print_all(node->child[i]);
}
}
//根据前缀打印全部单词
void print_pre(Node* root,string pre){
Node* node = root;
for(int i=0;i<pre.length();i++){
if(node->child[pre[i]-'a']==NULL){
cout<<"没有前缀"<<endl;
return;
}
node = node->child[pre[i]-'a'];
}
print_all(node);
}
bool has_child(Node* node){
for(int i=0;i<26;i++){
if(node->child[i]!=NULL)
return true;
}
return false;
}
void DeleteWord(Node* node,string word,int lv){
if(lv==word.length() && node){
//清空节点
node->word="";
if(node->count==0){
cout<<"没有单词";
return;
}
node->count-=1;
if(!has_child(node)){
// delete node;
node = NULL;
}
}else{
DeleteWord(node->child[word[lv]-'a'],word,lv+1);
//清空单词标记
if(node){
node->word="";
node->count-=0;
if(!has_child(node)){
//delete node; //象征性的删除
node = NULL;
}
}
}
}
int main(){
Node* root = new Node;
Clear(root);
Insert(root,"hello");
Insert(root,"hello");
Insert(root,"haha");
Insert(root,"he");
Insert(root,"case");
Insert(root,"cat");
Insert(root,"biningo");
cout<<search_word(root,"hello")<<endl;
DeleteWord(root,"hello",0);
cout<<search_word(root,"hello")<<endl;
DeleteWord(root,"hello",0);
cout<<search_word(root,"hello")<<endl;
DeleteWord(root,"hello",0);
cout<<search_word(root,"hello")<<endl;
}
原文链接: https://www.cnblogs.com/biningooginind/p/12522359.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
![字典树-Trie树-前缀树](https://www.ccppcoding.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/336340
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!