数据结构之Trie树

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/53463971

1、什么是Trie树

  Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 它有3个基本性质:     1.根节点不包含字符,除根节点外每一个节点都只包含一个字符。     2.从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。     3.每个节点的所有子节点包含的字符都不相同。

2、Trie树的构建      本质上,Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符,这样树的每条分支代表一则子串,而树的叶节点则代表完整的字符串。和普通树不同的地方是,相同的字符串前缀共享同一条分支。举一个例子。给出一组单词,inn, int, at, age, adv, ant, 我们可以得到下面的Trie:

搭建Trie的基本算法很简单,无非是逐一把每则单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在,就共享,否则创建对应的节点和边。比如要插入单词add,就有下面几步:     1.考察前缀"a",发现边a已经存在。于是顺着边a走到节点a。     2.考察剩下的字符串"dd"的前缀"d",发现从节点a出发,已经有边d存在。于是顺着边d走到节点ad     3.考察最后一个字符"d",这下从节点ad出发没有边d了,于是创建节点ad的子节点add,并把边ad->add标记为d。 具体Trie树的创建、插入、查询代码如下所示:

  1. //此函数只考虑26个英文字母的情况
  2. #include<iostream>
  3. #include<cstring>
  4. using namespace std;
  5. #define MAX_CHILD 26
  6. typedef struct Tree
  7. {
  8. int count; //用来标记该节点是个可以形成一个单词,如果count!=0,则从根节点到该节点的路径可以形成一个单词
  9.     struct Tree *child[MAX_CHILD];
  10. }Node,*Trie_node;
  11. Node* CreateTrie() //创建trie节点树
  12. {
  13.     Node *node=(Node*)malloc(sizeof(Node));
  14.     memset(node,0,sizeof(Node));
  15.     return node;
  16. }
  17. void insert_node(Trie_node root,char *str)      //trie树插入结点
  18. {
  19. if(root ==NULL || *str=='\0')
  20.         return;
  21.     Node *t=root;
  22.     char *p=str;
  23. while(*p!='\0')
  24. {
  25. if(t->child[*p-'a']==NULL)
  26. {
  27.          Node *tmp=CreateTrie();
  28.          t->child[*p-'a']=tmp;
  29. }
  30.      t=t->child[*p-'a'];
  31.      p++;
  32. }
  33.     t->count++;
  34. }
  35. void search_str(Trie_node root,char *str)             //查找串是否在该trie树中
  36. {
  37. if(NULL==root || *str=='\0')
  38. {
  39.      printf("trie is empty or str is null\n");
  40.      return;
  41. }
  42.     char *p=str;
  43.     Node *t=root;
  44. while(*p!='\0')
  45. {
  46. if(t->child[*p-'a']!=NULL)
  47. {
  48.          t=t->child[*p-'a'];
  49.             p++;
  50. }
  51. else
  52.              break;
  53. }
  54. if(*p=='\0')
  55. {
  56. if(t->count==0)
  57.             cout<<"该字符串不在trie树中,但该串是某个单词的前缀\n";
  58. else
  59.             cout<<"该字符串在该trie树中\n";
  60. }
  61. else
  62.         cout<<"该字符串不在trie树中\n";
  63. }
  64. void del(Trie_node root)      //释放整个字典树占的堆空间
  65. {
  66. int i;
  67. for(i=0;i<MAX_CHILD;i++)
  68. {
  69. if(root->child[i]!=NULL)
  70.             del(root->child[i]);
  71. }
  72.     free(root);
  73. }
  74. int main()
  75. {
  76. int i,n;
  77.     char str[20];
  78.     cout<<"请输入要创建的trie树的大小:";
  79.     cin>>n;
  80.     Trie_node root=NULL;
  81.     root=CreateTrie();
  82. if(root==NULL)
  83.         cout<<"创建trie树失败";
  84. for(i=0;i<n;i++)
  85. {
  86.         scanf("%s",str);
  87.         insert_node(root,str);
  88. }
  89.     cout<<"trie树已建立完成\n";
  90.     cout<<"请输入要查询的字符串:";
  91. while(scanf("%s",str)!=NULL)
  92. {
  93.      search_str(root,str);
  94. }
  95.     return 0;
  96. }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏绿巨人专栏

TypeScript中的怪语法

13130
来自专栏刘望舒

Android深入理解JNI(二)类型转换、方法签名和JNIEnv

前言 1.数据类型的转换 首先给出上一篇文章中android_media_MediaRecorder.cpp中的android_media_MediaReco...

27060
来自专栏崔庆才的专栏

Python操作Redis,你要的都在这了!

10.5K50
来自专栏博客园

Core官方DI解析(4)--CallSiteRuntimeResolver

​ CallSiteRuntimeResolver类型是一个创建或获取服务实例的类型,这个类型继承了CallSiteVisitor<TArgument, TRe...

10610
来自专栏码匠的流水账

Trie树使用实例

本文简单介绍下apache collection4中的PatriciaTrie的使用。

10410
来自专栏mathor

TRIE(4)

 这道题的大意是我们有一个网站,然后要配置规则,决定哪些IP能访问,哪些IP不能。这些规则大概长这个样子:

11140
来自专栏Jackson0714

PHP内核之旅-3.变量

16240
来自专栏信安之路

php 不用字母,数字和下划线写 shell

还有这个师傅的 《记一次拿webshell踩过的坑(如何用PHP编写一个不包含数字和字母的后门)》

51110
来自专栏博客园

Core官方DI解析(4)--CallSiteRuntimeResolver

这两个类都在其CallSiteVisitor<TArgument, TResult>基类中

9830
来自专栏AhDung

【手记】注意BinaryWriter写string的小坑——会在string前加上长度前缀length-prefixed

之前以为BinaryWriter写string会严格按构造时指定的编码(不指定则是无BOM的UTF8)写入string的二进制,如下面的代码:

32030

扫码关注云+社区

领取腾讯云代金券