Tire树实现

什么是Trie树?

Trie树，又称字典树或者前缀树，是一种特殊的树形数据结构。它的目的是为了解决字符串快速查找的问题，可以高效地进行单词的插入、查询和删除等操作。

基本思想

Trie树的基本思想是用每个字符来作为树的一个节点，从根节点到某个节点路径上的字符连接起来就是该节点对应的字符串。Trie树的特点是根节点为空，每个节点都代表一个字符，从根节点到某个节点的路径上的所有字符连接起来就是该节点所代表的字符串；同时，每个节点维护着一个计数器，表示以该节点所代表的字符串为前缀出现过的次数。

应用

Trie树在字符串处理领域有着广泛的应用，如字符串匹配、字符串自动补全、最长公共前缀等。

我的理解

定义int int S[N][26] 二维数组来存储树.int cnt[N] 存储每个字符串出现的次数. int idx = 0 为当前可用的节点(节点编号).
在插入若干个字母组成的单词(全为小写字母)时,把单词中的每一个字母转变为数字.设char * des 为目标字符串,des[i]-'a' 得到字母a-z——0-25的映射.S[N][26]的第一维度[N]表示结点总数,第二维度[26]表示每个节点的下一个节点能向外延伸26条边(实际只要25条).S[p][u]表示节点编号为p的下一个子节点的编号,该子节点的字符为 u+'a' (数字到字母的反映射).

初学者的疑惑(为什么结点编号一定能限制一条路径?)

由于idx从0连续递增的,所以结点编号也是递增的,故在每次新增字符串后执行cnt[p++]表示以p的节点编号结束的字符串+1,怎么样才能找到结点编号为p的节点,只有从父节点不断向下递推才能得到.所以结点p只要有编号,那么到达它的路径被唯一限定了.

插入操作

void insert(char * des)
{
    int p =0; //下一个节点的节点编号
    for(int i = 0; des[i];i++)
    {

        int u = des[i] - 'a'; //把小写字母映射到 0-25
        if(!S[p][u]) S[p][u] =  ++idx;//新增结点编号
        p = S[p][u];
    }
    cnt[p]++;
}
1
2
3
4
5
6
7
8
9
10
11
12

查询操作

int query(char * des)
{

    int p = 0; //下一个节点的节点编号
    for(int i = 0; des[i];i++)
    {
        int u = des[i] - 'a';
        if(!S[p][u]) return 0;
        else  p =S[p][u];


    }
    return cnt[p];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

字符串统计的例题

#include "iostream"

using namespace std;

const int N = 1E5+10;

int S[N][26],idx=0;
int cnt[N];
char str[2],des[N];

void insert(char * des)
{
    int p =0; //下一个节点的节点编号
    for(int i = 0; des[i];i++)
    {

        int u = des[i] - 'a'; //把小写字母映射到 0-25
        if(!S[p][u]) S[p][u] =  ++idx;//新增结点编号
        p = S[p][u];
    }
    cnt[p]++;
}

int query(char * des)
{

    int p = 0; //下一个节点的节点编号
    for(int i = 0; des[i];i++)
    {
        int u = des[i] - 'a';
        if(!S[p][u]) return 0;
        else  p =S[p][u];


    }
    return cnt[p];
}

int main()
{

    int n =0;
    cin>>n;
    while(n--)
    {

        cin>>str>>des;
        if(str[0] == 'I')
        {
            //插入
           insert(des);

        }
        else
        { 
           //查询
           cout<<query(des)<<endl;

        }
    }


    return 0;
}
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