平衡树(二)
平衡树(一)链接:算法学习笔记(18): 平衡树(一) – jeefy – 博客园
本文中将讲述一下内容:
-
可持久化Treap
-
基于
Trie
的 类 平衡树(后文称之为BSTrie
) -
BSTrie的可持久化
可持久化Treap
可持久化Treap基于FHQ-Treap。其实不难发现,FHQ-Treap在分裂和合并时在每一层只对一个结点产生影响。于是我们可以大胆的可持久化此结构,且保证复杂度为 (O(log n))。
我们以此图为例。我们只需要复制下被影响的结点,基于原树获得一条新链:
红色节点是新产生的节点(可能实际上产生的顺序不一样)
其中
(8, 11)
作为新右树的根,(7, 8)
作为新左树的根
也就是说,我们经过一个结点复制一次即可。
inline void splitVal(int p, int val, int &x, int &y, bool simple = true) {
if (!p) return (void)(x = y = 0);
int np = simple ? p : clone(p);
if (val(p)
simple就是标志是否需要可持久化……特别简单
其实到这里就已经讲完了可持久化Treap了……因为其他绝大部分操作只需要对于分裂时持久化,在合并时并不需要持久化。
例如删除操作:
inline int insert(int root, int val, bool simple = false) {
int x(0), y(0), p(++usage);
nodes[p].init(val);
splitVal(root, val, x, y, simple);
return merge(merge(x, p), y);
}
这也请读者自行思考为什么不需要合并时可持久化。
基于Trie的 类 平衡树(BSTrie)
这里基于的Trie指的是 (01Trie),考虑其实每一个数都可以被拆分为二进制,于是有了此做法。
说实话,代码无比之简短,并且十分迅速,除了空间复杂度较大之外,令我不禁想要抛弃WBLT……
后记:空间复杂度……真的很大,很多普通平衡树能过的空间,Trie真不一定能过
我们首先只考虑正数的情况。如果我们把每一个数都扩展成同一个位长,从高位向低位保存成一棵树。我们从左到右(认为0在左,而1在右)观察其叶节点所对应的值(类似于Leafy Tree),可以知道是单调递增的,于是我们可以轻易的将之进行魔改,从而做到普通平衡树所能做到的事。
template
class BSTrie {
private:
int siz[N
这是这一颗树需要用到的内容。其实从这里就应该可以知道,其空间复杂度为 (O(n log C)) 其中 (C) 表示值域大小,一般为 (32)。这与其他空间为 (O(n)) 的平衡树相比远远不如……
插入
首先看代码:
void insert(int x) {
int p = 1;
for (int i = BS; ~i; --i) {
int bt = bit(x, i), &np = ch[p][bt];
if (!np) np = newNode();
p = np, ++siz[p];
}
}
写法有些许迷惑,见谅
其中BS指的是 (lceil log C rceil)
由于我们需要用到子树的大小以方便 (rank, kth) 操作,所以对于路径上 ++siz[p]
不就是普通的 Trie
插入操作吗?不讲了。
删除
void remove(int x) {
int p = 1;
for (int i = BS; ~i; --i) {
int np = ch[p][bit(x, i)];
if (!np) return;
p = np;
}
p = 1;
for (int i = BS; ~i; --i) {
p = ch[p][bit(x, i)], --siz[p];
}
}
这里需要注意的是需要两遍向下,以防止 x
并不存在的情况。
与普通的 Trie
删除操作类似,想必代码也十分易懂。
查询排名
在普通平衡树内查询排名怎么查,这里就怎么查:
-
进入右子节点,则累加左子树的大小
-
进入左子节点,则不累加
-
没有子节点,直接返回当前结果
int rank(int x, bool within = false) {
int p = 1;
int rk = 0;
if (x >= 0) rk += siz[1];
for (int i = BS; ~i; --i) {
int bt = bit(x, i), np = ch[p][bt];
if (bt) rk += siz[ch[p][0]];
if (!np) return rk;
p = np;
}
return within ? rk + siz[p] : rk;
}
这里对于加入了
within
参数,用于提示是否需要包含x
出现的次数。
为什么在第8行直接返回是正确的?简单来说就是空子树不会对结果造成影响。具体一点请读者自行思考。
查询第k大
呃,令 x
为当前结果:
-
若进入左子树,则令
x = x
-
否则令
x = (x (打括号是为了方便理解)
如果保证树内存在至少 (k) 个数,则一定可以找到正确答案,且不会进入空子树。
但是没有这么多个数……则结果不可预测
int kth(int k) {
int p = 1;
int x = 0;
for (int i = BS; ~i; --i) {
if (k
于是,你可以在100行内写出一个优秀的平衡树了……
现在考虑有复数的情况。有两种解决方法:
-
依据符号位,建两棵树。根据补码的知识,对于有符号类型的整数,其对应的无符号整型数值越大,其值越大。所以负数也可以利用同样的代码处理。
而改变方法也很简单,将语句
int p = 1
改为int p = x (标号随意)即可。
只是在kth
时,需要有:int x = k
在
rank
前要多加一句:if (x >= 0) rk += siz[1];
其他的都没大区别。
-
第二种方案相对简单,把所有数都加上一个
offset
,保证为正整数即可……(这种方法很简答,而且可持久化时也更简单)
于是我们优先采用第二种方法(尤其是需要可持久化的时候)。
可持久化BSTrie
可持久化 Trie
会吧……OK,下课!
还是提一下可持久化的思想:
把每一个经过的结点复制出来即可……类比可持久化Treap的操作
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net