字典树【Trie】

MarsTraveller · 2024-01-29 18:50:53 · 算法·理论

字典树

字典树（Trie）是一种树形结构。典型应用是用于统计和排序大量的字符串前缀来减少查询时间，最大限度地减少无谓的字符串比较。字典树的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间以达到提高效率的目的。

一、基本结构：

如下是字典树的一个例子：

字典树可以看做一个多叉树，它的根不存储任何数据。

图中的橙色圆圈可以看做一个结束标记（\text{tag[ ]}），表示从根到这里有一个单词。

我们可以很清晰的看出字符串之间的前缀关系。

二、存储方式

我们可以使用二维数组来存储字典树。

为方便举例，我们假定该字典树仅存储小写字母组成的单词（即 26 叉树）。

我们可以认为，每一个节点都有 26 个子节点，分别表示字符 a 到 z，编号从 1 到 26。

我们定义 \text{trie[u][id] = k} 中，u 表示字典树的节点编号，id 表示该节点中编号为 id 的字符（子节点）。显然，k 就应该表示为该子节点的编号（特殊地，当 k=0 时，表示没有该子节点）。

三、插入字符串

以上图为例，我们插入单词 bike。

第一步，插入字符 b，分如下步骤进行（起初，从根节点开始插入。可以认为指针从根节点开始）：

计算 b 的编号为 2。
判断指针当前的节点（根节点）的第 2 位是否存在。即判断 \text{trie[1][2]} 是否等于 0。
若等于 0，说明不存在，需要新建一个子节点，存储 b。即将 \text{trie[1][2]} 赋值为一个新的编号（可以用 tot 表示）。在这里是将该子节点编号赋为 2。
若不等于 0，则不操作（保证字典树的前缀关系）。
进入下一个节点（即将指针更新为 \text{trie[1][2]}，也就进入了子节点）。
重复操作 1-5，直至插入完毕。
打上结束标记。

我们根据操作可以写出如下代码：

void insert(string s)
{
    big pos = 1; // 指针（位置）
    for(big i = 0;i < s.size();i++)
    {
        big id = s[i]-'a'+1; // 获取编号（步骤1）
        if(trie[pos][id] == 0) // 判断是否存在子节点（步骤2）
        {
            trie[pos][id] = ++tot; //不存在，则新建一个点（步骤3）
        }
        pos = trie[pos][id] // 进入子节点（步骤5）
    }
    tag[pos] = 1; // 打结束标记（步骤7）
}

四、查找字符串

与插入相似，只不过需要判断子节点是否存在（即判断 \text{trie[1][2]} 是否等于 0），若等于 0，说明没有该字符串。

在最后，还要看是否被打有结束标记，若没有标记，则同样不成立。

big find(string s)
{
    big pos = 1; // 指针（位置）
    for(big i = 0;i < s.length();i++)
    {
        big id = s[i]-'a'+1;
        if(trie[pos][id] == 0)
        {
            return 0;
        }
        pos = trie[pos][id];
    }
    if(tag[pos] == 0)
    {
        return 0;
    }
    return 1;
}

五、模板与例题

以 P8306【模板】字典树为例，其中用到了一种较为常用的字典树处理方法，用以查询前缀。

我们考虑将一个数组 \text{cnt[ ]}，用以表示有多少字符串中包含该节点，换句话说，就是存储有多少个字符串是以从根到这个节点拼成的字符串为前缀的。

比如，上图中的 2 号节点 b。共有 4 个字符串包含该节点。分别是 bike，bin，bee，beer。显然，以 b 为前缀的字符串数量为 4。

又或者，上图中 3 号节点 i。共有 2 个字符串包含该节点，那么也至少会有 2 个字符串包含该节点的所有祖先节点（根据字典树的前缀结构），在这里是 b。那么以 bi 为前缀的字符串数量就是 2。

计算该数组，我们只需要在插入字符串时将经过的每个节点的 \text{cnt[ ]} 值增加 1 即可。