平衡树

二叉搜索树

二叉搜索树是一种二叉树形的数据结构，各节点权值按中序遍历排列单调不增(或不降)。

中序遍历：先左再中后右

二叉搜索树上的基本操作所花费的时间与树的高度成正比。对于一个有 $n$个结点的二叉搜索树中，这些操作的最优时间复杂度为 $O(\log{n})$，最坏为 $O(n)$。随机构造一棵二叉搜索树的期望高度为 $O(\log{n})$。

二叉搜索树其实是一个暴力版本的平衡树，平衡树在二叉搜索树上通过一些算法，将树高严格或期望维持在$\log{n}$，但相差不会太大，保证不会退化成一条链。

各家的平衡树

平衡树按照应用可以分为两类：

权值平衡树：维护一个有序可重集合(按权值排序，中序遍历为已排序的集合)；
序列平衡树：维护一个序列(按原始下标排序，中序遍历即为序列)，并不是所有平衡树都能够用作序列平衡树。

注意，并不是所有家的平衡树都能作为以上任意一种平衡树使用。

按照平衡树高度又可以分为两类：

强平衡树：树高严格为$O(\log{n})$
弱平衡树：树高期望为$O(\log{n})$

常见的平衡树有：

Splay—伸展树
Treap—树堆
- 旋转式Treap
- 分裂式Treap(又称fhq-treap，因为是fhq发明的)
AVL树
SgT—替罪羊树(比较有意思，发现树高不为$\log{n}$时，整个推倒重新建树，复杂度竟然也不高!?)
RBT—红黑树(最快的，没有之一，C++ STL都是这个，yyds!)
…………

OI中较常用的是 Splay 和 fhq-treap(剩下的性价比不高，要就不是难写，要就不是即难写还慢)。

~~所以，你的推是哪个?~~

fhq-treap平衡树

这东西以一种不可思议的方式运行着。具体来说，就是一言不合，就把你劈成两半……~~怕了怕了~~

treap 这个单词是由 tree 和 heap 组合而来，这表明 Treap 是一种由树和堆组合形成的数据结构。

高级之处

代码短，比线段树长不了多少。
思想简单易懂，导致的就是Debug时间减少。
两种平衡树均可使用。
可支持持久化。

准备工作

先来康康需要哪些变量：

son数组：记录每个节点的儿子节点的编号 son [i] [0] 表示 $i$ 号节点左儿子的编号，son [i] [1] 为右儿子的编号。
tot：记录总结点个数，声明一个新节点时会用到。
root：记录根节点编号。
size数组：size[i]标记以 $i$ 节点为根的子树大小(包括 $i$ 号节点本身)。
val数组：记录每个节点的权值。
rnd数组：记录每个节点的随机优先级。fhq-treap 的每个结点上具有一个$priority$值，fhq-treap 除了要满足中序遍历有序的性质之外，还需满足父节点的 $priority$(随便一种关系，如大于、小于等于……)两个儿子的$priority$。在一般的实现中， $priority$是每个结点建立时随机生成的，因此 fhq-treap 是期望平衡的。

最基本的平衡树的空间复杂度为 $O(5n)$，当然也可以动态优化，但并不能起到较为显著的效果(每个节点都有可能被访问)。

宏定义

有效降低代码长度、出错概率以及Debug时间。

#define Ls son[pos][0]
#define Rs son[pos][1]

build_new_node函数

声明一个新的节点

inline int nnd(int x)  //声明一个新的节点并分配priority值
{
    size[++tot] = 1;
    val[tot] = x; //注意，维护有序队列时，应把x替换成tot，想清楚要维护的是什么
    rnd[tot] = rand();
    return tot;
}

update函数

更新当前节点的size信息

inline void upd(int pos) //更新节点size大小
{
    size[pos] = size[Rs] + size[Ls] + 1;
}

核心操作——分裂与合并

分裂

一共两种分裂方法，适用于不同场景。（作为区间平衡树时只有按节点数分裂一种）.

分裂基本原理为每次判断当前根节点将被分到左右哪侧，再递归分裂根节点位于另一侧的子树，将分裂结果的同侧部分接在原位。

按权值分裂：

按照设定的key值为分裂条件，将小于等于key的节点挂在左边，大于key的挂在右边。

inline void spv(int pos, int key, int &l, int &r) //按照权值分裂,pos当前节点编号,key分裂值,&l左侧挂载位置,&r右侧挂载位置
{
    if (pos == 0) //没有叶子节点,结束递归
    {
        l = r = 0; //没有叶子节点,结束递归,并将挂载点赋值0(空)
        return;
    }
    if (val[pos] <= key) //如果当前节点小于等于key,则将左子树(都小于当前节点,所以都小于key值)和当前节点挂在左侧,继续分裂右子树
    {
        l = pos;             //挂在上次传递的挂载点位置
        spv(Rs, key, Rs, r); //递归分裂右子树,因为右子树中所有值均大于当前节点,因此如果仍有小于key值的应挂在当前节点的右儿子的地方
    }
    else //如果当前节点大于key,则将右子树(都大于当前节点,所以都大于key值)和当前节点挂在右侧,继续分裂左子树
    {
        r = pos;             //挂在上次传递的挂载点位置
        spv(Ls, key, l, Ls); //递归分裂左子树,因为左子树中所有值均小于当前节点,因此如果仍有大于key值的应挂在当前节点的左儿子的地方
    }
    upd(pos); //更新节点size大小(因为分裂开后,子树大小有改变)
}

