数据结构之Trie树

╰半夏微凉° 2022-07-14 09:19 159阅读 0赞

1、什么是Trie树

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

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

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

![Center][]

搭建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.   
    
12. Node\* CreateTrie()                             //创建trie节点树  
    
13. \{   
    
14.     Node \*node=(Node\*)malloc(sizeof(Node));  
    
15.     memset(node,0,sizeof(Node));  
    
16.     return node;  
    
17. \}
18.   
    
19. void insert\_node(Trie\_node root,char \*str)      //trie树插入结点  
    
20. \{   
    
21.     if(root ==NULL || \*str=='\\0')  
    
22.         return;  
    
23.     Node \*t=root;   
    
24.   
    
25.     char \*p=str;  
    
26.       
    
27.     while(\*p!='\\0')  
    
28.     \{   
    
29.      if(t\->child\[\*p\-'a'\]==NULL)  
    
30.         \{   
    
31.          Node \*tmp=CreateTrie();  
    
32.          t\->child\[\*p\-'a'\]=tmp;          
    
33.         \}  
    
34.      t=t\->child\[\*p\-'a'\];  
    
35.      p\+\+;  
    
36.     \}  
    
37.     t\->count\+\+;  
    
38. \}  
    
39.   
    
40. void search\_str(Trie\_node root,char \*str)             //查找串是否在该trie树中  
    
41. \{   
    
42.     if(NULL==root || \*str=='\\0')  
    
43.     \{   
    
44.      printf("trie is empty or str is null\\n");  
    
45.      return;  
    
46.     \}  
    
47.   
    
48.     char \*p=str;  
    
49.     Node \*t=root;  
    
50.     while(\*p!='\\0')  
    
51.     \{        
    
52.      if(t\->child\[\*p\-'a'\]!=NULL)  
    
53.         \{   
    
54.          t=t\->child\[\*p\-'a'\];  
    
55.             p\+\+;  
    
56.         \}  
    
57.      else  
    
58.              break;  
    
59.     \}  
    
60.     if(\*p=='\\0')  
    
61.     \{   
    
62.      if(t\->count==0)  
    
63.             cout<<"该字符串不在trie树中，但该串是某个单词的前缀\\n";  
    
64.         else  
    
65.             cout<<"该字符串在该trie树中\\n";  
    
66.     \}  
    
67.     else  
    
68.         cout<<"该字符串不在trie树中\\n";  
    
69. \}  
    
70.   
    
71. void del(Trie\_node root)      //释放整个字典树占的堆空间  
    
72. \{   
    
73.     int i;  
    
74.     for(i=0;i<MAX\_CHILD;i\+\+)  
    
75.     \{   
    
76.      if(root\->child\[i\]!=NULL)  
    
77.             del(root\->child\[i\]);  
    
78.     \}  
    
79.     free(root);  
    
80. \}  
    
81.   
    
82. int main()  
    
83. \{   
    
84.     int i,n;  
    
85.     char str\[20\];  
    
86.     cout<<"请输入要创建的trie树的大小：";  
    
87.     cin>>n;   
    
88.     Trie\_node root=NULL;  
    
89.     root=CreateTrie();   
    
90.     if(root==NULL)  
    
91.         cout<<"创建trie树失败";  
    
92.     for(i=0;i<n;i\+\+)   
    
93.     \{   
    
94.         scanf("%s",str);  
    
95.         insert\_node(root,str);  
    
96.     \}  
    
97.     cout<<"trie树已建立完成\\n";  
    
98.     cout<<"请输入要查询的字符串:";  
    
99.     while(scanf("%s",str)!=NULL)  
    
100.     \{   
    
101.      search\_str(root,str);  
    
102.       
    
103.     \}  
    
104.     return 0;
105. \}
106.

[Center]: /images/20220714/94851c1305b840ae9aa0015e5cf86f22.png