本笔记内容来源于算法基础课

Trie树

Trie树：高效地存储和查找字符串集合的数据结构

字符串中的字母类型通常较少

存储形式

以每一个字符作为一个节点，从根节点到标记节点的一条路径代表一个字符串集合，分支处代表了不同字符集合的相同前缀，在每个单词的结尾处进行标记集合的结束

查找

从根节点开始查找一条路径，判断结尾处是否标记

模板

son[i][26] 节点i的所有可能的子节点的下标，0为空指针，非0则子节点为son[p]节点
cnt[N] 以当前节点结尾的单词的个数
idx 分配空间的最后一个节点的下标

下标是0的点既是根节点，也是其他节点指向的空节点

注意不需要存储字符值，因为存在子节点的下标隐含了值[0,25] -> ['a','z']

注意N为所有可能的字符串的数目承以字符串的最大长度，即最多可能的节点数目

例子

插入 $b, a, ac, a$
son, cnt, idx如图所示，son的每一行都代表一个节点，而节点值隐含在父节点指向它的下标

插入节点

void insert(char[] str) {
    int p = 0; // root节点
    for (int i = 0; str[i] != '\0'; i++) {
        int u = str[i] - 'a'; // a~z -> 0~25
        if (son[p][u] == 0) son[p][u] = ++idx; // 不存在则分配一个节点
        p = son[p][u]; // 移动到下一个节点
    }
    cnt[p]++; // 以p点结尾的单词增加
}

查询字符串的出现次数

void query(char[] str) {
    int p = 0; // root节点
    for (int i = 0; str[i] != '\0'; i++) {
        int u = str[i] - 'a'; // a~z -> 0~25
        if (son[p][u] == 0) return 0; // 不存在此字符直接返回
        p = son[p][u]; // 移动到下一个节点
    }
    return cnt[p]; // 返回出现次数
}