按节点个数分裂：
- 按照设定的key值，在左侧挂key个最小的节点，其余的挂在右侧。

```c++
inline void spn(int pos, int key, int &l, int &r) //按照节点个数分裂,pos当前节点编号,key分裂值,&l左侧挂载位置,&r右侧挂载位置
{
    if (pos == 0) //没有叶子节点,结束递归,并将挂载点赋值0(空)
    {
        l = r = 0;
        return;
    }
    if (size[Ls] + 1 <= key) //如果左子树和当前节点个数之和小于等于key,则挂在左侧,继续在右子树中选key-size[Ls]-1个加入左侧
    {
        l = pos;                            //挂在上次传递的挂载点位置
        spn(Rs, key - size[Ls] - 1, Rs, r); //递归分裂右子树,因为已经在左侧又挂了size[Ls]+1个节点,所以要在右子树中再选key-size[Ls]-1个即可
    }
    else //如果左子树和当前节点个数之和大于key,不满足条件,继续在右子树查找size合适的子树
    {
        r = pos;             //挂在上次传递的挂载点位置
        spn(Ls, key, l, Ls); //递归分裂左子树,因为并没有在左侧挂任何节点,因此key不改变
    }
    upd(pos); //更新节点size大小(因为分裂开后,子树大小有改变)
}
```

合并

合并是分裂的逆操作，基本原理为按照优先级判断哪棵树的根将成为新树的根，之后递归地合并另一棵树与当前树的对应子树。

需要注意的是：fhq-treap 的合并操作相当于只是简单拼接两棵树的中序遍历，不会检查权值是否有序(理论上如果操作正确的话，分裂出的子树均为有序)，如果被合并的两棵树权值大小关系有误，将导致之后按权值分裂是出现不可预期的结果！

inline int tog(int l, int r) //合并两棵树,l左侧树的根节点,r右侧树的根节点;递归思想
{
    if (l == 0 || r == 0) //如果任意一个树是空的,剩余的树的根节点就是挂载点
        return l + r;
    if (rnd[l] < rnd[r]) //优先级定义,可以随便写
    {
        son[l][1] = tog(son[l][1], r); //右侧树挂载左侧树的右侧
        upd(l);                        //更新左侧树根节点的信息
        return l;                      //返回新树的根节点
    }
    son[r][0] = tog(l, son[r][0]); //左侧树挂载右侧树的左侧
    upd(r);                        //更新右侧树根节点的信息
    return r;                      //返回新树的根节点
}

各种操作

总之就是使用上面三种核心操作，实现的一系列qwq的实际操作。

~~感受fhq脑洞之大吧~~

inside插入

inline void ins(int v)
{
    spv(root, v, ll, rr);            //按照v分割成根节点为ll和rr两棵子树
    root = tog(tog(ll, nnd(v)), rr); //先合并ll和新加入的节点,再和rr合并,然后更新总树的根节点
}

delete删除

若有多个相同的数，只删除一个。

inline void del(int val)
{
    spv(root, val, ll, rr);        //按照v分割成根节点为ll和rr两棵子树
    spn(ll, size[ll] - 1, ll, LL); //再在左侧分割出1个节点挂在右侧
    root = tog(ll, rr);            //合并新ll和rr,不合并第二次分裂的右侧1个节点,即删除,然后更新总树的根节点
}

order-value查询key值的排名

排名定义为比当前数小的数的个数 $+1$ 。

inline int ordv(int v)
{
    spv(root, v - 1, ll, rr); //将所有小于v的数分割
    int r = size[ll];         //记录根节点size,即所有小于v的节点的数量,后续合并时可能变化
    root = tog(ll, rr);       //合并分裂开的两棵树
    return r + 1;             //返回注意+1
}

order-num查询第key个数的值

inline int ordn(int k)
{
    spn(root, k, ll, rr);        //分裂出前k个节点
    spn(ll, k - 1, ll, RR);      //再分裂出前k-1个节点,这样右侧就有一个排名为k的节点,其下标为RR
    root = tog(tog(ll, RR), rr); //合并分裂开的两棵树
    return val[RR];              //返回编号为RR的节点的权值
}

fir查询前驱(前驱定义为小于x，且最大的数)

inline int fit(int v)
{
    spv(root, v - 1, ll, rr);      //先分裂出所有小于v的节点
    spn(ll, size[ll] - 1, ll, RR); //再在小于v的节点中分裂出最大的一个,因为ll是根节点,size[ll]即为小于v的节点数量
    root = tog(tog(ll, RR), rr);   //合并分裂开的ll,前缀和rr
    return val[RR];                //返回前驱的值
}

back查询后继(后继定义为大于x，且最小的数)

inline int back(int v)
{
    spv(root, v, ll, rr);        //先分裂出所有小于等于v的节点
    spn(rr, 1, LL, rr);          //再在大于v的节点中分裂出最小的一个
    root = tog(tog(ll, LL), rr); //合并分裂开的ll,后缀和rr
    return val[LL];              //返回后缀的值
}

“懒”标记

在某些时候，当实现一个对于区间的操作时，也可以在平衡树上使用“懒”标记以达到降低时间复杂度的目的。

和线段树一样，也应该注意标记的下放和优先级关系。

最近更新于 2021年10月17日