Trie 树
Trie 树，亦称前缀树，是一种高效处理字符串的基础数据结构。许多算法问题中，Trie 树因其能快速检索字符串的前缀匹配而备受青睐。
在本文中，我们将从 Trie 树的基本插入与查询操作出发，详解为何节点编号 p 不会被限制在 26 个以内。
1. Trie 树的基本结构
Trie 树通常用于处理一组字符串，每个节点代表一个前缀。Trie 树的每个节点最多有 26 个子节点，分别对应小写字母 a 到 z。
插入操作
以下是 Trie 树的典型插入代码：
void insert(char str[])
{
int p = 0; // 从根节点开始遍历
for (int i = 0; str[i]; i++) // 沿着字符串的每个字符进行遍历
{
int j = str[i] - 'a'; // 将字符映射为 0 ~ 25 的整数
if (!son[p][j]) son[p][j] = ++idx; // 如果该子节点不存在，则创建新节点
p = son[p][j]; // 移动到下一个节点
}
cnt[p]++; // 记录该字符串出现的次数
}
在上述代码中，p 代表当前遍历到的节点编号，而 j = str[i] - 'a' 则将字符映射为相应的索引值，范围为 0 到 25，分别对应 a 到 z 的 26 个字母。
查询操作
查询一个字符串是否存在于 Trie 树中的代码如下：
bool search(char str[])
{
int p = 0; // 从根节点开始
for (int i = 0; str[i]; i++) // 遍历字符串的每个字符
{
int j = str[i] - 'a'; // 计算字符的索引
if (!son[p][j]) return 0;
p = son[p][j]; // 移动到下一个节点
}
return cnt[p];
}
p 是节点编号，不是字符索引
p 是 Trie 树中节点的编号，它表示当前遍历到的节点。虽然每个节点最多有 26 个子节点（对应字母 a 到 z），但 p 的值会随着 Trie 树的扩展而不断增加。p 代表的是节点编号，而不是字符范围。
2. 为什么 p 不会被限制在 26？
很多人可能疑惑，既然每个节点最多有 26 个子节点（分别对应字母 a 到 z），那么为什么 p 的值不会被限制在 26 个以内呢？
关键在于节点数量的动态扩展
Trie 树的每个节点最多有 26 个分支，但节点的总数却不限于 26。不同字符串的前缀可能会产生不同的节点，因此节点数量会根据插入的字符串的数量和内容动态增长。每当插入一个新字符串，如果某个字符的节点不存在，都会创建一个新的节点，并分配一个新的编号。
例如：
- 插入字符串
"apple"时，p将沿着字符路径"a" -> "p" -> "p" -> "l" -> "e"移动，并为每个新字符创建一个新节点。 - 每创建一个新节点时，节点编号
p会递增，而不仅仅是 0 到 25 之间的固定值。 - 因此，随着插入字符串数量的增加，Trie 树中的节点数量可以轻松超过 26，
p也会相应地增大。
3. Trie 树节点扩展的示例
假设我们插入三个不同的字符串："apple"、"app" 和 "bat"。Trie 树的扩展情况如下：
插入
"apple"：a-> 新建节点（编号 1）p-> 新建节点（编号 2）p-> 新建节点（编号 3）l-> 新建节点（编号 4）e-> 新建节点（编号 5）
插入
"app"：- 由于
"app"与"apple"共享前缀"app"，只需沿着现有节点移动即可，不创建新节点。
- 由于
插入
"bat"：b-> 新建节点（编号 6）a-> 新建节点（编号 7）t-> 新建节点（编号 8）
最终，节点 p 的最大编号会达到 8，而不是 26。这是因为每插入一个新字符串，都会动态扩展树的节点数量。
4. 总结
通过对 Trie 树插入和查询操作的讲解，我们可以得出以下结论：
- 节点编号
p表示当前遍历的节点，不是字符索引。 - 节点数量根据插入的字符串数量动态增长，虽然每个节点的子节点数目被限制为 26，但节点的总数是根据需要不断扩展的，因此节点编号
p也会随之增长。 - Trie 树是一种高效的字符串存储和检索结构，非常适合前缀匹配和大规模字符串数据处理场景。
如果你在学习算法的过程中遇到类似的疑问或困惑，不妨从基础概念入手，逐步理解数据结构的设计原理。Trie 树作为一个经典的算法问题，值得深入理解与应用。