Trie 树

简介 #

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

构造 #

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

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

bool query(string s) { // 查询 str[] 中是否有字符串 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 树的节点存储于结构体中：

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

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

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

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

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

插入 #

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

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

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 树中是否有某个字符串，只需要从空节点向下搜索即可.

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
}

模板 #

结构体

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

二维数组

const int N = 1e6;
int trie[N][26], tot;
bool isEnd[N];

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

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