Trie树(字典树)

一、Trie树是什么？

Trie树又称字典树或前缀树，是一种能够快速查找一组字符串含有一个字符串的类似哈希表的树结构，是以空间换时间，利用字符串的前缀来降低查询时间。

与二叉树不同，Trie树有26子节点对应26个字母，根节点不包含字符串，从根节点到某个节点，经过的字符连起来的字符串就是对应的字符串。当储存结束一个字符串后，尾节点会用cnt[ ]数组来说明该字符串的次数。

二、怎么建立Trie树

2.1 字符串插入trie树

开始先定义 ： int son[N][26], cnt[N], idx;

son[N][26]:储存子节点的位置，分支最多26条

cnt[N]：存储以节点结尾的字符串个数

idx：表示当前要插入的节点（新建节点）

代码如下（示例）：

void insert(string str){
    int p = 0;//类似指针指向当前节点
    for(int i = 0; i < str.size(); i ++){
        int u = str[i] - 'a';        //当前节点是什么字符
        if(!son[p][u]) son[p][u] = ++ idx;//如果节点不存在就新建节点
        p = son[p][u];        //p 指向新建的节点
    }
    cnt[p] ++;//尾节点的字符数量加1
}

图解：

2.2 查找字符串

代码如下（示例）：

int query(char *str)
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;  //该节点不存在，即该字符串不存在
        p = son[p][u]; 
    }
    return cnt[p];  //返回字符串出现的次数
}

2.3 完整代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], cnt[N], idx, n;
void insert(string str){
    int p = 0;
    for(int i = 0; i < str.size(); i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++;
}
int query(string str){
    int p = 0;
    for(int i = 0; i < str.size(); i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    while(n --){
        string op, str;
        cin >> op >> str;
        if(op == "I") insert(str);
        else cout << query(str) << endl;
    }
    return 0;
}