Trie 树
原创
字典树是字符串匹配中经常使用的一种数据结构,他大概是这样的一种数据结构,我们假设这样一种场景,我们从头开始匹配字符串,这里字符串我们只有英文,当然现实中有数字,中文等等,这些场景太过复杂,因此我们假设只有 26 个英文字母的字符串进行匹配.
因此,我们的树大概场景是这样的,从根节点开始,有 26 个子节点,每个子节点有 26 个子节点.
show me the code
// 定义数据结构
struct node{
int count; // 用于记录该节点包含的单词数量
struct node* child[26];
};// 对数据结构的操作 增删改查
//数据结构初始化 创建一个 node
struct node* create_node(){
struct node* pNode = new node();
pNode->count = 0;
for(int i = 0; i < 26; i++){
pNode->child[i] = NULL;
}
return pNode;
}
// 增 插入一个单词
void insert_node(struct node* root, char * key){
struct node* pNode = root;
char* p = key;
while(*p){
if(pNode->child[*p - 'a'] == NULL){
pNode->child[*p - 'a'] = create_node();
}
pNode = pNode->child[*p - 'a'];
++p;
}
pNode -> count +=1; // 这里的计数是在单词末尾计数
}
// 查询
int query_node(struct node * root, char* key){
struct node* pNode = root;
char* p = key;
while(*p && pNode != NULL){
pNode = pNode->child[*p - 'a'];
++p;
}
if(pNode == NULL) return 0;
return pNode->count;
}上述就是对数据的操作,包括初始化,增和查,那么为什么没有改和删, 首先一个就是成本,随着我们插入的单词数量增多,这棵树会越来越复杂,删除的成本越来越大.
而对于这样的匹配树来说改和删其实可以说是一个内容,与其进行修改不如直接添加一个新的分支.
到这里 Trie 树的实现基本结束.
我们可以发现相对于算法实现,对于实现数据结构,并对数据结构操作,相对来说没有那样考验智力,但是对于我们理解编程很有帮助.
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
