Trie

Trie

字典树,又称单词查找树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

缺点也有:存储Trie会占用极大空间,对内存很不友好,是典型的以空间复杂度换时间复杂度的数据结构。

Trie树的基本性质可以归纳为:

  1. 根节点不包含字符,除根节点意外每个节点只包含一个字符。

  2. 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。

  3. 每个节点的所有子节点包含的字符串不相同。

Trie树有一些特性:

  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。

  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。

  3. 每个节点的所有子节点包含的字符都不相同。

  4. 如果字符的种数为n,则每个结点的出度为n,这也是空间换时间的体现,浪费了很多的空间。

  5. 插入查找的复杂度为O(n),n为字符串长度。

如图,将字符串abc, abcd, abd, b, bcd, efg, hii存入字典树。

Trie代码实现

存储树

1
2
3
4
5
struct Trie_node
{
bool exist; //记录当前节点是否存在单词
int next[26]; //指向下一个节点,具体多少个开多少个取决于有多少种字符。
};

插入字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void insert(int root,char* word)
{
int rot=root;
char* p=word;
int id;
while(*p)
{
id=*p-'a'; //转换成数字
if(trie[rot].next[id]==0)//如果下一个节点是空的
trie[rot].next[id]=++cnt;//插入新节点
rot=trie[rot].next[id];//将模拟指针指向下一个节点
p++;
}
trie[rot].exist=true;//记录当前节点是一个单词
}

查找字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool search(int root,char* word)
{
int rot=root;
char* p=word;
int id;
while(*p)
{
id=*p-'a'; //转换成数字
if(trie[rot].next[id]==0)//如果下一个节点是空的
return false;//那么在字典树内一定不存在这个单词
rot=trie[rot].next[id];//将模拟指针指向下一个节点
p++;
}
if(trie[rot].exist==true)//找到单词
return true;
else
return false;
}

按字典序排列所有字符串

在存储树的struct里面添加一个新变量char str[],

表示当前节点所构成的字符串。

在insert的时候,将每个节点的字符串记录下来。

之后进行dfs,按先序遍历输出字符串。

1
2
3
4
5
6
7
8
void dfs(int pos)
{
if(trie[pos].exist)
printf("%s\n",trie[pos].str);
for(int i=0;i<26;i++)
if(trie[pos].next[i]!=0)
dfs(trie[pos].next[i]);
}

删除已添加的字符串

删除操作,同插入操作一样,找到单词位置然后把exist值变成false

例题

HDU1251统计难题

考虑在存树的结构体里面加一个统计变量,来统计字符前缀出现的次数,之后查询时,查找新字符串位置的统计的次数值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
typedef struct Trie_node
{
int count; // 统计单词前缀出现的次数
struct Trie_node* next[26]; // 指向各个子树的指针
bool exist; // 标记该结点处是否构成单词
}TrieNode , *Trie;
TrieNode* createTrieNode()
{
TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode));
node->count = 0;
node->exist = false;
memset(node->next , 0 , sizeof(node->next)); // 初始化为空指针
return node;
}
void Trie_insert(Trie root, char* word)
{
Trie node = root;
char *p = word;
int id;
while(*p)
{
id = *p - 'a';
if(node->next[id] == NULL)
node->next[id] = createTrieNode();
node = node->next[id]; // 每插入一步,相当于有一个新串经过,指针向下移动
++p;
(node->count)++; // 这行代码用于统计每个单词前缀出现的次数(也包括统计每个单词出现的次数)
}
node->exist = true; // 单词结束的地方标记此处可以构成一个单词
}
int Trie_search(Trie root, char* word)
{
Trie node = root;
char *p = word;
int id;
while( *p )
{
id = *p - 'a';
node = node->next[id];
++p;
if(node == NULL)
return 0;
}
return node->count;
}
int main(void)
{
Trie root = createTrieNode(); // 初始化字典树的根节点
char str[12] ;
bool flag = false;
while(gets(str))
{
if(flag)
printf("%d\n",Trie_search(root , str));
else
{
if(strlen(str) != 0)
Trie_insert(root , str);
else
flag = true;
}
}
return 0;
}

洛谷P2580于是他错误的点名开始了

