普通平衡树（splay）

· · 个人记录

前言：

和树链剖分差不都，很多同学向我推荐了平衡树，那今天开始就写一写平衡树有关的博客吧。

前置知识：

BST：

他的 China 名字是二叉查找树。

就是给定一棵二叉树，每一个节点有一个权值，命名“关键码”

1.这个节点的关键码不小于它的左子树上任意一个节点的关键码

2.这个节点的关键码不大于它右子树上的任意一个关键码

然后我们就可以发现这棵树的中序遍历，就是一个关键码单调递增的节点序列。在这里我就称之为树是平衡的。

树的建立：

交换：

有同学可能就要问了，按照顺序不应该先讲如何插入一个数吗？但这里要说明的是平衡树的每一次操作都要将操作的数排到最前面（就比作考试完后，老师要找一些同学的成绩，肯定优先级先是这几个同学在前，其余同学在后）。

那么，我们就可以进行交换操作了（在此我们初始化0为根节点，不然可能出错）。

我们要把 d 移动到 c 的位置，那么我们就可以先把d的祖父节点的左子节点（在这里c是哪一边换上去d就是那一边，因为要保证b是一颗 BST）换成d，d的父亲节点换成&b&。

随后我们为了保证d还是一颗BST，那么c就只能移到原本d在的那一边的相反处（因为d在它的左下方的话d一定比c小，所以为保证不变这样移），替代的位置的数就移到d原来的位置上。

最后维护一下子树数量即可。

void shuchuan(int x) {tr[x].size=tr[tr[x].h[1]].size+tr[tr[x].h[0]].size+tr[x].cnt;}
void jiaohuan(int x)
{
    int u=tr[x].fa,v=tr[u].fa,k=(tr[u].h[1]==x);//u是父亲节点，v是祖父节点，k是当前这个数在他父亲的哪一边 
    tr[v].h[(tr[v].h[1]==u)]=x;//更改祖父的子节点 
    tr[x].fa=v;//更改自身的父亲节点 
    tr[u].h[k]=tr[x].h[1^k];//父亲下移 
    tr[tr[x].h[1^k]].fa=u;//更改当前位置上的树的父亲 
    tr[x].h[1^k]=u;
    tr[u].fa=x;
    shuchuan(u),shuchuan(x);//维护字数数量 
}

在这里还要注意一下三点共线的情况，我们遇到就需要先提父亲节点，再提他自己。

void weiyi(int x,int y)//把x换到y的子节点 
{
    while(tr[x].fa!=y)
    {
        int u=tr[x].fa,v=tr[u].fa;
        if(v!=y)
        {
            if(((tr[v].h[0]==u)^(tr[u].h[0]==x))==0)//判定三点共线 
            {
                jiaohuan(u);
            }
            else jiaohuan(x);
        } 
        jiaohuan(x);
    }
    if(y==0) tou=x;//更改树的根节点 
}

插入：

这里就到了比较熟悉的环节了，我们可以先看一看我们这颗树中有没有当前元素，如果有就直接把当前元素的数量加一，反之就添加一个元素位用来装他，最后把它反转到头。

void charu(int x)
{
    int u=tou,fa=0;
    while(u&&tr[u].sum!=x)//判断有没有这个数 
    {
        fa=u;
        u=tr[u].h[x>tr[u].sum];//大就右边，小就左边。 
    }
    if(u) tr[u].cnt++;//有元素加加 
    else//没有加一个 
    {
        u=++top;
        if(fa!=tou){tr[fa].h[x>tr[fa].sum]=u;}
        tr[u].cnt=1;
        tr[u].size=1;
        tr[u].h[0]=tr[u].h[1]=0;
        tr[u].sum=x; 
        tr[u].fa=fa;
    }
    weiyi(u,0);//旋转到根 
}

if(op==1)
{
    int x;
    cin>>x;
    charu(x);
}

查询当前元素的位置：

如果上面懂了，这里的查找方式与上面差不多。我们只需要判断当前的数比这个位置上的数大还是小，大就右边，小就左边。

void find(int x)
{
    int u=tou;
    while(tr[u].h[x>tr[u].sum]&&x!=tr[u].sum)//直接找 
    {
        u=tr[u].h[x>tr[u].sum];
    }
    weiyi(u,0);
}

查找前驱与后驱

首先你需要明白前驱与后驱是什么。

前驱就是一个数前面第一个比它小的数是多少，后驱就是一个数后面第一个比他大的数。

前驱我们只需要找这个数左节点中最右边的节点，而后驱我们只需要找到右节点中最左边的数。

int cha(int x,int f)//0是前驱，1是后驱 
{
    find(x);
    int u=tou;
    if(tr[u].sum>x&&f) return u;//判断头的大小 
    if(tr[u].sum<x&&!f) return u;//判断头的大小
    u=tr[u].h[f];//找到这个数 
    while(tr[u].h[1^f]) u=tr[u].h[1^f]; 
    return u;
}

删除：

只要你会找前驱与后驱了，那么就很简单了，我们只用先把前驱提到更节点，然后把后驱提至前驱的下面，这样直接删即可。

void shanchu(int x)
{
    int l=cha(x,0),r=cha(x,1);
    weiyi(l,0);
    weiyi(r,l);
    if(tr[tr[r].h[0]].cnt>1) tr[tr[r].h[0]].cnt--,weiyi(tr[r].h[0],0);
    else tr[r].h[0]=0;
}

找第k个数

我们只用一步步向下查找即可。

int chak(int x)
{
    int u=tou;
    if(tr[u].size<x) return 0;
    while(1)
    {
        int v=tr[u].h[0];
        if(tr[v].size+tr[u].cnt<x)
        {
            x-=tr[v].size+tr[u].cnt;
            u=tr[u].h[1];
        }
        else
        {
            if(tr[v].size>=x) u=v;
            else return tr[u].sum;
        }
    }
}