由hash树变形到字典树

有关hash树的知识，上一篇文章已经介绍过了，字典树是哈希树的变形，又称前缀树，建议去看看，这里不多赘述

我推荐一下一个大佬的博客；https://blog.csdn.net/weixin_39778570/article/details/81990417?depth_1-utm_source=distribute.pc_relevant_right.none-task-blog-BlogCommendFromBaidu-1&utm_source=distribute.pc_relevant_right.none-task-blog-BlogCommendFromBaidu-1；

字典树的作用，
用来查找超长的文件中每个单词是否出现过，出现了几次；
特点搜索速度快，每次查找,删除，插入，的复杂度为O(len)，牺牲空间换时间，时间复杂度M*N(所以单词长度之和)
类似word文档中的查找功能，先构造树，然后查找。
字典树在存储的时候是将单词的每个字符一次分散在树的一条链上，从树到树根组合在一起就是整个单词，牺牲空间。
我们在单词结尾的地方标记，代表从树根到这个字母结束的单词存在。
每个节点记录的信息分为两块：
1.是否存在以它结尾的单词。
2.继续往下找，子儿子所在的地址（这里是节点的下表查找）
3.ti,以这个字符结束的单词出现的次数。
与hash树的比较
1。hash 树我们是用动态链表实现的，空间上具有优势，因为每当我们删除的时候我们都会delete空间。
2.hash树在分辨一堆树的时候我们采取的是每个节点从下往上记录信息，因为如果当前的特征数序列已经可以把它和前面的单词区分开我们就直接插入
我们分辨两个数是否相同，是看特征树序列的长度和相似度。
3.由2可知hash 树节点利用的效率远远高于字典树

用链表实现的哈希树：

  1 #include<iostream>
  2 #include<cstring>
  3 using namespace std;
  4 const int MAX_=10000; 
  5 struct Node{
  6     bool occupied;
  7     int son[27];
  8     int Ti;
  9     Node(){
 10         memset(son,0,sizeof(son));
 11         occupied=false;
 12         Ti=0;
 13     }    
 14 }tirenode[MAX_];
 15 int cnt=0;
 16 //插入操作：
 17 //1.我们先计算当前level的字母需要放在该节点的第几个儿子，index=a[level]-'a';
 18 //2.判断它的这个儿子是否存在
 19 //3.不存在我们创造一个新节点，存在儿子的节点下表（地址），指向儿子所在的地址
 20 //4.如果这是最后一个单词，他儿子后面没有单词，我么判断这个点是否已经记载了一个单词
 21 //5.没有的话进行标记，然后相同单词的次数加1，返回
 22 //6.如果不是最后一个下一个字母，我们把level变更到下一个字母重复操作1；
 23 // 
 24 void insert(int p,char *a,int level,int len)
 25 {
 26     int index=a[level]-'a';
 27     if(tirenode[p].son[index]==0)
 28     {
 29         tirenode[p].son[index]=++cnt; 
 30     } 
 31     p=tirenode[p].son[index];
 32     if(level==len-1)
 33     {
 34         if(tirenode[p].occupied==false)
 35         {
 36             tirenode[p].occupied=true;
 37         }
 38         tirenode[p].Ti++;
 39         return;
 40     }
 41     level++;
 42     insert(p,a,level,len);
 43 }
 44 //在这个字符串中间的单词是否出现 
 45 bool search(int p,char *a,int level,int len)
 46 {
 47     int index=a[level]-'a';
 48     if(tirenode[p].son[index]==0)//这个son节点是否存在，不存在则这个单词直接查找失败 
 49         return false;
 50     p=tirenode[p].son[index];
 51     if(level==len-1)//全部查找完，判断是否存在 
 52     {
 53         if(tirenode[p].occupied==false)
 54             return false;
 55         else
 56             return true; 
 57     } 
 58     level++;//继续匹配下一个字符 
 59     return search(p,a,level,len);
 60 } 
 61 void deletenode(int p,char *a,int level,int len)
 62 {
 63     int index=a[level]-'a';
 64     if(tirenode[p].son[index]==0) 
 65         return ;
 66     p=tirenode[p].son[index];
 67     if(level==len-1)//与查找差不多，在最后我们先将这个单词出现的次数减1，然后判断是否还有相同的单词 
 68     {
 69         tirenode[p].Ti=max(tirenode[p].Ti-1,0);
 70         if(tirenode[p].Ti==0)
 71             tirenode[p].occupied=false;
 72         return ;
 73     }
 74     level++;
 75     deletenode(p,a,level,len);//匹配下一个字符 
 76 }
 77 int main()
 78 {
 79     char a[100];
 80     int n;
 81     cin>>n;
 82     getchar();
 83     for(int i=1;i<=n;i++)
 84     {
 85         cin>>a;
 86         getchar();
 87         insert(0,a,0,strlen(a));
 88     }
 89     while(cin>>a)
 90     {
 91         if(search(0,a,0,strlen(a)))
 92         {
 93             cout<<"yes
";
 94             deletenode(0,a,0,strlen(a));
 95         }
 96         else
 97             cout<<"NO EXSIT
";
 98         getchar();
 99     } 
100 }

用数组模拟的字典树：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 const int MAX_=10000;
 6 const int CHAR=26;
 7 int trie[MAX_][CHAR]={0};
 8 bool color[MAX_]={false};
 9 int cnt=0;
10 void insert(char *w)
11 {
12     int len=strlen(w);
13     int p=0;
14     for(int i=0;i<len;i++)
15     {
16         int index=w[i]='a';
17         if(trie[p][index]==0)
18             trie[p][index]=++cnt;
19         p=trie[p][index];
20     }
21     color[p]=true;
22 }
23 int search(char *s)
24 {
25     int len=strlen(s);
26     int p=0;
27     for(int i=0;i<len;i++)
28     {
29         int index=s[i]-'a';
30         if(trie[p][index]==0)
31             return 0;
32         p=trie[p][index];
33     }
34     return color[p]==1;
35 }
36 int main()
37 {
38     int t,q;
39     char s[20];
40     scanf("%d%d",&t,&q);
41     while(t--)
42     {
43         scanf("%s",s);
44         insert(s);
45     }
46     while(q--)
47     {
48         scanf("%s",s);
49         if(search(s))
50             cout<<"yes
";
51         else cout<<"no";
52     }
53     return 0;
54 }