平衡树学习

查无此人 · 2019-10-12 16:16:06 · 题解

Splay

什么是Splay？

伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(log \ n)内完成插入、查找和删除操作。

总之，这是一个能实现O(log \ n)复杂度的二叉排序树

什么是二叉排序树呢？

二叉排序树就是二叉查找树，它最显著的特点便是：对于任意一个非叶节点，它的左儿子的值小于它的值，右儿子的值大于它的值

换句话说，比它小的点全在其左侧，比它大的点全在它右侧

传统的二叉查找树效率不够高，尤其是当排成一条链后，复杂度会退化至O(n)

平衡树便是可以维护效率的二叉查找树，能保证复杂度在O(log \ n)上下

Splay便是平衡树的一种实现方式。平衡树可以由很多东西来实现。但是蒟蒻只会Splay

框架代码及一些前置函数：

每一个节点不是只代表一个数，而是代表若干(cnt)个权值(v)相同的数

对于它的左儿子(son[0])，值总是小于它，右儿子son[1]反之

另外注意sum代表的是子树的元素总个数(包括重复的元素数)，不是点数(即元素种类数)

#define N 100005
int sum[N],cnt[N],son[N][2],fa[N],w[N];
//sum:该点及其子树的元素总数 cnt:该点表示元素的个数 
//son:0左儿子,1右儿子 fa:父亲 w:权值 
int n,m; //n为节点数，m为元素数  
#define root son[0][1] //根节点 

//功能函数......

#undef root

以下分别是更新sum值的pushup函数，判断自己是父亲的左/右儿子的getid函数

以及连接rt与f两点，使rt成为f的son[id]的connect函数

inline void pushup(int rt)
{
    sum[rt] = sum[son[rt][0]] + sum[son[rt][1]] + cnt[rt]; //记得加上自己 
}

inline int getid(int rt)
{
    return son[fa[rt]][0] == rt ? 0 : 1; 
}

inline void connect(int rt,int f,int id)
{
    fa[rt] = f;
    son[f][id] = rt;
}

但请注意对于两个点之间，只用一次connect会出锅

因为你只更新了要连接的两个节点，而没有考虑到它们原来所连接的节点

如图，

我们如果connect(3,1,1)，即把3号节点连到1号节点上：

看起来好像没有问题，但仔细一看，发现2号节点的右儿子仍然为3

在下面学习旋转时，会着重强调connect的用法

旋转及伸展：

伸展树之所以可以维护二叉搜索树的平衡，就在于它的旋转及伸展操作

旋转是一个灰常重要的操作，伸展便是建立在其之上的

什么是旋转，怎样旋转？

先来看图，1与2是要旋转的点

旋转后

有关系吗？？？

很明显没有

我们仔细观察，发现在变化后，2成了1的父亲，0的儿子由1变为了2

难道只是简单的swap了1和2吗？

很明显不是，3原来2的右儿子，现在变成了1的左儿子

1原来的左儿子为2,2原来的右儿子为3,1与3互相顶替了它们的位置

很明显这样旋转是有道理的，目的是使旋转后仍然为二叉搜索树

结合平衡树的性质，我们可以分类讨论：

①当当前节点v为父节点u的左儿子时，因为w[v] < w[u]，所以旋转后，u应为v的右儿子，这样原来v的右儿子及其子树只能是u的左儿子

②当当前节点v为父节点u的右儿子时，因为w[v] > w[u]，所以旋转后，u应为v的左儿子，这样原来v的左儿子及其子树只能是u的右儿子

(问为什么没有w[v] == w[u]的情况的人，可以重头再看一遍)

假设节点v是u的x(x \in \{0,1\})儿子，很容易看出旋转后u的x儿子为x相对的儿子x \ xor \ 1

那该怎么连接这些点呢？

第一篇博客说的很清楚了，我就不复述了(主要是懒得作图)，详情看代码：

inline void rotate(int rt) //将自己旋转至父亲的位置上 
{
    int f = fa[rt],rtid = getid(rt); //f为当前节点父亲，gf即父亲的父亲 
    int gf = fa[f],fid = getid(f); //rtid为当前点是父节点的哪个儿子,fid同理 
    connect(son[rt][rtid ^ 1],f,rtid);//连接自己的儿子与父亲 
    connect(f,rt,rtid ^ 1),connect(rt,gf,fid);//连接父亲与自己，自己与祖父 
    pushup(f),pushup(rt); //父亲是你的儿子，先更新老父亲，再更新你 
} 

至于什么是伸展，你可以理解为将一个节点u旋转至节点v的位置上去，说白了，就是连续旋转至目标点

按理来说，是可以直接无脑上旋的

但似乎如果祖孙一条线，先转父亲效果会更好，具体实现还是看代码

