平衡树（二）

平衡树（一）链接： 算法学习笔记(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) <= val)
        x = np, splitVal(rp(p), val, rp(x), y, simple), update(x);
    else
        y = np, splitVal(lp(p), val, x, lp(y), simple), update(y);
}

                        
                      

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<int N = 100000>
class BSTrie {
private:
    int siz[N << 5];
    int ch[N << 5][2];
    int usage;
    #define newNode() ({ \
        ++usage; \
        siz[usage] = ch[usage][0] = ch[usage][1] = 0; \
        usage; \
    })
}

                        
                      

这是这一颗树需要用到的内容。其实从这里就应该可以知道，其空间复杂度为 \(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 << 1 。

• 否则令 x = (x << 1) | 1 （打括号是为了方便理解） 。

如果保证树内存在至少 \(k\) 个数，则一定可以找到正确答案，且不会进入空子树.

但是没有这么多个数……则结果不可预测 。

                        
                          int kth(int k) {
    int p = 1;
    int x = 0;
    for (int i = BS; ~i; --i) {
        if (k <= siz[lc(p)]) p = lc(p), x <<= 1;
        else k -= siz[lc(p)], p = rc(p), x = (x << 1) | 1;
    }
    return x;
}

                        
                      

---

于是，你可以在100行内写出一个优秀的平衡树了…… 。

---

现在考虑有复数的情况。有两种解决方法:

• 依据符号位，建两棵树。根据补码的知识，对于有符号类型的整数，其对应的无符号整型数值越大，其值越大。所以负数也可以利用同样的代码处理.

  而改变方法也很简单，将语句 int p = 1 改为 int p = x < 0 ? 1 : 2 （标号随意）即可。 只是在 kth 时，需要有： int x = k <= siz[1] ? (1 << (32 - BS)) - 1 : 0,

  在 rank 前要多加一句： if (x >= 0) rk += siz[1],

  其他的都没大区别.

• 第二种方案相对简单，把所有数都加上一个 offset ，保证为正整数即可……（这种方法很简答，而且可持久化时也更简单） 。

于是我们优先采用第二种方法（尤其是需要可持久化的时候）.

---

可持久化BSTrie

可持久化 Trie 会吧……OK，下课！ 。

还是提一下可持久化的思想:

把每一个经过的结点复制出来即可……类比可持久化Treap的操作 。

最后此篇关于算法学习笔记(21):平衡树（二）的文章就讲到这里了,如果你想了解更多关于算法学习笔记(21):平衡树（二）的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。