字典树 (单词查找树, Trie, /ˈtraɪ/): 是一种有序树,用于保存关联数组,其中的键通常是字符串。

字典树

时间复杂度:$O(m)$

$m$ 为待操作字符串的长度。

分析

储存多个字符串的朴素方法就是将字符串储存到多个字符数组内,但这样储存比较占用空间,并且查询操作比较费时。

如果字符串的字符种类较少,例如只有小写字母、只有大写字母、只有数字、只有 0/1 这种情况,就可以使用字典树这一种数据结构(也可以使用二进制转化为 0/1 的情况)。

(图片来源:Wikipedia,属于公有领域)

实现方式,与链表比较类似。使用了一个二维数组储存子节点指针,第一维代表节点序号,其中 $0$ 号节点代表头节点,也代表空节点,节点结尾指向空节点。第二维代表字母,若储存小写字母,则需要 $26$ 个,$0\sim25$ 分别代表 $a\sim z$.

代码实现

(以下代码示例储存的为小写字母)

插入

const int MAXN = 1e6 + 10;
int son[MAXN][26], cnt[MAXN], idx;

void insert(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int c = str[i] - 'a';
        if (!son[p][c])
            son[p][c] = ++idx;
        p = son[p][c];
    }
    cnt[p]++;
}

查询

返回待查询字符串的数量。

int query(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int c = str[i] - 'a';
        if (!son[p][c])
            return 0;
        p = son[p][c];
    }
    return cnt[p];
}

标签: 字典树

添加新评论