当前位置：首页 > news >正文

【数据结构】Trie字典树（前缀树）— 数组实现

news 2025/1/3 2:43:22

学习视频推荐：b站上有很多优秀的讲解视频，大家可以自行搜索。这里推荐两个：

1、学习什么是字典树，了解字典树的插入和查找的过程：【数据结构 10】Trie｜前缀树｜字典树_哔哩哔哩_bilibili；

2、学习字典树代码：【C++】字典树Trie+代码数据结构_哔哩哔哩_bilibili

博客推荐：【数据结构】字典树TrieTree图文详解-CSDN博客

题目推荐： 208. 实现 Trie (前缀树) - 力扣（LeetCode）

在学习之前，博主还是建议大家至少看完以上推荐的学习视频。up主讲解的非常清晰。本篇博客主要讲述代码实现的具体过程和注意事项。

什么是字典树？

字典树的结构

字典树的主要操作

插入（Insertion）

查找（Search）

前缀匹配（Prefix Matching）

完整代码：

字典树的作用

字典树的优缺点

什么是字典树？

字典树（Trie），又称前缀树或单词查找树，是一种树形数据结构。字典树的特点是每个节点代表一个字符，从根节点到叶子节点的路径表示一个完整的字符串（或单词）。字典树主要用于高效地存储和检索字符串集合。

字典树的核心思想是通过共享字符前缀来减少存储空间和提高查询效率。例如，如果多个字符串共享相同的前缀（如 “cat” 和 “car” 共享 “ca”），那么在字典树中，这些前缀只会存储一次。

假设插入的顺序为：“cat”，“dog”，“door”，“deer”，“pan”，“panda”。就会形成如下字典树。

可见当两个不同的单词拥有共同前缀时，字典树可以显著的减少存储空间，并能高效查找单词。

字典树的结构

根节点：字典树的根节点通常为空或代表一个特殊标记（如空字符）。
节点：每个节点代表一个字符，并且包含指向子节点的指针（通常是一个数组或哈希表），用于存储下一个字符。
结束标记：每个单词的结尾需要一个特殊标记（如布尔值 isEndOfWord），用于表示从根节点到当前节点的路径是有效的字符串。

对于树这种数据结构，我们通常可以采用链式结构和数组模拟实现逻辑上的树结构这两种方式来实现。这里我们主要介绍使用数组模拟实现字典树，以及代码中需要的注意事项。

字典树类的设计：

constexpr int _capacity = 1e5 + 1;class Trie {
private:int trie[_capacity][26]; // 使用数组模拟树(空间换时间)int end[_capacity]; // 字符串末尾标记int _len; // 当前 trie 的节点个数public:Trie() : _len(0) {// 将 trie 数组的所有元素初始化为 -1，表示所有节点的子节点都不存在。memset(trie, -1, sizeof(trie));// 将 end 数组的所有元素初始化为 0，表示所有节点都不是单词的结束位置。memset(end, 0, sizeof(end));}void insert(const string& word); // 插入字符串（通常是既定单词）bool search(const string& word); // 查找字典树中是否包含word字符串bool startsWith(const string& prefix); // 寻找字典树中是否有前缀prefix
};

成员变量

int trie[_capacity][26]：

二维数组，用于模拟前缀树的结构。
trie[i][j]表示与 i 所代表的字符相连接的字符 j 在该字典树中的索引！
i 是当前节点的索引，j 是字符 'a' 到 'z' 的映射值（范围是 0 到 25）。
如果 trie[i][j] 为 -1，表示节点 i 没有以第 j 个字符为子节点的前缀。

【建议看完代码再来看这一段】

注意：一定不要将trie当作一个普通的二维数组看待，它是一颗逻辑上的树，我们对它的操作就是为了确保它逻辑上的正确性。对于trie[i][j]我们只需要关心索引 i 代表什么，索引 j 代表什么，trie[i][j]的值代表什么。

例如：当我们增加或者查找一个字符串时，我们会从字典树的根节点开始查找。那么i就表示当前节点的索引，j就表示与当前节点相连的字符。那么trie[i][j]就表示与 i 所代表的字符相连接的字符 j 在该字典树中的索引！

举个例子：假设现在字典树中有一个字符串“cat”，那么会是这样的：

当新插入一个字符时_len的大小一定是在变化的。因此我们将_len的值作为标识与当前节点字符所连接的可以构成前缀的字符的“唯一索引标识”。

【注意：插入字符并不是类似于链式树中的插入节点，例如：为trie[pos]['c' - 'a']赋值字符'c'的索引值表示字符'c'已经与索引 pos 表示的字符形成了一个字符串前缀】。

1. 插入字符 'c'

从根节点开始，根节点的索引为 0（pos = 0）。
检查 trie[0][2]（因为 'c' - 'a' = 2）是否为空。
如果为空，说明字符 'c' 还没有被插入，我们需要为它分配一个新的索引（_len + 1）。
更新 trie[0][2] = _len + 1，表示字符 'c' 与根节点相连，并且它的索引是 _len + 1。

2. 插入字符 'a'

将 pos 更新为字符 'c' 的索引，即 pos = trie[0][2]。
检查 trie[pos][0]（因为 'a' - 'a' = 0）是否为空。
如果为空，说明字符 'a' 还没有被插入，需要为它分配一个新的索引。
更新 trie[pos][0] = _len + 1，表示字符 'a' 与字符 'c' 相连，并且它的索引是 _len + 1。

3. 插入字符 't'

