Yharim Area

Appearance

Trie 树

2021-05-20

简介 ​

Trie 树又名「字典树」，能够像字典一样录入和查询多个字符串。

INFO

不局限于字符串，任何同类型序列都可以用 Trie 数进行维护。

构造 ​

一般我们会用数组保存字符串，可是这么做既浪费空间，查询速度又慢。

cpp
const int N = 4;
const string str[N] = {
    "his", "her", "hello", "this"
};

// 查询 str[] 中是否有字符串 s
bool query(string s) {
    for (int i = 0; i < N; i ++)
        if (str[i] == s)
            return true;
    return false;
}

如果将字符串放在链表里，就会有相当一部分节点可以合并。例如 his，her，hello 的开头都是 h，那么它们可以共享同一个 h 节点。同理，her 和 hello 可以共享 he。

最后，在上方建一个空节点，指向各个字符串的开头，一棵标准的 Trie 树就建好了。空节点使代码实现变得更方便。

节点 ​

Trie 树的节点存储于结构体中：

cpp
const int N = 1e6;
struct Node {
    bool isEnd = false; // 该节点是否为某单词的末尾，默认为 false
    int next[26];       // 该节点的子节点
} trie[N];

按照节点的创建顺序为其编号，令 trie[u] 表示第 u 个建立的节点。trie[u].next['s'] 表示 u 号节点的子节点中，代表字符 s 的节点的编号。

cpp
trie[1].next['d'] = 2
trie[1].next['h'] = 3

在程序中，我们一般用 0 - 25 替换 a - z，数组就只要开到 next[26]。

当然，也有人习惯于用二维数组存储 Trie 树节点。

插入 ​

如何往 Trie 树中插入一个字符串？

本着勤俭节约的精神，能共享的节点就尽量共享。例如要在刚才那棵 Trie 树中插入 thus，并且发现 t，h 可以共享，那么就只要新建 u，s 两个节点。

cpp
const int N = 1e6;
int tot;
struct Node {
    bool isEnd = false;
    int next[26];
} trie[N];

void insert(string str) { // 往 trie 树中插入字符串 str
    int p = 0; // 最上方的空节点编号为 0
    for (int i = 0; i < str.size(); i ++) {
        int ch = str[i] - 'a';
        if (!trie[p].next[ch]) // 如果不能共享，就新建节点
            trie[p].next[ch] = ++ tot;
        p = trie[p].next[ch];
    }
    trie[p].isEnd = true; // 标记字符串结尾
}

查询 ​

查询 Trie 树中是否有某个字符串，只需要从空节点向下搜索即可。

cpp
bool search(string str) { // 查询 trie 树中是否有字符串 str
    int p = 0;
    for (int i = 0; i < str.size(); i ++) {
        int ch = str[i] - 'a';
        if (!trie[p].next[ch])
            return false;
        p = trie[p].next[ch];
    }
    return trie[p].isEnd; // 如果想查询 str 是否为前缀，直接返回 true
}

模板 ​

cpp
const int N = 1e6;
int tot;
struct Node {
    bool isEnd = false;
    int next[26];
} trie[N];

void insert(string str) {
    int p = 0;
    for (int i = 0; i < str.size(); i ++) {
        int ch = str[i] - 'a';
        if (!trie[p].next[ch])
            trie[p].next[ch] = ++ tot;
        p = trie[p].next[ch];
    }
    trie[p].isEnd = true;
}

bool search(string str) {
    int p = 0;
    for (int i = 0; i < str.size(); i ++) {
        int ch = str[i] - 'a';
        if (!trie[p].next[ch])
            return false;
        p = trie[p].next[ch];
    }
    return trie[p].isEnd;
}