Trie单词查找树：快速掌握核心思想与基础用法

创作时间:

作者:

@小白创作中心

Trie单词查找树：快速掌握核心思想与基础用法

引用

CSDN

https://blog.csdn.net/m0_65426912/article/details/140721374

Trie单词查找树（字典树）是一种用于高效存储和查找字符串的数据结构。本文将从基本思想出发，详细讲解其核心操作和数据结构，并通过代码示例帮助读者理解。

1 基本思想

Trie单词查找树（Trie的发音是Try）用于高效地存储和查找字符串，使用集合数据结构，其存储数据在形式上看起来类似树。

我们可以观看下面的视频来迅速理解其操作原理和流程：

算法演示视频

通过视频，我们可以发现其核心操作是插入操作（即存储数据）与查找操作。

2 核心操作分解

在讲解核心操作之前，我们先学习一下实现Trie单词查找树所使用的数据结构。

2.1 数据结构

我首先直接给出数据结构，而后再逐一讲解，如下：

int son[N][X], cnt[N], idx;

son[N][X] 与 idx

N代表了最大字符串长度，X代表了字符种类总数，这个字符的种类总数题目往往会直接告诉我们，所以在实际应用中我们会直接把X处写死为一个常数。

我们存储的基本思路就是将节点使用idx进行编号，一个idx代表一个节点，根节点的idx为0。对于每个节点我们都再使用一个二维数组来维护其所有的子节点信息。

如son[1][1]，代表结点1的1号子节点。假设idx=1对应的节点为字母a，那么在下图中，son[1][1]就代表了字母b(索引从0开始)。

由于Trie单词查找树所涉及的题目往往只需处理有限种类的大写或小写字母，以及数字串。据此，我们完全可以使用一个二维数组来维护所有节点的子节点。很奇妙，很优雅。

cnt[N]

在之前的操作视频中，我们确定曾经存储过这个字符串，是基于对应节点是不是蓝色，而在代码中我们怎么来对应表示呢？当然是我们的惯用思路，使用一个数组来维护其特征信息。也即使用我们此处的cnt数组来维护此字符串是否存在。

继续看到上图，假设子节点b的idx为3，那么对应我们在插入字符串后，会更新cnt[3]的值为1，代表插入了一个字符串，对应为ab。

2.2 插入操作

在插入操作中，我们需要把一个一个的字符串，或者一个数串，插入到我们的查找树中。那么我们自然会需要遍历我们的树，按照什么顺序来遍历呢？

针对我们所需要插入的字符串，逐字符插入即可，我们令字符串为str[N]。我直接给出对应代码：

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

这段代码实现了将字符串逐字符插入到Trie树中。其中，p表示当前节点的索引，u表示当前字符在字符集中的位置。如果当前字符对应的子节点不存在，则创建一个新的子节点。最后，更新cnt[p]表示该字符串的出现次数。

2.3 查找操作

查找操作用于判断一个字符串是否存在于Trie树中。代码如下：

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

这段代码实现了在Trie树中查找字符串。如果在遍历过程中发现某个字符对应的子节点不存在，则返回0表示字符串不存在。最后返回cnt[p]表示该字符串的出现次数。