void splay(int rt,int to) //将当前节点旋转至指定节点
{
    to = fa[to];
    while(fa[rt] ^ to) //即e[rt].fa != to 
    {
        int up = fa[rt];
        if(fa[up] == to)  rotate(rt); //父亲即为指定节点
        else if(getid(rt) ^ getid(up)) //不在一条线上，将自己向上旋转两次
            rotate(rt),rotate(rt);
        else //如果你和你的祖父在一条线上，先旋转父亲，再旋转自己
            rotate(up),rotate(rt); 
    }
}

插入元素：

建立新节点：

inline void create(int v,int f,int id) 
{
    ++ n;
    w[n] = v;
    connect(n,f,id);
    sum[n] = cnt[n] = 1;
}

插入元素(不一定会建立节点):

void insert(int v) 
{
    int rt = root;
    if(!m) create(v,root,1),rt = 1;
    else
        while(true)
        {
            ++ sum[rt];//新节点肯定在下方，所以当前节点及其子树包含的元素++
            if(v == w[rt])
            {
                ++ cnt[rt]; //有该元素便++出现次数 
                break;
            }
            int nxt = w[rt] > v ? 0 : 1;
            if(!son[rt][nxt])
            {
                create(v,rt,nxt); //没有则新建一个节点 
                rt = n;
                break;
            }
            rt = son[rt][nxt];
        }
    ++ m;
    splay(rt,root);//因为新建节点可能会拉出一条链，需要将该节点splay到根节点,沿途一直rotate可恢复平衡
}

查询元素：

inline int find(int v) //找到权值等于或最接近V的节点 
{
    int rt = root;
    while(true)
    {
        if(w[rt] == v) return rt;
        int nxt = w[rt] > v ? 0 : 1;
        if(!son[rt][nxt]) return rt;//如果没有相等的元素，当前节点为最接近v的节点
        rt = son[rt][nxt];
    } 
}

代码还是好理解，至于为什么要返回最接近的节点，在下面求前驱与后缀时有用

前驱与后缀：

前驱即小于x的最大的数，由于我们在find函数中找的是最接近的元素，所以我们可以将该元素splay到根上去，如果它比v小，那它即为前驱，否则跳至其左儿子，容易得知左子树的所有权值肯定比v小，则一直跳至右儿子，以求最大

int pre(int v)
{
    splay(find(v),root);
    if(w[root] < v) return root;  
    int rt = son[root][0]; //跳到左儿子 
    while(son[rt][1]) rt = son[rt][1]; //在左儿子中一直找右儿子 
    return rt;
} 

后缀同理：

int last(int v) //找后继，即大于v的最小的数 
{
    splay(find(v),root);
    if(w[root] > v) return root;
    int rt = son[root][1];
    while(son[rt][0]) rt = son[rt][0];
    return rt;
}

移除节点：

void remove(int v)
{
    int del = find(v);
    if(w[del] != v) return; 
    -- m;
    splay(del,root);
    if(cnt[del] > 1) //如果有多个元素，删掉一个 
    {
        -- cnt[del];
        -- sum[del]; 
        return;
    }
    if(!son[del][0]) //没有左儿子，右儿子当根 
    {
        root = son[del][1];
        fa[root] = 0;
    }
    else //有左儿子，找到左儿子中最大的，令其成为左儿子，左儿子便没了它的右儿子 
    {
        int lef = son[del][0],rig = son[del][1];
        while(son[lef][1]) lef = son[lef][1];
        splay(lef,son[del][0]);
        connect(rig,lef,1),connect(lef,0,1); //把右儿子接在没了右儿子的左儿子上，左儿子当根
        root = lef;
        pushup(root);
    } 
}

主要是为什么要找左儿子中最大的当根难以让人理解

左儿子最大的节点肯定是没有右儿子的，也一定小于删除节点的右儿子，所以便可以将右儿子直接接在它身上

编号相关：

得到排名：

首先找到该节点，将其splay到根，则小于它的元素都汇集至它的左子树

它的排名便为当前节点左子树的元素和+1(加上自己)

inline int get_rank(int v)
{
    int k = find(v);
    if(v != w[k]) return -1;
    splay(k,root);
    return sum[son[root][0]] + 1;
}

查找编号为k的数：

int atrank(int k)
{
    if(k > m) return -1;
    int rt = root;
    while(true)
    {
        int minuse = sum[rt] - sum[son[rt][1]];
        if(k > sum[son[rt][0]]&&k <= minuse) break; //x即为rt
        if(k < minuse) rt = son[rt][0]; //在左儿子中 
        else
        {
            k -= minuse; //减去比他小的个数
            rt = son[rt][1]; //在右儿子中 
        }
    }
    splay(rt,root); 
    return rt;
}

好了，讲完了。

没有帮助？那就对了