【数据结构:前缀树Trie】

前言

本篇介绍数据结构前缀树的理论部分。
代码实现采用动态和类实现。

编程语言:Java/C++， 前面的理论部分主要以Java语言为主。

前缀树介绍和应用

前缀树(Trie Tree),读做Trie[traɪ]。
它是一种典型的多叉树结构。字符集只包括小写字母a~z， 那么它就是一棵26叉树。

应用:比如自动补全功能(根据已有的前缀内容自动弹出后续可能的内容），拼写纠错，词频统计等等功能。

比如一个比较经典的问题， 给定两个字符串数组arr1,arr2。

1. arr2中某个字符串比如abc是否出现在arr1中？
2. 接着1的问题， 如果该字符串出现，那么该字符串出现几次？
3. 第3个问题， 该字符串能作为arr1字符串前缀串吗？若可以，那么出现过几次？比如abc作为arr1字符串数组abcd,abc,abcdf(假设它们是arr1数组的字符串)字符串的前缀串。
4. arr2哪些字符串是作为arr1中某些字符串出现最频繁的前缀串， 返回这些字符串和最大出现次数。

学习完下面的前缀树结构， 就能实现

---

一、前缀树的定义

前缀树的问题和思考

如何理解前缀树这个结构？
前缀树是如何存储字符串信息？
前缀树的节点和边要维护哪些信息？
它的核心API和实现？

前缀树的映射思想

以下假设字符串内部存储的小写字母a~z, 关于更多字符类型， 包括所有ASCII码和Unicode码等实现方式采用哈希表。

前缀树是一种有序树形数据结构。
理解前缀树的关键是前缀树的路径存储字符串信息。
一条边存储字符串的某个字符。
回顾路径的概念: 从根节点出发到某个叶子节点经过的边序列就是一条简单路径。
比如，参考下图。 从根节点沿着t这条边然后再走o边， 这样得到一条序列to.。
这条路径存储了字符串to的信息。
这反映了字符串to存在， 因为前缀树存在一条存储的路径。同理，我们可以从根节点出发沿着t->e->a这条边到达叶子节点。这说明tea字符串也存在。

下面我们对前缀树的边考虑。
边至少要存储3个信息: 边的起点，边的终点，边附带的字符。
好像应该这么设计边比较合适。

事实上， 前缀树不需要对边单独定义。
前缀树只定义了节点Node,没有定义Edge。
为什么呢？
不妨考虑节点如何定义。 当前节点如何知道下一步去往哪些节点呢？字符信息！
比如从根节点出发， 查询字符串to是否出现过， 先从根节点找到并前往t字符的节点， 然后再从该节点找到前往o字符的节点。
如何知道通往对应的字符的节点呢? 用一个数组或者哈希表存储字符->节点的信息。
你可能大概知道如何定义了， 请看下面的java代码。
当前节点+字符信息->下一个节点， 理解这个就明白为什么边不需要定义了， 因为节点的这种关联关系更加方便。

class TrieNode{TrieNode[] next;TrieNode(){//'a'->0//'b'->1//...//'z'->25next = new TrieNode[26];}
}

前缀树用到了映射的思想， 节点内部定义了一个关联数组代替边的功能来查找当前节点去往指定字符的下一个节点。
事实上， 一个字符串对应前缀树的某一条特定路径。字符串是作为前缀树查询的完整的键， 某个节点只是单独存储键的一个字符。

前缀树三大性质

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。

---

二.前缀树节点结构

前面篇幅提过前缀树不需要定义边， 只需要节点带关联数组或者哈希表就可以替代边的功能。
下面对节点完善定义。
前面提出的问题中， 我们需要从前缀树获取某个字符串出现的次数信息， 以及字符串作为前缀的次数。
还是这张图。
比如字符串ten出现了12次。 如何从前缀树中获取呢?
还是那句话，字符串对应前缀树的路径。从根节点出发，沿着t到达节点1·t， 后e走到节点2·te, 最后n走到节点3·ten。
最后一个节点存储end信息， end表示从根节点出发到该节点结尾的字符串个数。
新增一个字符串ten就沿着路径t->te->ten，对末尾的节点3·ten的end++。
同理，若要查询ten字符串出现的次数，只需要从根节点出发走到3·ten读取end信息即可。
因此，一个节点存储end信息记录字符串出现的次数

te是作为tea,ted,ten这三种字符串的前缀串。反映在前缀树中就是这条子路径,被多少条路径覆盖了。对每个节点加入pass属性，记录当前该节点的字符串数量。表示从根节点沿着某条路径到当前节点的字符串作为前缀串的次数。

如下就是前缀树节点的完整定义：

//Java内部类
public static class TrieNode{//记录经过该节点的字符串数量int pass;//记录以该节点结尾的字符串数量int end;//指向子节点的指针数组TrieNode[] next;//HashMap<Character,TrieNode> next 哈希表充当路public TrieNode(){pass = 0;end = 0;//next['a'-'a']->null; 当前节点不存在走向字符a的路。//next['a'-'a']->不是null,是某一个TrieNode。 存在走向字符a的路。//next['z'-'a']:next[25] 有没有走向字符z的路。next = new TrieNode[26];//26个小写字母}}

---

三. 前缀树接口介绍和实现

下面将详细介绍前缀树的四个主要接口函数及其参数功能：

四个·接口API

public void insert(String word);
public int search(String word);
public int startsWith(String pre);
public void delete(String word);

1. insert(String word)

• 功能：将一个字符串 word 插入到前缀树中。若 word 已经存在于前缀树中，则相应的计数器end增加。

• 参数：

  • word：需要插入到前缀树中的字符串。这里由小写字母组成，可以根据需求扩展支持其他字符集。

2. search(String word)

• 功能：查询字符串 word 在前缀树中出现的次数。

• 参数：

  • word：需要查询的字符串。

3. startsWith(String pre)

• 功能：查询以字符串 pre 作为前缀的所有字符串的数量。

• 参数：

  • pre：需要查询的前缀字符串。

• 返回值：

  • int：表示以 pre 为前缀的字符串数量。若没有任何字符串以 pre 为前缀，返回 0。

4. delete(String word)

• 功能：从前缀树中删除一个字符串 word。如果 word 在前缀树中存在多次，则减少其出现次数；如果只存在一次，则完全删除 word，并释放不再需要的节点。

• 参数：

  • word：需要删除的字符串。

• 返回值：

  • int：表示 word 在前缀树中出现的次数。如果 word 不存在，返回 0。

API实现

1. 查询操作search

理解查询操作，那么实现API将毫无难度， 前缀树API之间代码极其相似。
查找核心是找到字符串最后一个字符对应前缀树中节点的end信息。

• 算法流程：
  • 步骤：
  1. 从根节点开始遍历。定义cur=root,cur：循环变量。
  2. 对于字符串 word 中的每一个字符，计算其在子节点数组中的索引。
  3. 检查当前节点的对应子节点是否存在：
     • 如果不存在，说明 word 不在前缀树中，返回 0。
     • 如果存在，移动到该子节点。
  4. 遍历完所有字符后，返回最后一个节点的 end 计数，表示 word 出现的次数。
• Java代码实现：

/**** @param word 在前缀树中查询word字符串出现了几次* @return word在前缀树中出现的次数。*/public int search(String word){if(word==null) return 0;char[] s = word.toCharArray();TrieNode cur = root;for(int i=0,index;i<s.length;i++){index = s[i]-'a';if(cur.next[index]==null){return 0;}cur = cur.next[index];}return cur.end;}

2. 插入操作insert

插入操作对于循环的处理与查找相同。
但需注意这里是新增字符串， 每经过一个节点都要对其pass进行自增。
还需注意字符串可能是初次添加进前缀树， 对于不存在的路，要创建新节点。

• 详细说明：

  • 步骤：
    1. 从根节点开始遍历。定义cur=root,cur：循环变量。
    2. 对于字符串 word 中的每一个字符，计算其在子节点数组中的索引（例如，'a' 对应索引 0，'b' 对应索引 1，以此类推）。
    3. 检查当前节点的对应子节点是否存在：
       • 如果不存在，则创建一个新的子节点。
       • 如果存在，直接移动到该子节点。
    4. 每访问一个子节点，增加该节点的 pass 计数，表示有一个字符串经过该节点。
    5. 最后一个字符对应的节点，增加其 end 计数，表示有一个字符串以该节点结尾。

• Java代码实现：

        public void insert(String word){if(word==null) return ;char[] s = word.toCharArray();TrieNode cur = root;cur.pass++;for(int i=0,index;i<s.length;i++){index = s[i] - 'a';if(cur.next[index]==null){cur.next[index] = new TrieNode();}cur = cur.next[index];cur.pass++;}cur.end++;}

• 举例

  //假设封装好一个前缀树类TrieTree
  TrieTree trie = new TrieTree();
  trie.insert("apple");
  trie.insert("app");
  

以下是创建路和不创建路只增加pass,end的例子。

• 插入 "apple" 时，会依次创建节点 a -> p -> p -> l -> e，并相应增加 pass 和 end 计数。
• 插入 "app" 时，节点 a、p、p 已存在，只需增加相应的 pass 和 end 计数。

查询前缀startsWith

查询前缀串与查询字符串逻辑完全相同，唯一区别在于查询前缀最后读取pass信息， 并非end信息。

• 详细说明：

  • 步骤：
    1. 从根节点开始遍历。定义cur=root,cur：循环变量。
    2. 对于前缀 pre 中的每一个字符，计算其在子节点数组中的索引。
    3. 检查当前节点的对应子节点是否存在：
       • 若不存在，则说明没有字符串以 pre 为前缀，返回 0。
       • 若存在，移动到该子节点。
    4. 遍历完所有字符后，返回最后一个节点的 pass 计数，表示有多少个字符串经过该节点，即以 pre 为前缀的字符串数量。

• Java代码实现

		/*** @apiNote 查询前缀树中以pre为前缀的字符串数目。* @param pre 前缀串* @return 以pre前缀的字符串数目*/public int startsWith(String pre){if(pre==null) return 0;char[] s = pre.toCharArray();TrieNode cur = root;for(int i=0,index;i<s.length;i++){index = s[i]-'a';if(cur.next[index]==null){return 0;}cur = cur.next[index];}return cur.pass;}

• 示例：

  int prefixCount = trie.startsWith("ap"); // 返回 2 ("apple" 和 "app")
  prefixCount = trie.startsWith("app");    // 返回 2 ("apple" 和 "app")
  prefixCount = trie.startsWith("ban");    // 返回 0
  

删除函数delete

删除函数实现的注意事项。
先做查询! 字符串存在则执行后面的删除。
根据存在的字符串出现的个数， 又分两种情况。

1. 沿途减少计数pass,最末尾字符减少end.
2. 在1的基础上，出现pass为0的情况， 意味着当前节点开始后续的节点都无效了。需要释放(C++手动管理内存，Java直接置空交给JVM处理）。

C++代码会解释如何手动释放不必要节点， 参考下文C++实现。

• 详细说明：

  • 步骤：
    1. 查询存在性：首先调用 search(word) 方法检查 word 是否存在于前缀树中。若不存在，直接返回，删除无效！
    2. 遍历减少计数：
       • 根节点开始，依次遍历 word 中的每一个字符。
       • 对于每一个字符，计算其在子节点数组中的索引。
       • 移动到对应的子节点，并减少该节点的 pass 计数。
    3. 减少 end 计数：在最后一个字符对应的节点，减少其 end 计数，表示 word 出现次数减少。
    4. 删除pass为0及以后的节点：
       • 从后往前遍历 word 中的字符，检查每个节点的 pass 计数。
       • 如果某个节点的 pass 计数降为 0，表示没有其他字符串经过该节点，可以删除该节点并将其父节点对应的指针设为 null(Java)。
       • 继续向前检查，直到遇到 pass 不为 0 的节点为止。

• Java代码实现：

 /**** @param word 前缀树中删除的字符串word* 如果字符串word不存在什么也不做* 若字符串word不止一个， 那么减少一次词频。* 若删除导致路径不存在了，那么释放节点。*/public void delete(String word){if(search(word)==0) return;//删除的word在前缀树中不存在。TrieNode cur = root;cur.pass--;char[] s = word.toCharArray();for(int i=0,index=0;i<s.length;i++){index = s[i] - 'a';if(--cur.next[index].pass==0){cur.next[index] = null;//JVM会处理return ;}cur = cur.next[index];}cur.end--;}

• 示例：

  trie.insert("apple");
  trie.insert("apple");
  trie.insert("app");trie.delete("apple");
  int count = trie.search("apple"); // 返回 1trie.delete("apple");
  count = trie.search("apple");     // 返回 0trie.delete("app");
  count = trie.search("app");       // 返回 0
  

  • 在上述示例中，"apple" 被插入了两次，删除一次后，"apple" 的出现次数减少为 1。
  • 再次删除 "apple" 后，"apple" 不再存在于前缀树中，节点被删除。
  • 删除 "app" 后，"app" 也被完全移除。

四. Java代码完整实现

节点类和前缀树类是两个内部类，自行改写。

package Code01_TrieTree;public class Code01_TrieTree {public static class TrieNode{//记录经过该节点的字符串数量int pass;//记录以该节点结尾的字符串数量int end;//指向子节点的指针数组TrieNode[] next;//HashMap<Character,TrieNode> next 哈希表充当路public TrieNode(){pass = 0;end = 0;//next['a'-'a']->null; 当前节点不存在走向字符a的路。//next['a'-'a']->不是null,是某一个TrieNode。 存在走向字符a的路。//next['z'-'a']:next[25] 有没有走向字符z的路。next = new TrieNode[26];//26个小写字母}}public static class Trie{private TrieNode root;public Trie(){root = new TrieNode();}public void insert(String word){if(word==null) return ;char[] s = word.toCharArray();TrieNode cur = root;cur.pass++;for(int i=0,index;i<s.length;i++){index = s[i] - 'a';if(cur.next[index]==null){cur.next[index] = new TrieNode();}cur = cur.next[index];cur.pass++;}cur.end++;}/**** @param word 在前缀树中查询word字符串出现了几次* @return word在前缀树中出现的次数。*/public int search(String word){if(word==null) return 0;char[] s = word.toCharArray();TrieNode cur = root;for(int i=0,index;i<s.length;i++){index = s[i]-'a';if(cur.next[index]==null){return 0;}cur = cur.next[index];}return cur.end;}/*** @apiNote 查询前缀树中以pre为前缀的字符串数目。* @param pre 前缀串* @return 以pre前缀的字符串数目*/public int startsWith(String pre){if(pre==null) return 0;char[] s = pre.toCharArray();TrieNode cur = root;for(int i=0,index;i<s.length;i++){index = s[i]-'a';if(cur.next[index]==null){return 0;}cur = cur.next[index];}return cur.pass;}/*** @param word 前缀树中删除的字符串word*             如果字符串word不存在什么也不做*             若字符串word不止一个， 那么减少一次词频。*             若删除导致路径不存在了，那么释放节点。*/public void delete(String word) {if (search(word) == 0) return;//删除的word在前缀树中不存在。TrieNode cur = root;cur.pass--;char[] s = word.toCharArray();for (int i = 0, index = 0; i < s.length; i++) {index = s[i] - 'a';if (--cur.next[index].pass == 0) {cur.next[index] = null;//JVM会处理return;}cur = cur.next[index];}cur.end--;}}
}

五、前缀树类模板的两道题

其它的测试链接要用静态数组的方式实现， 将在算法篇的前缀树说明。
以下是来自leetcode的两道前缀树类模板的题型
测试链接:
前缀树I
前缀树II

前缀树I

直接改写一下部分方法的返回类型和返回值即可。

class Trie {public static class TrieNode {int pass;int end;TrieNode[] next;// HashMap<Character,TrieNode> next 哈希表充当路public TrieNode() {pass = 0;end = 0;// next['a'-'a']->null; 当前节点不存在走向字符a的路。// next['a'-'a']->不是null,是某一个TrieNode。 存在走向字符a的路。// next['z'-'a']:next[25] 有没有走向字符z的路。next = new TrieNode[26];// 26个小写字母}}private TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {if (word == null)return;char[] s = word.toCharArray();TrieNode cur = root;cur.pass++;for (int i = 0, index; i < s.length; i++) {index = s[i] - 'a';if (cur.next[index] == null) {cur.next[index] = new TrieNode();}cur = cur.next[index];cur.pass++;}cur.end++;}/**** @param word 在前缀树中查询word字符串出现了几次* @return word在前缀树中出现的次数。*/public boolean search(String word) {if (word == null)return false;char[] s = word.toCharArray();TrieNode cur = root;for (int i = 0, index; i < s.length; i++) {index = s[i] - 'a';if (cur.next[index] == null) {return false;}cur = cur.next[index];}return cur.end!=0;}/*** @apiNote 查询前缀树中以pre为前缀的字符串数目。* @param pre 前缀串* @return 以pre前缀的字符串数目*/public boolean startsWith(String pre) {if (pre == null)return false;char[] s = pre.toCharArray();TrieNode cur = root;for (int i = 0, index; i < s.length; i++) {index = s[i] - 'a';if (cur.next[index] == null) {return false;}cur = cur.next[index];}return true;}
}

---

前缀树II

改个方法名， 提交一下。 本题是会员题。
提供题目所给的示例一，自行对照。非会员的朋友们可以参考一下。

输入
[“Trie”, “insert”, “insert”, “countWordsEqualTo”, “countWordsStartingWith”, “erase”, “countWordsEqualTo”, “countWordsStartingWith”, “erase”, “countWordsStartingWith”]
[[], [“apple”], [“apple”], [“apple”], [“app”], [“apple”], [“apple”], [“app”], [“apple”], [“app”]]
输出
[null, null, null, 2, 2, null, 1, 1, null, 0]
解释
Trie trie = new Trie();
trie.insert(“apple”); // 插入 “apple”。
trie.insert(“apple”); // 插入另一个 “apple”。
trie.countWordsEqualTo(“apple”); // 有两个 “apple” 实例，所以返回 2。
trie.countWordsStartingWith(“app”); // “app” 是 “apple” 的前缀，所以返回 2。
trie.erase(“apple”); // 移除一个 “apple”。
trie.countWordsEqualTo(“apple”); // 现在只有一个 “apple” 实例，所以返回 1。
trie.countWordsStartingWith(“app”); // 返回 1
trie.erase(“apple”); // 移除 “apple”。现在前缀树是空的。
trie.countWordsStartingWith(“app”); // 返回 0

class Trie {class TrieNode {public int pass;public int end;public TrieNode[] nexts;public TrieNode() {pass = 0;end = 0;nexts = new TrieNode[26];}}private TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {TrieNode node = root;node.pass++;for (int i = 0, path; i < word.length(); i++) { // 从左往右遍历字符path = word.charAt(i) - 'a'; // 由字符，对应成走向哪条路if (node.nexts[path] == null) {node.nexts[path] = new TrieNode();}node = node.nexts[path];node.pass++;}node.end++;}// 如果之前word插入过前缀树，那么此时删掉一次// 如果之前word没有插入过前缀树，那么什么也不做public void erase(String word) {if (countWordsEqualTo(word) > 0) {TrieNode node = root;node.pass--;for (int i = 0, path; i < word.length(); i++) {path = word.charAt(i) - 'a';if (--node.nexts[path].pass == 0) {node.nexts[path] = null;return;}node = node.nexts[path];}node.end--;}}// 查询前缀树里，word单词出现了几次public int countWordsEqualTo(String word) {TrieNode node = root;for (int i = 0, path; i < word.length(); i++) {path = word.charAt(i) - 'a';if (node.nexts[path] == null) {return 0;}node = node.nexts[path];}return node.end;}// 查询前缀树里，有多少单词以pre做前缀public int countWordsStartingWith(String pre) {TrieNode node = root;for (int i = 0, path; i < pre.length(); i++) {path = pre.charAt(i) - 'a';if (node.nexts[path] == null) {return 0;}node = node.nexts[path];}return node.pass;}}

C++完整实现(deleteNode管理内存)

C++earse函数需要释放无效的节点。
思路:
用vector收集路径的所有节点的地址， 然后遍历vector删除所有pass==0的节点。

 // 删除一个单词void erase(const string& word) {if (countWordsEqualTo(word) == 0) return; // 单词不存在，无法删除Node* node = root;node->pass--; // 根节点的pass减少// 记录遍历路径上的节点，用于可能的回溯删除vector<Node*> path;path.push_back(node);for (char ch : word) {int index = ch - 'a';Node* nextNode = node->nexts[index];nextNode->pass--;path.push_back(nextNode);node = nextNode;}node->end--; // 单词结尾计数减少// 从后向前检查是否需要删除节点for (int i = word.size(); i >= 1; --i) {Node* cur = path[i];if (cur->pass == 0) {// 当前节点的pass为0，删除该节点Node* p = path[i - 1];int index = word[i - 1] - 'a';delete p->nexts[index];p->nexts[index] = nullptr;} else {// 当前节点的pass不为0，其他单词仍在使用该节点break;}}}

---

完整代码

class Trie {
private:// TrieNode 类，表示 Trie 中的每个节点class TrieNode {public:int pass;  // 经过该节点的单词数int end;   // 以该节点为结尾的单词数vector<TrieNode*> nexts;  // 子节点，大小为 26，对应 'a' 到 'z'TrieNode() : pass(0), end(0), nexts(26, nullptr) {}// 析构函数，递归删除子节点~TrieNode() {for (int i = 0; i < 26; ++i) {if (nexts[i] != nullptr) {delete nexts[i];nexts[i] = nullptr;}}}};typedef TrieNode Node;TrieNode* root;  // Trie 的根节点public:// 构造函数，初始化 TrieTrie() {root = new TrieNode();}// 析构函数~Trie() {delete root;}// 插入一个单词void insert(const string& word) {Node* node = root;node->pass++;  // 根节点的 pass 加 1for (char c : word) {int path = c - 'a';  // 计算字符对应的索引（0 到 25）if (node->nexts[path] == nullptr) {node->nexts[path] = new TrieNode();  // 如果该路径没有节点，则创建新节点}node = node->nexts[path];node->pass++;  // 经过该节点的单词数加 1}node->end++;  // 单词的结束节点，end 加 1}// 删除一个单词void erase(const string& word) {if (countWordsEqualTo(word) == 0) return; // 单词不存在，无法删除Node* node = root;node->pass--; // 根节点的pass减少// 记录遍历路径上的节点，用于可能的回溯删除vector<Node*> path;path.push_back(node);for (char ch : word) {int index = ch - 'a';Node* nextNode = node->nexts[index];nextNode->pass--;path.push_back(nextNode);node = nextNode;}node->end--; // 单词结尾计数减少// 从后向前检查是否需要删除节点for (int i = word.size(); i >= 1; --i) {Node* cur = path[i];if (cur->pass == 0) {// 当前节点的pass为0，删除该节点Node* p = path[i - 1];int index = word[i - 1] - 'a';delete p->nexts[index];p->nexts[index] = nullptr;} else {// 当前节点的pass不为0，其他单词仍在使用该节点break;}}}// 查询前缀树中，单词出现的次数int countWordsEqualTo(const string& word) {Node* node = root;for(int i=0,path;i<word.size();i++){path=word[i]-'a';if(node->nexts[path]==nullptr){return 0;}node = node->nexts[path];}return node->end;}// 查询前缀树中，有多少单词以指定前缀开始int countWordsStartingWith(const string& prefix) {Node* node = root;for (char c : prefix) {int path = c - 'a';  // 计算字符对应的索引if (node->nexts[path] == nullptr) {return 0;  // 如果没有该前缀的路径，返回 0}node = node->nexts[path];}return node->pass;  // 返回以该前缀开始的单词数量}
};

总结

前缀树是一个学习起来非常容易的树。
理论很简单， 明白节点的定义的。API实现想明白查询操作的写法，也是一通百通。
前缀树的数据结构和类模板实现， 到此结束。
有需要补充的内容，笔者会更新此篇内容的。

后续会更新算法篇的前缀树。