目录
前缀树介绍
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。常用与拼写检查自动补全等; 是一种查找结构他的存储逻辑类似于哈希表，但是它相对于哈希表来说，限制更多，通用性较差，但是它的功能更加强大，可定制性也更强。 leetcode指路：实现Trie(前缀树)
如图可以查看trie树的基本结构：
与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。(这个是前缀树的精髓，也是难理解的地方，他不用存储某个节点的实际字符，他的对应下标映射出了需要存储的字符！)
一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。
一般情况下，不是所有的节点都有对应的值（他们只是前缀），只有叶子节点和部分内部节点所对应的键才有相关的值。
C++实现
核心思想
单链表:通过Node中封装的Node* next来找下一个连着的节点;
二叉树:通过Node中封装的Node* left 和 Node* right来找左右孩子节点;
前缀树？
因为维护了26个可能的Node*节点，所以跟上面一个道理，只是不能枚举出来了，用了一个Node*arr[26]来维护，恰巧把这个数组的下标设计成了某个字符的种类，就可以达到利用逻辑下标存储一个实际字符的作用了！
前缀树插入示意图
上图中，每经过一个节点，将该节点的pass值加一，将末尾节点的end值加一。通过这种操作记录所有经过的数据记录
前缀树的插入是灵魂所在，搞懂了之后结构就明白了，不管是查找还是删除无非就是类似对链表的相关操作;
前缀树的大致框架
假设只存小写字符:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//26 个小写英文字母
#define NUM 26
class Trie{
private:
Trie* arr[NUM];//多叉树(最大26个分支，因为26个小写字母嘛)
int end; //代表word完整单词的个数，0就是无此单词，只是一个前缀;insert一个单词的时候，这个单词的end首次出现就置为1;之后重复插入就end++;
int pass; //代表以此前缀为公共前缀的节点个数,每次insert的时候会调整;
public:
Trie() {
memset(arr,0,sizeof(arr));//每个新节点的映射数组内容置nullptr
end = 0;
ncount = 0; //初始化时以该映射信息字符为前缀的个数为1(这个字符本身算的1)
}
//插入单词
void Insert(string &x)
{
}
//查找 完全匹配字符串x 的数量
int Find(string &x)
{
}
//查找 前缀为字符串x 的数量
int FindContain(string& x)
{
}
//删除某个单词(前缀)
bool Erase(string &x)
{
}
~Trie()
{
//因为new了26个连续的tire*空间，不要某个节点，不要把它对应给下层准备的26个空间也delete掉 防止内存泄漏
for (int i = 0; i < NUMBER; i++)
{
if (nexts[i]){
delete nexts[i];
}
}
}
};
- 二叉树，父节点之下包含两个节点，分别为左右子节点，分别开辟空间，进行数据存储。
- 前缀树的结构也是类似的，它的每个节点包含两个部分: 值部分和指针部分。
- 它的存储方式为：在一棵树上，从根到子节点，分别存储所有目标数据的每一个下标位置上的数据
- 值部分主要又包含两个数据: 路过该节点的数量为pass， 以该节点为结尾的数量为end。
- 指针部分主要包含它的所有子节点（比如26个小写字母），记为arr
下面的实现给出了四个接口:
Insert插入字符串，给前缀树添加一组数据
其中
Insert方法需要注意插入新单词的过程中，路径所有前缀的个数pass+1
Find查找已存入的完整匹配的字符串个数FindContain查找已存入的前缀匹配的字符串个数Erase从前缀树中擦除一个完整字符串
Erase方法需要注意的是：
- 需Find先检查字符串是否存在；
- pass == 1 时，代表其下没有任何可能存在的字符子串，所以直接将这个节点delete删除即可；
- pass不为1且存在这个字符串，我们把end有效字符串个数-1就行
- 移除节点时，需要提前写好析构函数，将其节点开辟的26个Node*内存全部释放，以免出现内存泄漏;
前缀树插入字符串
另外，下面的功能代码不过多解释，代码注释自行理解，核心要点就是用数组下表映射的方式确定前往哪一条链表，之后的寻找和插入等操作都有点像链表的操作，搞个cur指针向后遍历等;
//插入单词
void Insert(const string &x)
{
int size = x.size();
Node* cur = root;
cur->pass++;//不管insert啥，我们root空节点的pass相当于必须+1，最终这个root->pass可以代表一共insert了几次=-=
for (int i = 0; i<size; i++) {
char index = x[i] - 'a';
//该字符在当前分支下的映射为空，没有那就new
if (cur->arr[index] == nullptr) {
cur->arr[index] = new Node;
}
cur->arr[index]->pass++; //不管 cur->arr[index] 是new的还是本来就有，insert要路过他了，他的pass+1,
cur = cur->arr[index];//同时cur下指过去，进行下一个字符的insert
}
cur->end++;//insert最终将完整字符串个数end+1
}
前缀树查找完整的字符串
//查找 完全匹配字符串 x 的数量 -->end
int Find(const string &x)
{
int size = x.size();
Node* cur = root;
for (int i = 0; i < size; i++) {
char index = x[i] - 'a';
//搜索到某个字符断了，没有这个完整的字符串x 返回0
if (cur->arr[index] == nullptr) return 0;
//没断，继续向下一个字符搜索;
cur = cur->arr[index];
}
return cur -> end;//返回完整字符串x的有效个数end
}
前缀树查找前缀匹配的字符串
//查找 前缀为字符串 x 的数量 -->pass
int FindContain(const string& x)
{
//与Find一模一样的逻辑，只是最后的return 变了，这体现了Node*封装 int end 和int pass的好处了吧
int size = x.size();
Node* cur = root;
for (int i = 0; i < size; i++) {
char index = x[i] - 'a';
if (cur->arr[index] == nullptr) return 0;
cur = cur->arr[index];
}
return cur -> pass;
}
前缀树删除完整字符串
//删掉某个完整单词-以及这个单词后面可能存在的所有路径;（end>1 出现了很多次时，只需要end--一下）
bool Delete(const string &x)
{
if (Find(x) == 0) return false;//压根没这个单词，删除失败;
//有这个单词，我们需要找到他的prev前一个，delete掉他,prev的arr[x]=nullptr!
Node* cur = root;
Node* prev = root;
int size = x.size();
for (int i = 0; i < size; i++) {
char index = x[i]-'a';
//if (cur->arr[index] == nullptr) return false;这句不需要，都过了Find 肯定x每个字符都存在于字典树中
cur->pass--;//别忘了路过的路径都得-1;
prev = cur;
cur = cur->arr[index];
}
if (cur->end==1) {//代表x所在字符串的个数只有1，直接递归delete删掉它 和 他后面的子串
delete cur;//这个delete调析构，我们析构已经写好了，防止内存泄漏;
prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一个字符-'a'] = nullptr!
}
else cur->end--;//end>1 :end--代表这个节点的有效字符串个数-1，end==1 end-- == 0，这个节点的字符有效个数为0了，但是他因为pass>1,暂时保存 后面的不删;
//end>1,那就end有效个数-1就行了;
return true;
}
总结
- 这个字典树的树结构可以根据需求来进行多样式的处理；比如我为了实现设计的功能，每个节点都保存了pass和end俩int方便功能记录和函数内的使用;
- 字典树本质上是牺牲空间，换查找同前缀的字符串提升时间效率的一种措施，但是我们这种每个节点都开26个数组的方式是非常浪费空间的，比如只有一个有效字符下标，其他25个nullptr都浪费了，而且在大量相同的前缀下就是单链表，浪费更严重。
- 这时候我们可以把Node*arr[26]数组换成map<char,Node*>这样搞(每层某一个char只会出现一次，所以char做key没问题)，需要配对啥就insert给红黑树中添加啥,大大节省空间;
所以说这个树没有啥固定玩法，可塑性太强了…这可能也是不刷题的我不常见的愿因？
完整代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//26 个小写英文字母
#define NUM 26
//前缀树节点
class Node {
public:
Node* arr[NUM];//多叉树(最大26个分支，因为26个小写字母嘛)
int end; //代表
int pass; //代表以此前缀为公共前缀的节点个数,每次insert的时候会调整
Node()
{
end = 0;
pass = 0;
memset(arr, 0, sizeof(arr));
}
~Node()
{
//这里有点递归的意思，除了删除当前节点，更重要的是如果当前节点的子节点还有非空。递归delete掉！
for (int i = 0; i < NUM; i++)
{
if (arr[i]!=nullptr) delete arr[i];
}
}
};
//前缀树主体
class Trie{
public:
Node* root = nullptr;
public:
Trie() {
root = new Node;
}
//插入单词
void Insert(const string &x)
{
int size = x.size();
Node* cur = root;
cur->pass++;//不管insert啥，我们root空节点的pass相当于必须+1，最终这个root->pass可以代表一共insert了几次=-=
for (int i = 0; i<size; i++) {
char index = x[i] - 'a';
//该字符在当前分支下的映射为空，没有那就new
if (cur->arr[index] == nullptr) {
cur->arr[index] = new Node;
}
cur->arr[index]->pass++; //不管 cur->arr[index] 是new的还是本来就有，insert要路过他了，他的pass+1,
cur = cur->arr[index];//同时cur下指过去，进行下一个字符的insert
}
cur->end++;//insert最终将完整字符串个数end+1
}
//查找 完全匹配字符串 x 的数量 -->end
int Find(const string &x)
{
int size = x.size();
Node* cur = root;
for (int i = 0; i < size; i++) {
char index = x[i] - 'a';
//搜索到某个字符断了，没有这个完整的字符串x 返回0
if (cur->arr[index] == nullptr) return 0;
//没断，继续向下一个字符搜索;
cur = cur->arr[index];
}
return cur -> end;//返回完整字符串x的有效个数end
}
//查找 前缀为字符串 x 的数量 -->pass
int FindContain(const string& x)
{
//与Find一模一样的逻辑，只是最后的return 变了，这体现了Node*封装 int end 和int pass的好处了吧
int size = x.size();
Node* cur = root;
for (int i = 0; i < size; i++) {
char index = x[i] - 'a';
if (cur->arr[index] == nullptr) return 0;
cur = cur->arr[index];
}
return cur -> pass;
}
//删掉某个完整单词-以及这个单词后面可能存在的所有路径;（end>1 出现了很多次时，只需要end--一下）
bool Delete(const string &x)
{
if (Find(x) == 0) return false;//压根没这个单词，删除失败;
//有这个单词，我们需要找到他的prev前一个，delete掉他,prev的arr[x]=nullptr!
Node* cur = root;
Node* prev = root;
int size = x.size();
for (int i = 0; i < size; i++) {
char index = x[i]-'a';
//if (cur->arr[index] == nullptr) return false;这句不需要，都过了Find 肯定x每个字符都存在于字典树中
cur->pass--;//别忘了路过的路径都得-1;
prev = cur;
cur = cur->arr[index];
}
if (cur->end==1) {//代表x所在字符串的个数只有1，直接递归delete删掉它 和 他后面的子串
delete cur;//这个delete调析构，我们析构已经写好了，防止内存泄漏;
prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一个字符-'a'] = nullptr!
}
else cur->end--;//end>1 :end--代表这个节点的有效字符串个数-1，end==1 end-- == 0，这个节点的字符有效个数为0了，但是他因为pass>1,暂时保存 后面的不删;
//end>1,那就end有效个数-1就行了;
return true;
}
};