字典树的结构体里面记录一下当前单词是否被查找过,插入所有后直接查找即可,被查找过的记录一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
typedef struct Trie_node
{
bool exist;
struct Trie_node* next[26];
bool searched;
}TrieNode,*Trie;
int n,m;
TrieNode* creat()
{
Trie node=(TrieNode*)malloc(sizeof(TrieNode));
node->exist=false;
node->searched=false;
memset(node->next,0,sizeof(node->next));
return node;
}
void insert(Trie root,char* word)
{
Trie rot=root;
char* p=word;
int id;
while(*p)
{
id=*p-'a';
if(rot->next[id]==NULL)
rot->next[id]=creat();
rot=rot->next[id];
p++;
}
rot->exist=true;
}
int search(Trie root,char* word)
{
Trie rot=root;
char* p=word;
int id;
while(*p)
{
id=*p-'a';
if(rot->next[id]==NULL)
return 0;
rot=rot->next[id];
p++;
}
if(rot->exist==0)
return 0;//未找到
if(rot->searched)
return 2;//重复查找
rot->searched=true;//首次查找打标记
return 1;//首次查找
}
int main()
{
Trie root=creat();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
char str[60];
scanf("%s",str);
insert(root,str);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
char str[60];
scanf("%s",str);
switch(search(root,str))
{
case 0: printf("WRONG\n"); break;
case 1: printf("OK\n"); break;
case 2: printf("REPEAT\n"); break;
}
}
return 0;
}

洛谷P2292 [HNOI2004]L语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
typedef struct Trie_node
{
bool exist;
struct Trie_node* next[26];
}TrieNode,*Trie;
int n,m;
bool dp[maxn];
char str[maxn];
Trie creat()
{
Trie node=(Trie)malloc(sizeof(TrieNode));
node->exist=false;
memset(node->next,0,sizeof(node->next));
return node;
}
void insert(Trie root,char* word)
{
Trie node=root;
char* p=word;
int id;
while(*p)
{
id=*p-'a';
if(node->next[id]==NULL)
node->next[id]=creat();
node=node->next[id];
p++;
}
node->exist=true;
}
void search(Trie root,char* word)
{
Trie node=root;
char* p=word;
int id;
while(*p)
{
id=*p-'a';
if(node->next[id]==NULL)
return ;
node=node->next[id];
if(node->exist)
dp[p-str]=true;
p++;
}
}
int main()
{
Trie root=creat();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",str);
insert(root,str);
}
for(int i=1;i<=m;i++)
{
int ans=-1;
scanf("%s",str);
memset(dp,0,sizeof(dp));
search(root,str);
for(char* p=str;*p;p++)
if(dp[p-str])
{
ans=p-str+1;
search(root,p+1);
}
printf("%d\n",ans);
}
return 0;
}

洛谷P3294 [SCOI2016]背单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
    #include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
const int maxl=510010;
const int maxc=26;
typedef struct Trie_node
{
bool exist;
struct Trie_node* next[maxc];
int val;
}TrieNode,*Trie;
Trie creat()
{
Trie node=(Trie)malloc(sizeof(TrieNode));
node->exist=false;
memset(node->next,0,sizeof(node->next));
return node;
}
Trie root=creat();
char str[maxl];
int n,size[maxn];
vector<int> e[maxn];
long long f[maxn];
bool cmp(const int &x,const int &y)
{
return size[x]<size[y];
}
void insert(char* word, int num)
{
Trie node=root;
char* p=word+strlen(word)-1;
int id;
while(p>=word)
{
id=*p-'a';
if(node->next[id]==NULL)
node->next[id]=creat();
node=node->next[id];
p--;
}
node->val=num;
node->exist=true;
}
void build(Trie node,const int &p)
{
if(node->exist)
e[p].push_back(node->val);
for(int i=0;i<maxc;i++)
{
Trie nxt=node->next[i];
if(nxt!=NULL)
build(nxt,node->val?node->val:p);
}
}
void getsize(const int &x)
{
size[x]=1;
for(int i=0;i<e[x].size();i++)
{
int &y=e[x][i];
getsize(y);
size[x]+=size[y];
}
sort(e[x].begin(),e[x].end(),cmp);
}
void solve(const int &x)
{
f[x]=1;
long long tmp=0;
for(int i=0;i<e[x].size();i++)
{
int &y=e[x][i];
solve(y);
f[x]+=f[y]+tmp;
tmp+=size[y];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",str);
insert(str,i);
}
build(root,0);
getsize(0);
solve(0);
printf("%lld\n",f[0]-1);
return 0;
}