平衡树不好打?试试Trie字典树！
Woc,考场(面试)忘记打平衡树怎么办,Trie救你命
文本只发布于博客园,其他地方出现本文均是未经许可的盗版。
算法导入
众所周知平衡树很难打(大佬除外),还老是调错。万一这种事情发生在关键时刻你就GG了。那我们怎么办呢？
从本质上介绍,平衡树作用就是维护一个有序的序列(关系)。很多操作我们用vector(数组)+lower_bound(二分查找),都可以实现。但是vector插入不便,导致序列维护不便。如果用list(链表)代替vector,那么查找又很慢。怎么办呢？
考虑到我们一般都是维护一个整数的排序，那么我能不能找到一种支持动态排序的数据结构。堆可以进行动态处理，但是只有第一个是有序的，他的子节点只能满足比他小(大)。
难道除了平衡树我们就没有别的方法了吗？答案是有的。看看下面的树。
Root–>A[“0”]
Root–>B[“1”]
A[“0”]–>C[“0”]
A[“0”]–>D[“1”]
B[“1”]–>E[“0”]
B[“1”]–>F[“1”]
C[“0”].->G[“0”]
D[“1”].->H[“1”]
E[“0”].->I[“2”]
F[“1”].->K[“3”]
这不是01Trie(字典树)吗？这能当平衡树？？？？
别急，仔细看看。
这个Trie是不是左子树小于右子树？
好像是啊
再想想为什么？
应该是二进制关系,左边的节点当前这一位是0,后面更小的位再大,也不可能比当前这一位是1的大了。
没错
你再想想，Trie字典树是不是可以动态插入？
好像是
所以我们可以利用这种关系实现平衡了。甚至我们还能很简单的实现可持久化。
但是不难看出有几个缺点。
-
空间要比一般平衡树大，一个int32最坏情况需要32个int32去记录他。当然实际情况也不可能都是这样。实际运用中有许多的重复节点，可以重复利用的。知道数字范围的时候也能调整树高解决。在一道平衡树的模板题，内存是FHQ_Treap的1.7倍,速度更快，内存是Splay的2/3，速度差不多。是红黑树的4/5，速度是1/2。
-
不能直接输入负数(除非你建树的时候把符号位也建立进去，不过这样你也不好解决大小查找，毕竟负数是补码，情况和正数相反)。你需要加一个比较大的数值使得负数变为正数。
-
不能进行序列操作(不过支持这个操作的平衡树也不多)。
当然直接用Trie也不行，你还需要维护几个信息,否则你没法实现一些功能。
你需要维护
- 每个节点对应子树大小
- 每个叶子节点的值的数量(为了支持重复值插入)
代码实现
提前定义
这里我定义树高为25层
const int MAXLOG=25;
节点信息
需要保存两个儿子，节点子树大小，叶子节点计数
代码如下
struct node
{
int ch[2];
int sze, cnt;
} Tree[MAXLOG];
int p; //模拟一个内存池,这是对应的顶。
插入&删除 操作
插入操作其实和一般树没什么区别，唯一不同的地方就是你需要维护节点的sze和cnt信息。
删除操作和插入操作其实一样，区别就是一个做加法，一个做减法。
代码如下
void updata(int x, int offset) // 插入/删除 offset个x,插入正,删除负
{
int now = 0; //0是根
for (int i = MAXLOG - 1; i >= 0; i--)
{
bool now_bit = (x & (1 << i) != 0); //第i位的数值
if (!Tree[now].ch[now_bit] == 0) //指向空,需要分配子节点
Tree[now].ch[now_bit] = ++p;
now = Tree[now].ch[now_bit];
Tree[now].sze += offset; //这条子树链上的节点都需要
}
Tree[now].cnt += offset; //跑到叶子节点了
}
数取排名
代码也是比较简单,就是注意当节点为NULL的时候就可以退出了。
int get_rank(int x) //获取比x小的数的数量,不包括本身
{
int now = 0; //0是根
int ans = 0;
for (int i = MAXLOG - 1; i >= 0; i--)
{
bool now_bit = ((x & (1 << i)) != 0); //第i位的数值
if (now_bit == 1) //处于大的那一边
ans += Tree[Tree[now].ch[0]].sze; //把比自己小的那些加上
now = Tree[now].ch[now_bit];
if (now == 0) //别忘了,这里的0是空的意思
break;
}
return ans;
}
排名取数
int get_kth(int k) //通过排名大小
{
int now = 0; //0是根
int ans = 0;
for (int i = MAXLOG - 1; i >= 0; i--)
{
int temp = Tree[Tree[now].ch[0]].sze; //看看自己前面有多少
if (k <= temp) //还在更前面
now = Tree[now].ch[0];
else //在自己后面
{
k -= temp; //更新相对在右子树的位置
now = Tree[now].ch[1];
ans |= (1 << i); //可以确定这一位是1
}
if (now == 0) //别忘了,这里的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的,Trie能可持久化,这个也能。不过可持久化我们以后再讲。
完整代码下载地址://files.cnblogs.com/files/blogs/694685/TrieBST.7z