将 pos 更新为字符 'a' 的索引，即 pos = trie[pos][0]。
检查 trie[pos][19]（因为 't' - 'a' = 19）是否为空。
如果为空，说明字符 't' 还没有被插入，需要为它分配一个新的索引。
更新 trie[pos][19] = _len + 1，表示字符 't' 与字符 'a' 相连，并且它的索引是 _len + 1。
由于 't' 是单词 "cat" 的结尾字符，我们需要标记它为结束字符。通常通过一个额外的数组 end[] 来标记：
更新 end[pos] = 1，表示从根节点到当前节点 pos 的路径是一个完整的单词。

但需要注意't'是既定字符串“cat”的结尾字符，所以我们需要将该字符't'所对应的索引位设置为既定字符串结束位，即end[pos] = 1。那么为什么不是end['t' - 'a'] = 1呢？设想一下，假如字符树状态如下：

可见，同样是字符't'，他们作为结束位的字符串是不同的，所以对应的索引值一定是不同的！！！使用pos作为代表字符的结束位可以恰当的表示字典树中的该前缀是否是一个既定的完整字符串。

因此：使用 end[pos]可以明确地标记当前节点的索引 pos 是否是某个字符串的结尾。即使多个字符串共享相同的前缀，只要它们的结尾节点不同，就可以通过 end[pos] 正确标记。

int end[_capacity]：

一维数组，用于标记某个节点是否是一个单词的结束位置。
end[i] 表示索引 i代表的字符 是否是一个单词的结束位置，1 表示是，0 表示不是。

int _len：

用于记录当前 trie 中的节点个数。初始值为 0，表示没有节点。
同时_len也同时作为标记字典树中每个单词的唯一索引（在代码中体现），因为当字典树中新增一个单词时，_len的值就会+1。所以使用_len的值作为trie[_capacity][26]的值不仅能准确的标识字典树中每一个字符所处于的索引位置，还保证了索引与不同节点的一一对应。

字典树的主要操作

插入（Insertion）

将一个字符串插入到字典树中。
从根节点开始，逐个字符向下查找或创建节点。
如果字符不存在，则创建新节点；如果存在，则继续查找下一个字符。
在字符串的最后一个字符节点上标记该节点是一个既定字符串的结尾字符。

void insert(const std::string& word) {int pos = 0;  // 从根节点开始for (char c : word) {int index = c - 'a';  // 将字符转换为 0-25 的索引if (trie[pos][index] == -1) {  // 如果当前字符对应的子节点不存在trie[pos][index] = ++_len;  // 创建新节点，并将新节点索引赋值给 trie[pos][index]}pos = trie[pos][index];  // 更新当前节点位置为新节点}end[pos] = 1;  // 标记当前节点为单词的结束位置
}

查找（Search）

检查字典树中是否存在指定的字符串。
从根节点开始，逐个字符向下查找。
如果所有字符都存在且最后一个字符的标记位置，则表示字符串存在。

bool search(const std::string& word) {int pos = 0;  // 从根节点开始for (char c : word) {int index = c - 'a';  // 将字符转换为 0-25 的索引if (trie[pos][index] == -1) {  // 如果当前字符对应的子节点不存在return false;  // 单词不存在}pos = trie[pos][index];  // 更新当前节点位置为子节点}return end[pos] == 1;  // 检查当前节点是否是单词的结束位置
}

前缀匹配（Prefix Matching）

查找以指定前缀开头的所有字符串。
从根节点开始，逐个字符向下查找前缀。
如果前缀存在，则继续从该节点开始递归或迭代查找所有子节点。

bool startsWith(const std::string& prefix) {int pos = 0;  // 从根节点开始for (char c : prefix) {int index = c - 'a';  // 将字符转换为 0-25 的索引if (trie[pos][index] == -1) {  // 如果当前字符对应的子节点不存在return false;  // 前缀不存在}pos = trie[pos][index];  // 更新当前节点位置为子节点}return true;  // 前缀存在
}

在前缀查找中，end 数组不用于判断，只需要检查前缀的所有字符是否都能在 trie 中找到对应的子节点。

完整代码：

#include <cstring>
#include <string>using namespace std;constexpr int _capacity = 1e5 + 1;
class Trie {
private:int trie[_capacity][26]; // 使用数组模拟树(空间换时间)int end[_capacity]; // 字符串末尾标记int _len; // 当前 trie 的节点个数public:Trie() : _len(0) {// 将 trie 数组的所有元素初始化为 -1，表示所有节点的子节点都不存在。memset(trie, -1, sizeof(trie));// 将 end 数组的所有元素初始化为 0，表示所有节点都不是单词的结束位置。memset(end, 0, sizeof(end));}void insert(const string& word)// 插入字符串（通常是既定单词）{int pos = 0;  // 从根节点开始for (char c : word) {int index = c - 'a';  // 将字符转换为 0-25 的索引if (trie[pos][index] == -1) {  // 如果当前字符对应的子节点不存在trie[pos][index] = ++_len;  // 创建新节点，并将新节点索引赋值给 trie[pos][index]}pos = trie[pos][index];  // 更新当前节点位置为新节点}end[pos] = 1;  // 标记当前节点为单词的结束位置}bool search(const string& word) // 查找字典树中是否包含word字符串{int pos = 0;  // 从根节点开始for (char c : word) {int index = c - 'a';  // 将字符转换为 0-25 的索引if (trie[pos][index] == -1) {  // 如果当前字符对应的子节点不存在return false;  // 单词不存在}pos = trie[pos][index];  // 更新当前节点位置为子节点}return end[pos] == 1;  // 检查当前节点是否是单词的结束位置}bool startsWith(const string& prefix) // 寻找字典树中是否有前缀prefix{int pos = 0;  // 从根节点开始for (char c : prefix) {int index = c - 'a';  // 将字符转换为 0-25 的索引if (trie[pos][index] == -1) {  // 如果当前字符对应的子节点不存在return false;  // 前缀不存在}pos = trie[pos][index];  // 更新当前节点位置为子节点}return true;  // 前缀存在}
};