平衡树（平衡的艺术）

树结构 学习 SBT

平衡的艺术

要不断的提高自己的资识水平

都知道二叉搜索树吧,这位小哥的插入，删除操作都很简洁，简直业界典范。
然而有时候我们看见，他使用的操作未免太暴力了点，因此有时候自己都搞得一团糟，比如下面的情况：

(节点中是标号不是数据)
我们会发现，尽管节点有12个，但是层数却非log(12)=3个，原因就在于这棵树左右子树节点数并非完全相同，而是左子树大于右子树，这样我们看到的就不再是能满足我们log(n)查询要求的平衡树了。

为何会这样

原因就在于我们节点的数据有别，且我们在进行基本操作时，总会改变这样那样的节点深度，以至于在几次操作后我们就会发现我们的树不乖了。

那怎么办啊

那就需要用到SBT啦

SBT(Size Balanced Tree)

为了让树平衡，我们采取一定的操作，改换根节点，但是怎么改换根节点倒是有很多种实现方法，有Splay Treap等等，不过这些玩意代码量都不小，今天我们介绍代码量相对少一点的，SBT。
PS：本文中数据结构以及需要用到的基本操作应用如下

#define ls(t) T[t].lc
#define rs(t) T[t].rc
struct Node{
    int siz,lc,rc,val;//子树大小（包括本身），左右儿子，节点权值
    Node(){}
    Node(int x){val=x,lc=rc=0,siz=1}
}
Node T[maxn];
void pushup(int x){//用来计算一个点的子树大小
    T[x].siz=T[T[x.lc]].siz+T[T[x.rc]].siz+1;
}

平衡？

想要让树平衡，首先我们得明白什么是平衡。
平衡绝不是简单的左子树节点数等于右子树节点数,因为难免有差别，那么在SBT中，我们把平衡的概念定义如下
siz(v.child)>=siz(v.grandchild)
保证每棵子树大小不小于其兄弟的子树大小，这样就一定能平衡。
可以证明这样树的高度永远在log(n)上下。

旋根

发现了又能怎么样呢？
首先我们知道，在二叉搜索树中，左子树节点小于根节点小于右子树节点
;
再次用下这个图，我们看到，val(2)<val(1)<val(3)
图中状态不是很平衡，进行右旋，即：将2号节点重新作为根节点，1号节点作为2的右子树，5号节点作为1的左子树，1的右子树和2的左子树不变
(读者自行想象吧，我实在是没图了)
左旋的道理和右旋道理一样，下面直接给出右旋代码

void right_rotate(int &rt){//这里取地址直接改变根编号
    int t=ls(rt);
    ls(rt)=rs(t);pushup(rt);
    rs(t)=rt;pushup(t);
    rt=t;
}

知道了怎么旋根，还需要知道什么时候旋根，这时候我们使用Maintain函数(不要用maintain，否则在Linux环境下会挂掉)
上代码

void Maintain(int & rt){
    if (a[ls(ls(rt))].size>a[rs(rt)].size){
        Right_rotate(rt);
        Maintain(rt);Maintain(rs(rt));Maintain(ls(rt));return;
    }
    if(a[rs(rs(Rt))].size>a[ls(rt)].size){
        Left_rotate(rt);
        Maintain(rt);Maintain(ls(rt));Maintain(rs(rt));return;
    }
    if(a[rs(ls(rt))].size>a[rs(rt)].size){
        Left_rotate(ls(rt));Right_rotate(rt);
        Maintain(rt);Maintain(ls(rt));Maintain(rs(rt));return;
    }
    if(a[ls(rs(rt))].size>a[ls(rt)].size){
        Right_rotate(rs(rt));Left_rotate(rt);
        Maintain(rt);Maintain(ls(rt));Maintain(rs(rt));return;
    }
}

只要维护好了这树的平衡，其余操作不需要做任何变化，与普通二叉搜索树一样。
在这里我们不再给出未经任何修改的代码，只给出insert和delete两部分代码

void Insert(int & rt,int x){//注意，本文中我们大量使用了取地址操作，简化很多不必要的改变操作
    if (!rt){
        rt=++cnt;a[rt]=Node(x);
        return;
    }
    if (x<a[rt].val) Insert(ls(rt),x);
    else Insert(rs(rt),x);
    Pushup(rt);Maintain(rt);
}
void Delete(int & rt,int x){
    if (a[rt].val==x){
        if (!ls(rt) || !rs(rt)){rt=ls(Rt)+rs(rt);return;}
        Right_rotate(rt);Delete(rs(rt),x);
        Pushup(rt);Maintain(rt);
        return;
    }
    if (x<a[rt].val) Delete(ls(rt),x);
    else Delete(rs(rt),x);
    Pushup(rt);Maintain(rt);
}

总结

可以看出，整个SBT的核心代码其实只有Maintain以及rotate两个函数
其余直接沿用二叉搜索树代码就好，简洁好看。
关于复杂度，Maintain经证明可以做到O(1);高度logn，所以各种操作复杂度都是O(logn)，常数不大。
SBT最大的优点在于高度固定，且好理解。
反正我目前就会这一个优点当然多