前缀树原理与代码详解

本文主要是介绍前缀树原理与代码详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前置知识

1. 了解什么是树结构，比如二叉树、多叉树。
2. 了解为什么推荐静态数组的方式实现各种结构。【联想到静态链表，省时间省空间】
3. 知道哈希表怎么用。【$O(1)$复杂度】

前缀树又称为字典树，英文名 $trie$：

每个样本都从头结点开始，根据前缀字符或者前缀数字建出来的一棵大树，就是前缀树。

**前缀树的使用场景：**一般都用在需要信息前缀的场景中。

**前缀树的优点：**利用前缀信息选择树上的分支，可以节省大量的时间。

前缀树的缺点： 前缀树需要大量的空间来存储树上的节点。并且前缀树上是【树枝】表示具体字符（待会看例子你就明白什么意思了）

前缀树的定制： pass,end 等信息。

前缀树的类实现

前缀树Trie类的相关函数：

• struct TrieNode{}; ：前缀树的某个节点。
• class Trie{}；：整个前缀树类对象。
• void insert(string word) ：向前缀树中插入字符串word。
• int serach(string word) ：在前缀树中字符串word出现的次数。
• int prefixNumber(string prefix) {} ：以prefix为开头的字符串的个数（包含出现次数）。
• void erase(string word) {} ：在前缀树中删除字符串word。

前缀树的类实现代码很简单，为节省篇幅，我只给重要代码，其余代码可以在评论区找我讨论。

class Trie {
private:struct TrieNode {int pass;int end;TrieNode* nexts[26];  // next为指针数组，存的是指向子节点的指针//大小为什么是26呢？因为英文字符只有26个，这就是之前提到的“前缀树所需空间与字符种类有关”的原因TrieNode() { //无参pass = 0;end = 0;for (int i = 0; i < 26; i++) {nexts[i] = nullptr;}}TrieNode(int p, int e) { //有pass,endpass = p;end = e;for (int i = 0; i < 26; i++) {nexts[i] = nullptr;}}TrieNode(TrieNode& copyNode) {  // 拷贝构造函数this->pass = copyNode.pass;this->end = copyNode.end;for (int i = 0; i < 26; i++) {this->nexts[i] = copyNode.nexts[i];}}};TrieNode root; //root是最上层一个节点，pass 和 end 都为0。public:Trie() {}  // 构造函数，声明一个前缀树对象时只需要一个无子节点的root即可void insert(string word);int serach(string word);int prefixNumber(string prefix) {}void erase(string word) {}
};

void Trie::insert(string word) {TrieNode temp = root;  // 当前节点for (int i = 0; i < word.size(); i++) {temp.pass++;int path = word[i] - 'a'; //字符相减，本质上是ACSII码相减if (temp.nexts[i] == nullptr) {  // 如果此时的path不在前缀树中，则新建节点temp.nexts[i] = new TrieNode(0, 0);}temp = *temp.nexts[i];}//循环结束时，temp指向word的最后一个字符temp.end++;
}int Trie::serach(string word) { //找word出现了几次，其实就是先找word，//再取word最后一个字符所对应节点的end
// 从根结点开始找TrieNode temp = root;//找的过程其实就是从word[0]开始往下走，看看有没有一直到word[n-1]的分支,最后返回该分支结尾节点的endfor (int i = 0;i < word.size(); i++) {int path = word[i] - 'a';if (temp.nexts[path] == nullptr) {//没有wordreturn 0;}temp = *temp.nexts[path];}return temp.end;
}

但是前缀树用类实现的话，工作效率并不高，接下来我们来看前缀树静态数组实现。

前缀树的静态数组实现

静态数组的优势

为什么提倡使用静态数组来实现前缀树呢，这得益于静态结构比较节约空间。利用动态结构实现的前缀树只适用于单个样例，更换样例之后，之前样例对应的前缀树根本用不了，只能销毁并新消耗一些空间给当前样例，如此反复下去，通过所有样例所需要的空间是巨大的。而静态数组只需要在定义时占用足够的空间，所有样例都可以在这片空间上建立前缀树。

前缀树静态数组实现示例

向前缀树中依次插入字符串“abc”、“ac”和“abb”。我们需要借助一个二维矩阵和两个一维数组：$Trie[n][k]$ (k是字符的种类，在此示例中，k为3)，$pass[n]$，$end[n]$ 以及最关键的空间计数器cnt。

在最初时刻，未插入字符时，$Trie[n][k]$以及$pass[n],end[n]$,cnt的状态如下：

实现代码

我这里先直接给出实际静态数组实现代码：

class Trie {
private://静态空间static const int n = INT_MAX;static const int k = 26; //k表示字符种类个数int trie[n][k];int pass[n];int end[n];int cnt;    //cnt表示申请的空间总数目，其实也就是节点数量
public:Trie() :cnt(0) {memset(trie, 0, sizeof(trie));memset(pass, 0, sizeof(pass));memset(end, 0, sizeof(end));}void build() {cnt = 1; //建树初始便有节点1}void insert(string word) {int cur = 1; //cur指向当前节点pass[cur - 1]++; //pass按照编号进行计数，即节点编号1,2,3,...for (int i = 0;i < word.size();i++) {int path = word[i] - 'a';if (trie[cur][path] == 0) { //无分支则新建分支trie[cur][path] = ++cnt;cur = cnt;pass[cur - 1]++;}else {cur = trie[cur][path]; //trie[cur][path]存储的是path分支节点的编号pass[cur - 1]++;}}end[cur - 1]++;}//查找的原理在类实现中已经讲过：找到最后一个节点的end即可。int search(string word) {int cur = 1;for (int i = 0;i < word.size();i++) {int path = word[i] - 'a';if (trie[cur][path] == 0)   return 0;cur = trie[cur][path];}return end[cur - 1];}int prefixNumber(string word) {int cur = 1;for (int i = 0;i < word.size();i++) {int path = word[i] - 'a';if (trie[cur][path] = 0) return 0;cur = trie[cur][path];}return pass[cur - 1];}void erase(string word) {if (search(word) == 0)   return;int cur = 1;pass[cur - 1]--;for (int i = 0;i < word.size();i++) {int path = word[i] - 'a';cur = trie[cur][path];pass[cur - 1]--;}end[cur - 1]--;}
};

插入字符串“abc”、“ac”和“abb”之后，$Trie[n][k]$以及$pass[n],end[n]$,cnt的状态如下：

这篇关于前缀树原理与代码详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---