字典树
字典树，顾名思义，就是一个像字典一样的树。
—— OI-wiki
普通 Trie
如图：
Trie 用边代表字母，那么从根节点到某个节点的路径表示一个字符串。
Trie 支持的操作有三个：
- 插入字符串
- 查询字符串是否存在
- 删除字符串
Trie 的储存
个人习惯用结构体来表示某种数据结构的节点：
struct Trie{
int ch[26];
bool end_,vis;
}T[inf];
题目的数据范围：\(n\le10^4,s\le50\)。
那么 Trie 中插入的点最多有 \(5\times10^5\)。
所以 inf=5e5+7。
ch 表示子节点，共 26 个（根据题目不同子节点的的个数可能不同），end_ 表示这个点是不是字符串的结尾，vis 表示是不是第一次查找到这个点（某些题中有用到）。
插入
每找到一个节点，如果当前节点没有相应字母所对应的子节点，就新建一个节点作为其节点，直到整个字符串结束，标记一下 end_。
没错就是线段树、平衡树那里的动态开点。
void insert(int now,int i)
{
if(i==len){T[now].end_=1;return;}
if(T[now].ch[a[i]]==0)
T[now].ch[a[i]]=++cnt;
insert(T[now].ch[a[i]],i+1);
}
当然也可以用迭代，但感觉迭代没有递归好理解。
（刚开始学的时候用的迭代，这次复习才弄递归）
void build(char *s)
{
int now=1,i=0,len=strlen(s);
while(i<len)
{
if(trie[now][a[i]]==0)
trie[now][a[i]]=++cnt;
now=trie[now][a[i]],i++;
}
end_[now]=1;
}
接下来的代码将不再展示迭代，因为远古时期的码风是在太丑了。
查询
首先查找此字符串是否存在，如果按找路径找到某个节点为空则不存在。
再看最终节点是否为结束的节点，即有没有 end_ 标记。
最后在看是不是第一次查找到，即有没有 vis 标记。
#define OK 0
#define WRONG 1
#define REPEAT -1
int ask(int now,int i)
{
if(now==0)return WRONG;
if(i==len)
{
if(T[now].end_==0)return WRONG;
if(T[now].vis==1)return REPEAT;
T[now].vis=1;
return OK;
}
return ask(T[now].ch[a[i]],i+1);
}
此处的 define 更不容易出错。
删除
首先说明，上题和大多数题中并没有此操作。
删除的时候分情况讨论：
-
当前节点不是叶子节点。
清除标记即可。
-
当前节点为叶子节点，且根节点到当前节点有且仅有一个标记。
删除整条路径就好。
-
当前节点为叶子节点，且根节点到当前节点不只有一个标记。
从叶子节点删到上一个标记节点。
其实后两种情况差不多，都是从当前节点向上删。
bool pd_ye;
void remove(int now,int i)
{
if(now==0)return;
if(i==len)
{
pd_ye=1;
for(int j=0;j<26;j++)
if(T[now].ch[j])pd_ye=0;
T[now].end_=0,T[now].vis=0;
return;
}
remove(T[now].ch[a[i]],i+1);
if(pd_ye&&T[T[now].ch[a[i]]].end_==0)
T[now].ch[a[i]]=0;
else pd_ye=0;
}
但这样操作可能会被卡空间：不断地插入删除，虽然 Trie 的规模很小，实际的数组花费很大。
和 Fhq_Treap 那里一样，可以弄一个 垃圾场，将删除的数存到垃圾场里，等在动态开点的时候直接去垃圾场里找点。
stack<int>bin;
void insert(int now,int i)
{
if(i==len){T[now].end_=1;return;}
if(T[now].ch[a[i]]==0)
{
if(bin.empty())T[now].ch[a[i]]=++cnt;
else T[now].ch[a[i]]=bin.top(),bin.pop();
}
insert(T[now].ch[a[i]],i+1);
}
bool pd_ye;
void remove(int now,int i)
{
if(now==0)return;
if(i==len)
{
pd_ye=1;
for(int j=0;j<26;j++)
if(T[now].ch[j])pd_ye=0;
T[now].end_=0,T[now].vis=0;
return;
}
remove(T[now].ch[a[i]],i+1);
if(pd_ye&&T[T[now].ch[a[i]]].end_==0)
bin.push(T[now].ch[a[i]]),T[now].ch[a[i]]=0;
else pd_ye=0;
}
应该是对的，但我不是很确定（因为没找到例题），欢迎 dalao hack 和提供正确的代码。
通过这三个操作，就可以在较短的时间里实现插入、查找、删除一个字符串等操作。
01Trie
普通的 Trie 是一种 26 叉树，实际上更常用的是 2 叉树，也就是 01Trie。
（咕咕咕）
可持久化
（不会，待学）
标签：ch,return,复习,Trie,一轮,int,now,节点 From： https://www.cnblogs.com/Zvelig1205/p/16703063.html