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 树的扩展情况如下：

1. 插入 "apple"：

   • a -> 新建节点（编号 1）
   • p -> 新建节点（编号 2）
   • p -> 新建节点（编号 3）
   • l -> 新建节点（编号 4）
   • e -> 新建节点（编号 5）

2. 插入 "app"：

   • 由于 "app" 与 "apple" 共享前缀 "app"，只需沿着现有节点移动即可，不创建新节点。

3. 插入 "bat"：

   • b -> 新建节点（编号 6）
   • a -> 新建节点（编号 7）
   • t -> 新建节点（编号 8）

最终，节点 p 的最大编号会达到 8，而不是 26。这是因为每插入一个新字符串，都会动态扩展树的节点数量。

4. 总结

通过对 Trie 树插入和查询操作的讲解，我们可以得出以下结论：

• 节点编号 p 表示当前遍历的节点，不是字符索引。
• 节点数量根据插入的字符串数量动态增长，虽然每个节点的子节点数目被限制为 26，但节点的总数是根据需要不断扩展的，因此节点编号 p 也会随之增长。
• Trie 树是一种高效的字符串存储和检索结构，非常适合前缀匹配和大规模字符串数据处理场景。

如果你在学习算法的过程中遇到类似的疑问或困惑，不妨从基础概念入手，逐步理解数据结构的设计原理。Trie 树作为一个经典的算法问题，值得深入理解与应用。