【学习笔记】带你从0开始学习 01Trie
01Trie
Section 1：普通 Trie
Section 1.1 什么是 Trie
Trie 树，即字典树，是一种树形结构。典型应用是用于统计和排序大量的字符串前缀来减少查询时间，最大限度地减少无谓的字符串比较。
Section 1.2 如何实现
具体地说，对于每个结点，我们要保存几个信息：
ch[26]，保存此字符的下一个字符（\(a\sim z\)）的存储地址（没有为 \(0\)）。cnt，保存此节点被经过了多少次。
对于整个 Trie 树，我们还要额外保存
Tcnt，为节点数。Endp[]，表示的是这个字符串是否以这个下标结尾（如果只是看是否是前缀，则不需要此数组）。
几个操作
insert：往 Trie 树里插入一个字符串。
具体实现：把字符串里的字符扫描一遍，设当前字符为 \(s\)，如果 ch[s-'a'] 不等于 \(0\)，跳转到 ch[s-'a'] 的存储下标。否则把 ch[s-'a'] 设为树的节点数加一，然后跳转。跳转时把当前节点的 \(cnt\) 加一。
跳到最后把当前节点 \(Endp\) 设为一。
find：查询 Trie 里是否有这个字符串。
具体实现：根据每个字符一个一个跳。
如果跳的时候 \(cnt=0\)，说明没有。
如果跳到最后，有，但是 \(Endp_{nowNode}=0\) 即并不是以这个字符结尾的，说明没有。
否则有这个字符串，返回 true。
Section 1.3 代码实现
(只给出基础的插入和查询出现次数)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=3000005;
struct Trie{
int T[N][63],Tsiz,Endp[N];
void init(){
for(int i=0;i<=Tsiz;i++) for(int j=0;j<=62;j++) T[i][j]=0;
for(int i=1;i<=Tsiz;i++) Endp[i]=0;
Tsiz=0;
}
int gethash(char ch){
if(islower(ch)) return ch-'a';
if(isupper(ch)) return ch-'A'+26;
if(isdigit(ch)) return ch-'0'+26+26;
}
void insert(string s){
int rt=0,len=s.length();
for(int i=0;i<len;i++){
int x=gethash(s[i]);
if(!T[rt][x]) T[rt][x]=++Tsiz;
rt=T[rt][x];
}
Endp[rt]++;
}
int find(string s){
int rt=0,len=s.length();
for(int i=0;i<len;i++){
int x=gethash(s[i]);
if(!T[rt][x]) return 0;
rt=T[rt][x];
}
return Endp[rt];
}
}trie;
int T,n,q;
int main(){
trie.init();
cin>>n>>q;
string s;
for(int i=1;i<=n;i++){
cin>>s;
trie.insert(s);
}
for(int i=1;i<=q;i++){
cin>>s;
cout<<trie.find(s)<<'\n';
}
}
Section 1.4 例题实现
（使用以上代码无法通过此题，请写 \(cnt\) 维护前缀）
Section 2：01Trie
Section 2.1 什么是 01Trie?
和普通 Trie 相似，但是每个节点只有两个值：\(0/1\)。
从根节点至下的一条路径保存着一个正整数从高到低的二进制位。
如下图：
中序遍历结果为（忽略根节点）： \(00\ 01\ 10\ 11\)
我们会发现几点有趣的性质：
- 01Trie 是一棵二叉树，每个节点的左儿子为 \(0\)，右儿子为 \(1\)。
- 从根节点往下，所有左儿子开始的路径值都小于右儿子开始的路径值。
运用这两点性质，我们就可以用 01Trie 造一棵平衡树。
Section 2.2 平衡树
对于每个节点，我们维护两个信息：
siz，维护以当前节点为根节点的子树大小。cnt，维护数字到当前节点为二进制的最后一位的数字个数。
此外，和普通 Trie 一样，我们还要维护树的大小 \(p\)。
几个操作
insert：平衡树的插入操作。首先，给每个经过的结点的 \(siz\) 加一，表示子树节点的个数多了一个。如果当前数字的当前二进制位为 \(0\)，就把他放在左儿子，否则放在右儿子。插入到最后一位时给当前节点的 \(cnt\) 加 \(1\)。delete：平衡树的删除操作，与insert几乎一样，只是把最后一位 \(cnt-1\) 就行了。get_rank：查询当前数的排名。从根节点开始往下，如果当前数的当前二进制位为 \(1\)，就把排名加上它的左子树的值（性质二）。get_kth：查询排名为 \(k\) 的数。从根节点往下，设它的左子树 \(siz\) 为 \(tmp\)，则如果 \(k \le tmp\)，则说明排名为 \(k\) 的节点在它的左子树上。否则向右子树查找，并把答案的当前二进制位设为 \(1\)。pre：求当前数的前驱。返回get_kth(get_rank(x))即可。nxt：求当前数的后继。返回get_kth(get_rank(x+1)+1)即可。
Section 2.3 代码实现
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXLOG=24;
const int N=1e7;
class _01trie{
private:
struct node{
int ch[2];
int siz,cnt;
}T[1<<MAXLOG];
int p;
public:
void update(int x,int offset){
int now=0;
for(int i=MAXLOG-1;i>=0;i--){
bool now_bit=(x&(1<<i));
if(T[now].ch[now_bit]==0)
T[now].ch[now_bit]=++p;
now=T[now].ch[now_bit];
T[now].siz+=offset;
}
T[now].cnt+=offset;
}
int get_rank(int x){
int now=0,ans=0;
for(int i=MAXLOG-1;i>=0;i--){
bool now_bit=(x&(1<<i));
if(now_bit==1)
ans+=T[T[now].ch[0]].siz;
now=T[now].ch[now_bit];
if(now==0)
break;
}
return ans;
}
int get_kth(int k){
int now=0,ans=0;
for(int i=MAXLOG-1;i>=0;i--){
int tmp=T[T[now].ch[0]].siz;
if(k<=tmp)
now=T[now].ch[0];
else{
k-=tmp;
now=T[now].ch[1];
ans|=(1<<i);
}
if(now==0)
break;
}
return ans;
}
int pre(int x){
return get_kth(get_rank(x));
}
int nxt(int x){
return get_kth(get_rank(x+1)+1);
}
}Trie;
int n;
int opt,x;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&opt,&x);
if(opt==1) Trie.update(x+N,1);
if(opt==2) Trie.update(x+N,-1);
if(opt==3) printf("%d\n",Trie.get_rank(x+N)+1);
if(opt==4) printf("%d\n",Trie.get_kth(x)-N);
if(opt==5) printf("%d\n",Trie.pre(x+N)-N);
if(opt==6) printf("%d\n",Trie.nxt(x+N)-N);
}
}
Section 2.4 例题
最新文章
- Apache Mina实战
- php 队列
- Neutron分析（4）—— neutron-dhcp-agent
- JAVA IO 以及 NIO 理解
- C++ 第二次课堂作业（反转链表）
- Array补充方法
- [转]分享一个用Telnet代替JLinkRTTClient的办法，实现同时显示和记录
- 我使用中的Linux命令和快捷键(For Ubuntu)
- SpringMVC 配置定时执行任务
- Linux下使用Magent+Memcached缓存服务器集群部署
- C++11新特性应用--介绍几个新增的便利算法(不更改容器中元素顺序的算法)
- angular --- s3core移动端项目（二）
- ubuntu解压命令（转）
- python 之 初识面向对象
- unknown variable 'log_bin_basename'
- 【转载】COM 组件设计与应用（二）——GUID 和 接口
- Android ListView 几个重要属性
- thinkphp辅助方法，数据库操作
- unity 脚本执行顺序设置 Script Execution Order Settings
- VC++ 获取本地IP和计算机名