P3369 【模板】普通平衡树 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • ViXbob
    这么好的题解
  • attack
    +1
  • Chorse
    个人感觉Splay讲的最好的
  • wh_ZH
    坐稳了,送您上去
  • rill7747
    大佬%%%题解写得好详细啊
  • Windows_XP
    dalao至极
  • ZCDHJ
    好懂啊。。。
  • 依依
    写的好棒
  • 雨季
    +1
  • Dispwnl
    +1
作者: rentenglong 更新时间: 2017-03-04 21:29  在Ta的博客查看 举报    840  

本题的Splay写法(无指针Splay超详细)

前言

首先来讲。。。终于调出来了55555。。。调了整整3天。。。。。

看到大部分大佬都是用指针来实现的Splay。小的只是按照Splay的核心思想和原理来进行的。可能会有不妥之处,还请大佬们指出,谢谢!

那么这个题解存在的意义就是让不会敲Splay的人额。。。会敲Splay啦。。。

基本思想

数据结构

对于Splay,我定义了一个class类(当成struct就行啦。。。个人习惯不同啦),定义名称为“Splay”。

之后在类中,我定义了Splay的主体,即数组e。

e的类型是node类型,包含节点值(v)、父级节点(father)、左孩子(ch[0])、右孩子(ch[1])、包含自己在内的下面共有多少元素(sum)(注意是元素啊!!!不是节点!!!)、该节点所表示的元素出现的次数(recy)。

之后,还在类中定义了n代表当前已经使用的数组编号。points代表整个树总共有多少元素(注意是元素啊!!!不是节点!!!)。

另外,整棵树中,有一个超级根e[0],其右孩子即为树的根。

宏定义了e[0].ch[1]为root,方便访问、理解。并在类的末尾取消定义root,确保外部再定义root变量时不会出现问题,维持其模块性质。

class Splay//存储规则:小左大右,重复节点记录 
{
    #define root e[0].ch[1]   //该树的根节点
    private:
        class node
        {
            public:
                int v,father;//节点值,父级节点 
                int ch[2];//左孩子=0,右孩子=1
                int sum;//自己+自己下级有多少节点。在根节点为1。
                int recy;//记录自己被重复了几次
        };        
node e[MAXL];//Splay树主体
        int n,points;//使用存储数,元素数
    ……
    #undef root
};

功能全解

更新当前节点sum值(update)

就是在进行了连接、插入、删除等操作以后使用的一个维护性质的函数。用来确定被update的节点的sum值。

void update(int x)
{
    e[x].sum=e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].recy;
}

获取父子关系(identify)

用来确定当前节点到底是父亲的左孩子(0)还是右孩子(1)。

int identify(int x)
{
    return e[e[x].father].ch[0]==x?0:1;
}

建立父子关系(connect)

用来连接两个点,其中一个点为另一个点的孩子。

注意,这个操作并不能将其他的父子关系一并断开。因为他们与被操作的两个点没有直接的数据联系。例如下图:

图表明尽管B的父亲已经不是x,但是x的右孩子依旧是B,没有被更新。因此使用过程中应当有更巧妙的设计来避免这样导致的错误发生。

void connect(int x,int f,int son)//连接函数。用法:connect(son,father,左儿子(0)或右儿子(1))
{
    e[x].father=f;
    e[f].ch[son]=x;
}//作用:将x连接在f的下方。连接方向由son的值决定。

旋转节点(rotate)

着重注意的一个函数。这个函数同时实现了左旋和右旋。

所谓的旋转,其实就是指将被指定的节点向上移动一级,并将原有的父级节点作为自己的儿子。如下图:

我们可以通过下图原理论证来确定只需要三次connect即可完成旋转。

上图代表了右旋。

在图中,A、B、C代表三个子树(可以是空的),x和y代表被旋转的节点。R为y的上级节点,与旋转没有直接关系,但是它的右孩子要进行相应的改变。

在进行完connect函数后,再进行update函数即可完成旋转。

但是旋转总共有两种类型的操作(即左旋和右旋)。在这里,我们需要配合位运算直接达到自动判断和旋转方向决断的目的。

我们知道,对于任意一个自然数,与1进行逻辑异或运算,会得到这样的结果:

0^1=1 1^1=0 2^1=3 3^1=2 4^1=5 5^1=4 ……

也就是说,0对应1,2对应3,4对应5,向后依次推。

既然这样,那么我们的左右儿子节点所代表的编号分别是0和1。也就是说对其中一个取逻辑异或,会得到另一个儿子的标号(即对0取逻辑异或得1,对1取逻辑异或得0)。

通过左旋右旋的性质可以知道,实际改变了父子关系的节点是上图的:x、y、B节点。因为实际上,A、C节点的父子关系并没有发生任何改变。

并且我们能够注意到,x与y节点的连接方向一定是与x和B的连接方向不同的。

那么,我们只需要先通过“identify”函数确定x与y的父子关系,确定到底要向那一边旋转(如果x是y的左孩子,那么就向右旋转。如果x是y的右孩子,那么就向左旋转),然后通过逻辑异或来确定子树“B”究竟应当被连接在y的哪一侧。

void rotate(int x)
{
    int y=e[x].father;
    int mroot=e[y].father;
    int mrootson=identify(y);
    int yson=identify(x);
    int B=e[x].ch[yson^1];
    connect(B,y,yson);connect(y,x,(yson^1));connect(x,mroot,mrootson);
    update(y);update(x);
}

伸展操作(Splay)

其实就是考虑上旋节点的方式。

在这里,一开始我使用了一种较为偷懒的旋转方式,即能向上旋转就向上旋转。并不考虑上面的状况到底怎样。

其实,标准的写法中,需要考虑两种情况。如下图:

为了防止造成误导,我将不再介绍直接上旋的操作。但事实上,无论是直接上旋还是先判断再上旋,都会有可能进化或者退化原本的树形结构。

我也曾举出过两种操作模式各自进化或者退化树的例子。但是根据交题情况,在洛谷的模板题中,直接上旋的速度更快。然而在湖南的一道省选题中,使用直接上旋的模式却直接导致超时(大概慢了10倍)。所以说在面对大数据的不确定因素下,还是应当选择考虑更多种情况,而不能图方便。

在这里,我的函数实现的操作是:将at节点旋转到to节点所在的位置。

void splay(int at,int to)
{
    to=e[to].father;
    while(e[at].father!=to)
    {
        int up=e[at].father;
        if(e[up].father==to) rotate(at);
        else if(identify(up)==identify(at))
        {//对应图中case1
            rotate(up);
            rotate(at);
        }
        else
        {//对应图中case2
            rotate(at);
            rotate(at);
        }
    }
}

添加节点(crepoint)和摧毁节点(destroy)

这两个操作是在插入新元素和删除元素过程中使用的函数。

crepoint的作用是获得一个新的树存储位置,然后为这个存储空间写入基本的信息,并返回使用的存储位置编号。

destroy的作用则是使得一个节点完全失效,完全抹除节点信息,防止其他意外的发生。并且添加了一个小小的优化:如果被抹除的节点恰好是存储数组的当前最后一个元素,那么就对存储空间的使用数减1。

实际上,也可以通过一个队列来确定那些节点在中间被挖空了。但这样的操作不仅要牺牲一个O(log N)的时间复杂度,而且事实上并没有太大的用处,因为你开的数组大小一定能够满足极端情况(比如说所有操作都是插入)。

int crepoint(int v,int father)
{
    n++;
    e[n].v=v;
    e[n].father=father;
    e[n].sum=e[n].recy=1;
    return n;
}
void destroy(int x) 
{
    e[x].v=e[x].ch[0]=e[x].ch[1]=e[x].sum=e[x].father=e[x].recy=0;
    if(x==n) n--;
}

查找元素(find)

要实现的功能是找特定值是否在树中以及对应的节点编号。

很简单的实现方式。从根开始向下移动,如果要找的元素比当前节点小,那么就转到自己的左孩子。否则,就转向自己的右孩子,直到节点值等于要找的值。

如果在找到目标值之前,需要走的路已经无法再走(比如说现在到了5,要找的是3,应该往左走,但是5已经没有左孩子了),那么则查找失败,返回失败值(0)。如果查找成功,则返回节点对应的编号。

查找结束后,将被查找的节点旋转到根,以保证树的结构随机性。

int find(int v) 
{
    int now=root;
    while(true)
    {
        if(e[now].v==v)
        {
            splay(now,root);
            return now;
        }
        int next=v<e[now].v?0:1;
        if(!e[now].ch[next]) return 0;
        now=e[now].ch[next];
    }
}

建树(build)

建树的功能我并没有看懂大佬们的操作到底是什么意思。。。(我觉得应该是将Splay用作线段树的时候使用的功能)所以我写了一个没有上旋操作的insert函数。

首先,从根开始,向下寻找。如果要插入的元素已经在树中,那么将这个节点的recy加1即可。如果没有出现过,那么找一个合适的空的位置。找到位置后,调用crepoint函数,在数组中申请一个新的下标存储元素。

同时注意,在向下寻找的过程中,对被经过的点的sum值加1,因为如果经过这个点,代表要加的点肯定在自己下面,所以自己下面的元素个数加1。

int build(int v)//内部调用的插入函数,没有splay 
{
    points++;
    if(n==0)//特判无点状态 
    {
        root=1;
        crepoint(v,0);
    }
    else
    {
        int now=root;
        while(true)//向下找到一个空节点 
        {
            e[now].sum++;//自己的下级肯定增加了一个节点 
            if(v==e[now].v)
            {
                e[now].recy++;
                return now;
            }
            int next=v<e[now].v?0:1;
            if(!e[now].ch[next])
            {
                crepoint(v,now);
                e[now].ch[next]=n;
                return n;
            }
            now=e[now].ch[next];
        }
    }
    return 0;
}

插入节点(push)

就是在进行完build操作以后,执行一次上旋操作,确保树的结构随机性。

void push(int v)
{
    int add=build(v);
    splay(add,root);
}

删除节点(pop)

将输入值对应的节点在树中移除。

进行这样的操作时,我一开始考虑的是通过逐层的rotate操作将要被删除的节点转到最下方,然后再删除,最后逐层向上改变路径上的sum值。但是考虑到这样的操作可能会一方面导致树的大幅度退化,另一方面相当于要进行两次O(log N)的时间复杂度操作,常数略大,可能会成为一颗定时炸弹。所以为了稳定,还是用了常规的方法:

首先将要删除的节点旋转到根节点的位置。

然后,判断情况:如果要被删除的节点(注意现在它在根的位置)没有左孩子,那么直接摧毁这个节点,并将它的右孩子变成根。

如果自己有左孩子,那么就先把左子树中值最大的元素旋转到根的左孩子位置,然后将根节点的右孩子变成根节点的左孩子的右孩子,然后摧毁节点,并将左孩子变成根。

原理还请读者自己考虑吧,根据二叉排序树的性质。。。

void pop(int v)//删除节点 
{
    int deal=find(v);
    if(!deal) return;
    points--;
    if(e[deal].recy>1)
    {
        e[deal].recy--;
        e[deal].sum--;
        return;
    }
    if(!e[deal].ch[0])
    {
        root=e[deal].ch[1];
        e[root].father=0;
    }
    else
    {
        int lef=e[deal].ch[0];
        while(e[lef].ch[1]) lef=e[lef].ch[1];
        splay(lef,e[deal].ch[0]);
        int rig=e[deal].ch[1];
        connect(rig,lef,1);connect(lef,0,1);
        update(lef);
    }
    destroy(deal);
}

获取元素的排名(rank)&获取该排名对应的元素值(atrank)

两个函数是互逆的函数。

rank的实现根find差不多,只是在向下走的时候,对于当前已经记录的rank值进行更新(每次调用rank时都初始化为0)。规则是:向左走时,rank值不发生任何改变。向右走之前,要先给rank加上当前节点的左孩子的sum值和recy值。找到对应元素时,再对rank+1。如下图:

atrank函数根rank实现完全相反。在向下走的过程中,如果要找的排名大于当前点左子树的sum值,并且小于等于当前点的左子树的sum加上本节点的recy的值,那么当前的点就是要找的点。如果小于上述范围,就往左走,反之向右。注意向右走的过程中,将要查询的排名值减少上述范围的最大值。

两个操作结束后,都要将被操作的节点旋转到根。

int rank(int v)//获取值为v的元素在这棵树里是第几小 
{
    int ans=0,now=root;
    while(true)
    {
        if(e[now].v==v) return ans+e[e[now].ch[0]].sum+1;
        if(now==0) return 0;
        if(v<e[now].v) now=e[now].ch[0];
        else
        {
            ans=ans+e[e[now].ch[0]].sum+e[now].recy;
            now=e[now].ch[1];
        }
    }
    if(now) splay(now,root);
    return 0;
}
int atrank(int x)//获取第x小的元素的值 
{
    if(x>points) return -INF;
    int now=root;
    while(true)
    {
        int minused=e[now].sum-e[e[now].ch[1]].sum;
        if(x>e[e[now].ch[0]].sum&&x<=minused) break;
        if(x<minused) now=e[now].ch[0];
        else
        {
            x=x-minused;
            now=e[now].ch[1];
        }
    }
    splay(now,root);
    return e[now].v;
}

查找前驱(lower)和后继(upper)

两种操作是类似的操作。

前驱是指在树中,小于这个值并且最接近这个值的元素值。

后继则是大于这个值并且最接近这个值的元素值。

对于这两种函数的实现方式,就是先初始化一个最值,然后在向下走的过程中,如果发现了符合要求且更优的值,就用更优值替换当前的值。最后不能走的时候输出这个值即可。

int upper(int v) 
{
    int now=root;
    int result=INF;
    while(now)
    {
        if(e[now].v>v&&e[now].v<result) result=e[now].v;
        if(v<e[now].v) now=e[now].ch[0];
        else now=e[now].ch[1];
    }
    return result;
}
int lower(int v) 
{
    int now=root;
    int result=-INF;
    while(now)
    {
        if(e[now].v<v&&e[now].v>result) result=e[now].v;
        if(v>e[now].v) now=e[now].ch[1];
        else now=e[now].ch[0];
    }
    return result;
}

完整源代码

下面贴出完整源代码,方便交流分享!

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXL=100005;
const int INF=2147480000;

class Splay//存储规则:小左大右,重复节点记录 
{
    #define root e[0].ch[1]   //该树的根节点
    private:
        class node
        {
            public:
                int v,father;//节点值,父级节点 
                int ch[2];//左孩子=0,右孩子=1
                int sum;//自己+自己下级有多少节点。在根节点为1。
                int recy;//记录自己被重复了几次
        };
        node e[MAXL];//Splay树主体
        int n,points;//使用存储数,元素数
        void update(int x)
        {
            e[x].sum=e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].recy;
        }
        int identify(int x)
        {
            return e[e[x].father].ch[0]==x?0:1;
        }
        void connect(int x,int f,int son)//连接函数。用法:connect(son,father,1/0)
        {
            e[x].father=f;
            e[f].ch[son]=x;
        }//作用:使得x的father=f,f的son=x.
        void rotate(int x)
        {
            int y=e[x].father;
            int mroot=e[y].father;
            int mrootson=identify(y);
            int yson=identify(x);
            int B=e[x].ch[yson^1];
            connect(B,y,yson);connect(y,x,(yson^1));connect(x,mroot,mrootson);
            update(y);update(x);
        }
        void splay(int at,int to)//将at位置的节点移动到to位置
        {
            to=e[to].father;
            while(e[at].father!=to)
            {
                int up=e[at].father;
                if(e[up].father==to) rotate(at);
                else if(identify(up)==identify(at))
                {
                    rotate(up);
                    rotate(at);
                }
                else
                {
                    rotate(at);
                    rotate(at);
                }
            }
        }
        int crepoint(int v,int father)
        {
            n++;
            e[n].v=v;
            e[n].father=father;
            e[n].sum=e[n].recy=1;
            return n;
        }
        void destroy(int x)//pop后摧毁节点 
        {
            e[x].v=e[x].ch[0]=e[x].ch[1]=e[x].sum=e[x].father=e[x].recy=0;
            if(x==n) n--;//最大限度优化
        }
    public:
        int getroot(){return root;}
        int find(int v)//用于外部的find调用
        {
            int now=root;
            while(true)
            {
                if(e[now].v==v)
                {
                    splay(now,root);
                    return now;
                }
                int next=v<e[now].v?0:1;
                if(!e[now].ch[next]) return 0;
                now=e[now].ch[next];
            }
        }
        int build(int v)//内部调用的插入函数,没有splay 
        {
            points++;
            if(n==0)//特判无点状态 
            {
                root=1;
                crepoint(v,0);
            }
            else
            {
                int now=root;
                while(true)//向下找到一个空节点 
                {
                    e[now].sum++;//自己的下级肯定增加了一个节点 
                    if(v==e[now].v)
                    {
                        e[now].recy++;
                        return now;
                    }
                    int next=v<e[now].v?0:1;
                    if(!e[now].ch[next])
                    {
                        crepoint(v,now);
                        e[now].ch[next]=n;
                        return n;
                    }
                    now=e[now].ch[next];
                }
            }
            return 0;
        }
        void push(int v)//插入元素时,先添加节点,再进行伸展 
        {
            int add=build(v);
            splay(add,root);
        }
        void pop(int v)//删除节点 
        {
            int deal=find(v);
            if(!deal) return;
            points--;
            if(e[deal].recy>1)
            {
                e[deal].recy--;
                e[deal].sum--;
                return;
            }
            if(!e[deal].ch[0])
            {
                root=e[deal].ch[1];
                e[root].father=0;
            }
            else
            {
                int lef=e[deal].ch[0];
                while(e[lef].ch[1]) lef=e[lef].ch[1];
                splay(lef,e[deal].ch[0]);
                int rig=e[deal].ch[1];
                connect(rig,lef,1);connect(lef,0,1);
                update(lef);
            }
            destroy(deal);
        }
        int rank(int v)//获取值为v的元素在这棵树里是第几小 
        {
            int ans=0,now=root;
            while(true)
            {
                if(e[now].v==v) return ans+e[e[now].ch[0]].sum+1;
                if(now==0) return 0;
                if(v<e[now].v) now=e[now].ch[0];
                else
                {
                    ans=ans+e[e[now].ch[0]].sum+e[now].recy;
                    now=e[now].ch[1];
                }
            }
            if(now) splay(now,root);
            return 0;
        }
        int atrank(int x)//获取第x小的元素的值 
        {
            if(x>points) return -INF;
            int now=root;
            while(true)
            {
                int minused=e[now].sum-e[e[now].ch[1]].sum;
                if(x>e[e[now].ch[0]].sum&&x<=minused) break;
                if(x<minused) now=e[now].ch[0];
                else
                {
                    x=x-minused;
                    now=e[now].ch[1];
                }
            }
            splay(now,root);
            return e[now].v;
        }
        int upper(int v)//寻找该值对应的一个最近的上界值 
        {
            int now=root;
            int result=INF;
            while(now)
            {
                if(e[now].v>v&&e[now].v<result) result=e[now].v;
                if(v<e[now].v) now=e[now].ch[0];
                else now=e[now].ch[1];
            }
            return result;
        }
        int lower(int v)//寻找该值对应的一个最近的下界值 
        {
            int now=root;
            int result=-INF;
            while(now)
            {
                if(e[now].v<v&&e[now].v>result) result=e[now].v;
                if(v>e[now].v) now=e[now].ch[1];
                else now=e[now].ch[0];
            }
            return result;
        }
    #undef root
};
Splay F;

int main()
{

    return 0;
}

后记

总算是讲完了如何实现最基础的Splay排序树。

可能会有大佬感觉:明明是来做题的了,怎么会有不懂Splay的呢?这不纯粹是装逼么?而且一点水平也没有,纯粹瞎扯淡!

我只能说,我刚开始学Splay的时候,就是一点一点的寻找相关资料的。包括从这道模板题找。但是系统讲解的还真没多少。而且贴出来的示例代码比较复杂,表示弱鸡看不懂。。。所以在钻研以后,写下了这篇文章。这些是我对Splay的理解。我将他们变成了书面的东西去分享给大家,希望大家能够从中受益,希望能够帮到更多正在努力学习平衡树的OIERS。如果有问题,也可以提出来,帮助我改进。

评论

  • 落寞音箫
    为你写红黑树点赞,但是我估计没什么人学。。。
  • Rye_Catcher
    %%%
  • 密期望
    神犇大大,我第一次写红黑树,懂了思想过后自己实现的,0分,发在了讨论版,能看看吗?谢谢了。
  • 杜岱玮
    说起来我写的一棵平衡树就是红黑树。。。
  • 杜岱玮
    毕竟是照着算法导论学的
  • 翎驰
    红黑树比 Treap 简单
  • 13813812138xixixixi
    和线段树一样简单
  • temp6
    NB!
  • IzayoiAster
    OTTTTTTTTTTTTZ
  • Starrydream
    红黑树。。。
作者: 北极鹅 更新时间: 2018-02-15 15:15  在Ta的博客查看 举报    248  

看了那么多Splay、Treap、SBT、替罪羊树的题解,是时候来一篇此题历史最快的代码了。

红黑树,同样是一种自平衡二叉搜索树,由Rudolf Bayer最先提出,当时被称为平衡二叉B树(其实红黑树本质就是一棵B-tree),后来被Leo J. Guibas和Robert Sedgewick修改为"红黑树"。

红黑树具有如下性质:

1.红黑树是一棵平衡二叉搜索树,其中序遍历单调不减。

2.节点是红色或黑色。

3.根节点是黑色。

4.每个叶节点(也有称外部节点的,目的是将红黑树变为真二叉树,即NULL节点,空节点)是黑色的。

5.每个红色节点的两个子节点都是黑色。(换句话说,从每个叶子到根的所有路径上不能有两个连续的红色节点)

6.从根节点到每个叶子的所有路径都包含相同数目的黑色节点(这个数值叫做黑高度)。

如下面一棵树就是红黑树(请自行脑补外部节点):

而这几棵树就不是:

红黑树有几个变种,如AA树等,就此题而言,我将使用自己实现的最常见的红黑树模版

#include <cstdio>
#include <cctype>
#include <cassert>
using namespace std;

//#define __REDBLACK_DEBUG

#define bro(x) (((x)->ftr->lc == (x)) ? ((x)->ftr->rc) : ((x)->ftr->lc))
#define islc(x) ((x) != NULL && (x)->ftr->lc == (x))
#define isrc(x) ((x) != NULL && (x)->ftr->rc == (x))

template<typename T>
class redblacktree {
    protected:
        struct Node;

        Node* _root;    ////根节点位置
        Node* _hot; ////临时维护的节点

        void init(T);
        void connect34(Node*, Node*, Node*, Node*, Node*, Node*, Node*);
        void SolveDoubleRed(Node*); ////双红修正
        void SolveDoubleBlack(Node*);   //双黑修正
        Node* find(T, const int);   ////允许重复的查找
        Node* rfind(T, const int);  ////不允许重复的查找
        Node* findkth(int, Node*);
        int find_rank(T, Node*);
#ifdef __REDBLACK_DEBUG
        void checkconnect(Node*);
        void previs(Node*, int);
        void invis(Node*, int);
        void postvis(Node*, int);
#endif

    public:

        struct iterator;

        redblacktree() : _root(NULL), _hot(NULL) {}

        int get_rank(T);
        iterator insert(T);
        bool remove(T);
        int size();
        bool empty();
        iterator kth(int);
        iterator lower_bound(T);
        iterator upper_bound(T);
#ifdef __REDBLACK_DEBUG
        void vis();
        void correctlyconnected();
#endif
};

其中定义宏__REDBLACK_DEBUG是为了方便调试,提交的时候可以注释掉。

宏islc()、isrc()是用来判断是否为左右儿子节点的,宏bro(x)返回节点x的兄弟。

节点

下面,根据需要维护的信息,我们可以轻松写出节点Node的结构体:


template <typename T>
struct redblacktree<T>::Node {
    T val;  ////节点信息
    bool RBc;   ////节点颜色,若为true,则节点为Red;否则节点为Black.
    Node* ftr;  ////父亲
    Node* lc;   ////左儿子
    Node* rc;   ////右儿子
    int s;      ////域

    Node(   T v = T(), bool RB = true,
            Node* f = NULL, Node* l = NULL, Node* r = NULL ,int ss = 1  )
        : val(v), RBc(RB), ftr(f), lc(l), rc(r), s(ss) {}

    Node* succ() {      ////删除节点时用到的替代节点
        Node* ptn = rc;
        while(ptn->lc != NULL) {
            --(ptn->s);
            ptn = ptn->lc;
        }
        return ptn;
    }

    Node* left_node() {     ////直接前驱
        Node* ptn = this;
        if(!lc) {
            while(ptn->ftr && ptn->ftr->lc == ptn)
                ptn = ptn->ftr;
            ptn = ptn->ftr;
        } else {
            ptn = ptn->lc;
            while(ptn->rc) {
                ptn = ptn->rc;
            }
        }
        return ptn;
    }

    Node* right_node() {    ////直接后继
        Node* ptn = this;
        if(!rc) {
            while(ptn->ftr && ptn->ftr->rc == ptn)
                ptn = ptn->ftr;
            ptn = ptn->ftr;
        } else {
            ptn = ptn->rc;
            while(ptn->lc) {
                ptn = ptn->lc;
            }
        }
        return ptn;
    }

    void maintain() {   ////维护域s
        s = 1;
        if(lc) s += lc->s;
        if(rc) s += rc->s;
    }
};

迭代器

迭代器的结构体也很容易写出来啦:

template <typename T>
struct redblacktree<T>::iterator {
    private:

        Node* _real__node;

    public:

        iterator& operator++() {
            _real__node = _real__node->right_node();
            return *this;
        }

        iterator& operator--() {
            _real__node = _real__node->left_node();
            return *this;
        }

        T operator*() {
            return _real__node->val;
        }

        iterator(Node* node_nn = NULL) : _real__node(node_nn) {}
        iterator(T const& val_vv) : _real__node(rfind(val_vv, 0)) {}
        iterator(iterator const& iter) : _real__node(iter._real__node) {}

};

插入、双红现象及其修正

插入比较好写,只需要将节点作为红色节点插入(保证不违反性质6,但可能违反性质5,毕竟性质5比性质6容易修正),然后判断是否出现双红现象,修正该节点即可。

template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::insert(T v) {
    Node* ptn = find(v, 1);
    if(_hot == NULL) {
        init(v);
        return iterator(_root);
    }
    ptn = new Node(v, true, _hot, NULL, NULL, 1);
    if( _hot->val <= v  )
        _hot->rc = ptn;
    else
        _hot->lc = ptn;
    SolveDoubleRed(ptn);
    return iterator(ptn);
}

template <typename T>
void redblacktree<T>::init(T v) {
    _root = new Node(v, false, NULL, NULL, NULL, 1);
#ifdef __REDBLACK_DEBUG
    ++blackheight;
#endif
}

此处使用了函数find,和rfind一样,第一个参数是待寻找值,第二个参数是每个路过的节点域的增加值(插入为1,删除为-1,普通查找为0):

template <typename T>
typename
redblacktree<T>::Node* redblacktree<T>::find(T v, const int op) {
    Node* ptn = _root;  ////从根节点开始查找
    _hot = NULL;    ////维护父亲节点
    while(ptn != NULL) {
        _hot = ptn;
        ptn->s += op;
        if(ptn->val > v)
            ptn = ptn->lc;
        else
            ptn = ptn->rc;
    }
    return ptn;
}

template <typename T>
typename
redblacktree<T>::Node* redblacktree<T>::rfind(T v, const int op) {
    Node* ptn = _root;
    _hot = NULL;
    while(ptn != NULL && ptn->val != v) {
        _hot = ptn;
        ptn->s += op;
        if(ptn->val > v)
            ptn = ptn->lc;
        else
            ptn = ptn->rc;
    }
    return ptn;
}

双红修正

至于双红修正,可以分为以下三种情况:

1.没有出现双红。

这一点很重要,一定要加在SolveDoubleRed()里面判断,因为不论是直接插入还是上溢都有可能出现这种情况。

直接return返回就好,不解释……

2.父亲为红色(则父亲非根,祖父非空),叔叔bro(父亲)为黑色(注意:可能是叶子NULL,需要判断;祖父可能是根,需要判断)。(RR-1)

若修正节点x是祖父g的左儿子的左儿子或右儿子的右儿子(即互为同向祖孙关系),将g单旋一次(将x的父亲p伸展到g位置),再将g染红、p染黑即可;若x不是g的同向孙子,需要将x的父亲p旋转一次,再旋转g一次(将x伸展到g位置),最后将g染红、x染黑即可。

3.父亲为红色,叔叔为红色。(RR-2)

双红修正中唯一需要迭代或递归的情况。将祖父g染红、叔叔u和父亲p染黑,双红缺陷就会上溢两层,下一步就是修正g的双红缺陷啦!

但要注意的是,g有可能是树根。如果这种情况上溢到了树根,只需要将g再染黑即可,此时全树黑高度增加1。虽然这样可能会遍历整棵树的O(log n)个节点,但是分摊意义下,SolveDoubleRed()的时间复杂度为O(1)。可以用势能分析法证明。

因此可以轻松写出SolveDoubleRed()函数啦:

template <typename T>
void redblacktree<T>::SolveDoubleRed(Node* nn) {
    while((!(nn->ftr)) || nn->ftr->RBc) {
        if(nn == _root) {
            _root->RBc = false;
#ifdef __REDBLACK_DEBUG
            ++blackheight;
#endif
            return;
        }
        Node* pftr = nn->ftr;
        if(!(pftr->RBc)) return;            ////No double-red
        Node* uncle = bro(nn->ftr);
        Node* grdftr = nn->ftr->ftr;
        if(uncle != NULL && uncle->RBc) {   ////RR-2
            grdftr->RBc = true;
            uncle->RBc = false;
            pftr->RBc = false;
            nn = grdftr;
        } else {                            ////RR-1
            if(islc(pftr)) {
                if(islc(nn)) {
                    pftr->ftr = grdftr->ftr;
                    if(grdftr == _root) _root = pftr;
                    else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = pftr;
                    else grdftr->ftr->rc = pftr;
                    connect34(pftr, nn, grdftr, nn->lc, nn->rc, pftr->rc, uncle);
                    pftr->RBc = false;
                    grdftr->RBc = true;
                } else {
                    nn->ftr = grdftr->ftr;
                    if(grdftr == _root) _root = nn;
                    else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = nn;
                    else grdftr->ftr->rc = nn;
                    connect34(nn, pftr, grdftr, pftr->lc, nn->lc, nn->rc, uncle);
                    nn->RBc = false;
                    grdftr->RBc = true;
                }
            } else {
                if(islc(nn)) {
                    nn->ftr = grdftr->ftr;
                    if(grdftr == _root) _root = nn;
                    else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = nn;
                    else grdftr->ftr->rc = nn;
                    connect34(nn, grdftr, pftr, uncle, nn->lc, nn->rc, pftr->rc);
                    nn->RBc = false;
                    grdftr->RBc = true;
                } else {
                    pftr->ftr = grdftr->ftr;
                    if(grdftr == _root) _root = pftr;
                    else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = pftr;
                    else grdftr->ftr->rc = pftr;
                    connect34(pftr, grdftr, nn, uncle, pftr->lc, nn->lc, nn->rc);
                    pftr->RBc = false;
                    grdftr->RBc = true;
                }
            }
            return;
        }
    }
}

统一重平衡

为了简化代码,旋转操作都使用了统一重平衡函数connect34()


template <typename T>
void redblacktree<T>::connect34(    Node* nroot,    Node* nlc,      Node* nrc,
                                    Node* ntree1,   Node* ntree2,   Node* ntree3,   Node* ntree4) {
    nlc->lc = ntree1;
    if(ntree1 != NULL) ntree1->ftr = nlc;
    nlc->rc = ntree2;
    if(ntree2 != NULL) ntree2->ftr = nlc;
    nrc->lc = ntree3;
    if(ntree3 != NULL) ntree3->ftr = nrc;
    nrc->rc = ntree4;
    if(ntree4 != NULL) ntree4->ftr = nrc;
    nroot->lc = nlc;
    nlc->ftr = nroot;
    nroot->rc = nrc;
    nrc->ftr = nroot;
    nlc->maintain();
    nrc->maintain();
    nroot->maintain();
}

两种bound

lower_bound(v)、upper_bound(v)两个函数,分别返回红黑树中不大于v的最大的元素、大于v的最小的元素。可以用rfind(v, 0)实现,但此处注重效率,可以另写查找算法:

template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::lower_bound(T v) {
    Node* ptn = _root;
    while(ptn) {
        _hot = ptn;
        if(ptn->val < v) {
            ptn = ptn->rc;
        } else {
            ptn = ptn->lc;
        }
    }
    if(_hot->val < v) {
        ptn = _hot;
    } else {
        ptn = _hot->left_node();
    }
    return iterator(ptn);
}

template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::upper_bound(T v) {
    Node* ptn = _root;
    while(ptn) {
        _hot = ptn;
        if(ptn->val > v) {
            ptn = ptn->lc;
        } else {
            ptn = ptn->rc;
        }
    }
    if(_hot->val > v) {
        ptn = _hot;
    } else {
        ptn = _hot->right_node();
    }
    return iterator(ptn);
}

寻找第k大

就像快速选择一样,非常简单对不对?

template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::kth(int rank) {
    return iterator(findkth(rank, _root));
}

template <typename T>
typename
redblacktree<T>::Node* redblacktree<T>::findkth(int rank, Node* ptn) {
    if(!(ptn->lc)) {
        if(rank == 1) {
            return ptn;
        } else {
            return findkth(rank - 1, ptn->rc);
        }
    } else {
        if(ptn->lc->s == rank - 1) return ptn;
        else if(ptn->lc->s >= rank) return findkth(rank, ptn->lc);
        else return findkth(rank - (ptn->lc->s) - 1, ptn->rc);
    }
}

找到元素的名次

更简单了有木有?

template <typename T>
int redblacktree<T>::get_rank(T v) {
    return find_rank(v, _root);
}

template <typename T>
int redblacktree<T>::find_rank(T v, Node* ptn) {
    if(!ptn) return 1;
    else if(ptn->val >= v) return find_rank(v, ptn->lc);
    else return (1 + ((ptn->lc) ? (ptn->lc->s) : 0) + find_rank(v, ptn->rc));
}

其他接口

介绍删除之前,我们可以做一些比较简单的接口操作,如size()、empty()。

template <typename T>
int redblacktree<T>::size() {
    return _root->s;
}

template <typename T>
bool redblacktree<T>::empty() {
    return !_root;
}

删除、双黑现象及其修正

俗话说:老鼠拉木锨,大头在后边。删除和双黑修正是红黑树最令人恶心和窒息的操作,许多大学教材对此闭口不谈,连清华的《数据结构》也讲述地十分混乱(但编者邓俊辉教授绝对是我的恩人,2017提高组NOIP考试之前偶然瞥了一眼《数据结构》里面的希尔排序那一章,里面一个数论问题吸引了我的注意,于是我不经意间记下了那个公式:x(g, h) = g*h - g - h,第二天看到题我笑了,AC了D1T1)。

不说我的故事了,也不说邓教授的书了,下面直接进删除:

template <typename T>
bool redblacktree<T>::remove(T v) {
    Node* ptn = rfind(v, -1);
    if(!ptn) return false;
    Node* node_suc;
    while(ptn->lc || ptn->rc) { ////迭代寻找真后继
        if(!(ptn->lc)) {
            node_suc = ptn->rc;
        } else if(!(ptn->rc)) {
            node_suc = ptn->lc;
        } else {
            node_suc = ptn->succ();
        }
        --(ptn->s);
        ptn->val = node_suc->val;
        ptn = node_suc;
    }
    if(!(ptn->RBc)) {
        --(ptn->s);
        SolveDoubleBlack(ptn);
    }
    if(ptn == _root) {
        _root = NULL;
        delete ptn;
        return true;
    }
    if(ptn->ftr->lc == ptn)
        ptn->ftr->lc = NULL;
    else
        ptn->ftr->rc = NULL;
    delete ptn;
    return true;
}

看似非常简单对不对?只是因为我没有给出那一百来行的SolveDoubleBlack()代码……

双黑修正

双黑修正比较厉害,情况一共四种,同样只有一种情况需要迭代或递归。双黑修正不容易理解的就是SolveDoubleBlack(Node* x)的参数x。必黑的节点x代表,x的左右儿子黑高度均相等,即若以x作为根,子树x并不存在双黑缺陷,但x比兄弟bro(x)的黑高度少1,因此需要修正。

双黑修正的4种情况如下:

1.兄弟为红色(BB-1)

许多教材将此情况最后判断,同时也认为是需要递归的情况,但我认为不必,首先判断这个情况,可以兼顾效率和代码可读性。

旋转父亲p,将b伸展到p位置,然后染黑b、染红p,于是将问题转化到了BB-2R或BB-3。

2.兄弟和父亲都为黑色,且兄弟没有红儿子(BB-2B)

根据我的跟踪记录,在一些插入操作居多的数据(如百科词条、医院药品记录、核电站控制系统等现实情况),此情况几乎不会发生,但只要出现全树黑高度减少1的情况,BB-2B就一定发生且下溢到根节点了。

染红兄弟b,双黑缺陷下溢到了父亲p,问题转化为了BB-1、BB-2B、BB-2R或BB-3中的一个。

如果被修正节点为根节点,只需要直接返回即可,此时全树黑高度减少1。

3.兄弟是黑色,没有红儿子,父亲为红色(BB-2R)

相当简单了吧,不用我介绍,聪明的读者应该也能想到:

染红b,染黑p,然后就完成修正了。

4.兄弟是黑色,有红儿子(BB-3)

同样不需要转化问题:

如果侄子c是父亲p的同向孙子的话,旋转p使兄弟b伸展到p位置,并将b染为p的颜色,p、c染黑即可;如果c不是p的同向孙子,伸展c到p的位置,并将c染为p的颜色,然后染黑p即可。

于是双黑修正SolveDoubleBlack的代码也很容易写出啦:

template <typename T>
void redblacktree<T>::SolveDoubleBlack(Node* nn) {
    while(nn != _root) {
        Node* pftr = nn->ftr;
        Node* bthr = bro(nn);
        if(bthr->RBc) {                 ////BB-1
            bthr->RBc = false;
            pftr->RBc = true;
            if(_root == pftr) _root = bthr;
            if(pftr->ftr) {
                if(pftr->ftr->lc == pftr)
                    pftr->ftr->lc = bthr;
                else
                    pftr->ftr->rc = bthr;
            }
            bthr->ftr = pftr->ftr;
            if(islc(nn)) {
                connect34(bthr, pftr, bthr->rc, nn, bthr->lc, bthr->rc->lc, bthr->rc->rc);
            } else {
                connect34(bthr, bthr->lc, pftr, bthr->lc->lc, bthr->lc->rc, bthr->rc, nn);
            }
            bthr = bro(nn);
            pftr = nn->ftr;
        }
        if(bthr->lc && bthr->lc->RBc) { ////BB-3
            bool oldRBc = pftr->RBc;
            pftr->RBc = false;
            if(pftr->lc == nn) {
                if(pftr->ftr) {
                    if(pftr->ftr->lc == pftr)
                        pftr->ftr->lc = bthr->lc;
                    else
                        pftr->ftr->rc = bthr->lc;
                }
                bthr->lc->ftr = pftr->ftr;
                if(_root == pftr) _root = bthr->lc;
                connect34(bthr->lc, pftr, bthr, pftr->lc, bthr->lc->lc, bthr->lc->rc, bthr->rc);
            } else {
                bthr->lc->RBc = false;
                if(pftr->ftr) {
                    if(pftr->ftr->lc == pftr)
                        pftr->ftr->lc = bthr;
                    else
                        pftr->ftr->rc = bthr;
                }
                bthr->ftr = pftr->ftr;
                if(_root == pftr) _root = bthr;
                connect34(bthr, bthr->lc, pftr, bthr->lc->lc, bthr->lc->rc, bthr->rc, pftr->rc);
            }
            pftr->ftr->RBc = oldRBc;
            return;
        } else if(bthr->rc && bthr->rc->RBc) {  ////BB-3
            bool oldRBc = pftr->RBc;
            pftr->RBc = false;
            if(pftr->lc == nn) {
                bthr->rc->RBc = false;
                if(pftr->ftr) {
                    if(pftr->ftr->lc == pftr)
                        pftr->ftr->lc = bthr;
                    else
                        pftr->ftr->rc = bthr;
                }
                bthr->ftr = pftr->ftr;
                if(_root == pftr) _root = bthr;
                connect34(bthr, pftr, bthr->rc, pftr->lc, bthr->lc, bthr->rc->lc, bthr->rc->rc);
            } else {
                if(pftr->ftr) {
                    if(pftr->ftr->lc == pftr)
                        pftr->ftr->lc = bthr->rc;
                    else
                        pftr->ftr->rc = bthr->rc;
                }
                bthr->rc->ftr = pftr->ftr;
                if(_root == pftr) _root = bthr->rc;
                connect34(bthr->rc, bthr, pftr, bthr->lc, bthr->rc->lc, bthr->rc->rc, pftr->rc);
            }
            pftr->ftr->RBc = oldRBc;
            return;
        }
        if(pftr->RBc) {                 ////BB-2R
            pftr->RBc = false;
            bthr->RBc = true;
            return;
        } else {                        ////BB-2B
            bthr->RBc = true;
            nn = pftr;
        }
    }
#ifdef __REDBLACK_DEBUG
    --blackheight;
#endif
}

Debug的代码

为了方便调试,我在写红黑树板子的同时也写了一些调试代码:

#ifdef __REDBLACK_DEBUG

int blackheight(0);

template <typename T>   ////先序遍历
void redblacktree<T>::previs(Node* ptn, int cnt) {
    if(ptn == NULL) {
        if(blackheight == -1) blackheight = cnt;
        assert(blackheight == cnt);
        return;
    }
    printf("%d %s %d \n", ptn->val, ptn->RBc ? "Red" : "Black", ptn->s);
    if(!(ptn->RBc)) ++cnt;
    previs(ptn->lc, cnt);
    previs(ptn->rc, cnt);
}

template <typename T>   ////中序遍历
void redblacktree<T>::invis(Node* ptn, int cnt) {
    if(ptn == NULL) {
        if(blackheight == -1) blackheight = cnt;
        assert(blackheight == cnt);
        return;
    }
    if(!(ptn->RBc)) ++cnt;
    invis(ptn->lc, cnt);
    printf("%d %s %d \n", ptn->val, ptn->RBc ? "Red" : "Black", ptn->s);
    invis(ptn->rc, cnt);
}

template <typename T>   ////后序遍历
void redblacktree<T>::postvis(Node* ptn, int cnt) {
    if(ptn == NULL) {
        if(blackheight == -1) blackheight = cnt;
        assert(blackheight == cnt);
        return;
    }
    if(!(ptn->RBc)) ++cnt;
    postvis(ptn->lc, cnt);
    postvis(ptn->rc, cnt);
    printf("%d %s %d \n", ptn->val, ptn->RBc ? "Red" : "Black", ptn->s);
}

template <typename T>   ////输出所有序遍历的接口
void redblacktree<T>::vis() {
    printf("BlackHeight:\t%d\n", blackheight);
    printf("------pre-vis------\n");
    previs(_root, 0);
    printf("------in-vis------\n");
    invis(_root, 0);
    printf("------post-vis------\n");
    postvis(_root, 0);
}

template <typename T>   ////验证所有节点与父亲的连接是否正常、域s是否维护正常
void redblacktree<T>::checkconnect(Node* ptn) {
    if(!ptn) return;
    assert(ptn->s > 0);
    if(ptn->lc && ptn->lc->ftr != ptn) {
        printf("Oops! %d has a lc %d, but it failed to point its ftr!\n", ptn->val, ptn->lc->val);
    }
    if(ptn->rc && ptn->rc->ftr != ptn) {
        printf("Oops! %d has a rc %d, but it failed to point its ftr!\n", ptn->val, ptn->rc->val);
    }
    int sss = ptn->s;
    if(ptn->lc) sss -= ptn->lc->s;
    if(ptn->rc) sss -= ptn->rc->s;
    if(sss - 1) {
        printf("Damn! %d's size is %d, but the sum of its children's size is %d!\n", ptn->val, ptn->s, ptn->s - sss);
    }
    checkconnect(ptn->lc);
    checkconnect(ptn->rc);
}

template <typename T>
void redblacktree<T>::correctlyconnected() {
    checkconnect(_root);
}
#endif

主程序

板子都有了,这个最好写了不是?

inline
int readint() {
    int ret(0);
    int sgn(1);
    char c;
    while(isspace(c = getchar()));
    if(c == '-') {
        sgn = -1;
        c = getchar();
    }
    while(isdigit(c)) {
        ret = (ret << 3) + (ret << 1) + c - '0';
        c = getchar();
    }
    return ret * sgn;
}
#define ri readint()

int opt, x;

int tot;

redblacktree<int> my_tree;

int main() {
    register int i;
    tot = ri;
    redblacktree<int>::iterator it;
    for(i = 0; i < tot; ++i) {
        opt = ri;
        x = ri;
        switch(opt) {
            case 1:
                my_tree.insert(x);
                break;
            case 2:
                my_tree.remove(x);
                break;
            case 3:
                printf("%d\n", my_tree.get_rank(x));
                break;
            case 4:
                it = my_tree.kth(x);
                printf("%d\n", *it);
                break;
            case 5:
                it = my_tree.lower_bound(x);
                printf("%d\n", *it);
                break;
            case 6:
                it = my_tree.upper_bound(x);
                printf("%d\n", *it);
                break;
            default:
                break;
        }
    }

    return 0;
}

总结

红黑树应该是除哈希表外最快的搜索结构了(哈希表由于占内存太大,实际情况常常不用)。很多人认为红黑树太难写,就放弃学习它。我认为红黑树代码并不麻烦,和线段树的难度差不多,如果学会了会很容易写出来。

写于2018年2月15日,祝大家除夕快乐,拜个早年。

评论

  • strangeDDDF
    这么好的模板没人看吗?
  • Copen
    超级喜欢这一个[欢呼雀跃]
  • Juan_feng
    +1
  • Juan_feng
    从这个学会的平衡树
  • tuchen
    图在哪啊。。
  • ArachnidaQueen
    请滚到上面去碾压那些几十上百赞的!!%%%
  • G坑
    最清晰,没有之一 orz
  • G坑
    %%%, 为什么不置顶
  • _自动AC机_
    ORZ~
  • _自动AC机_
    大家顶上去
作者: 天上一颗蛋 更新时间: 2018-06-13 13:54  在Ta的博客查看 举报    184  

平衡树的板题,用Treap实现。

具体参见注释,写的很详细了,包括了原理,实现以及注意事项

蒟蒻写个注释板子写了两天,太弱了QAQ

感谢niiick指导

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
typedef long long LL;
using namespace std;
int RD(){
    int out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
//第一次打treap,不压行写注释XD
const int maxn = 1000019,INF = 1e9;
//平衡树,利用BST性质查询和修改,利用随机和堆优先级来保持平衡,把树的深度控制在log N,保证了操作效率
//基本平衡树有以下几个比较重要的函数:新建,插入,删除,旋转
//节点的基本属性有val(值),dat(随机出来的优先级)
//通过增加属性,结合BST的性质可以达到一些效果,如size(子树大小,查询排名),cnt(每个节点包含的副本数)等
int na;
int ch[maxn][2];//[i][0]代表i左儿子,[i][1]代表i右儿子
int val[maxn],dat[maxn];
int size[maxn],cnt[maxn];
int tot,root;
int New(int v){//新增节点,
    val[++tot] = v;//节点赋值
    dat[tot] = rand();//随机优先级
    size[tot] = 1;//目前是新建叶子节点,所以子树大小为1
    cnt[tot] = 1;//新建节点同理副本数为1
    return tot;
    }
void pushup(int id){//和线段树的pushup更新一样
    size[id] = size[ch[id][0]] + size[ch[id][1]] + cnt[id];//本节点子树大小 = 左儿子子树大小 + 右儿子子树大小 + 本节点副本数
    }
void build(){
    root = New(-INF),ch[root][1] = New(INF);//先加入正无穷和负无穷,便于之后操作(貌似不加也行)
    pushup(root);//因为INF > -INF,所以是右子树,
    }
void Rotate(int &id,int d){//id是引用传递,d(irection)为旋转方向,0为左旋,1为右旋
    int temp = ch[id][d ^ 1];//旋转理解:找个动图看一看就好(或参见其他OIer的blog)
    ch[id][d ^ 1] = ch[temp][d];//这里讲一个记忆技巧,这些数据都是被记录后马上修改
    ch[temp][d] = id;//所以像“Z”一样
    id = temp;//比如这个id,在上一行才被记录过,ch[temp][d]、ch[id][d ^ 1]也是一样的
    pushup(ch[id][d]),pushup(id);//旋转以后size会改变,看图就会发现只更新自己和转上来的点,pushup一下,注意先子节点再父节点
    }//旋转实质是({在满足BST的性质的基础上比较优先级}通过交换本节点和其某个叶子节点)把链叉开成二叉形状(从而控制深度),可以看图理解一下
void insert(int &id,int v){//id依然是引用,在新建节点时可以体现
    if(!id){
        id = New(v);//若节点为空,则新建一个节点
        return ;
        }
    if(v == val[id])cnt[id]++;//若节点已存在,则副本数++;
    else{//要满足BST性质,小于插到左边,大于插到右边
        int d = v < val[id] ? 0 : 1;//这个d是方向的意思,按照BST的性质,小于本节点则向左,大于向右
        insert(ch[id][d],v);//递归实现
        if(dat[id] < dat[ch[id][d]])Rotate(id,d ^ 1);//(参考一下图)与左节点交换右旋,与右节点交换左旋
        }
    pushup(id);//现在更新一下本节点的信息
    }
void Remove(int &id,int v){//最难de部分了
    if(!id)return ;//到这了发现查不到这个节点,该点不存在,直接返回
    if(v == val[id]){//检索到了这个值
        if(cnt[id] > 1){cnt[id]--,pushup(id);return ;}//若副本不止一个,减去一个就好
        if(ch[id][0] || ch[id][1]){//发现只有一个值,且有儿子节点,我们只能把值旋转到底部删除
            if(!ch[id][1] || dat[ch[id][0]] > dat[ch[id][1]]){//当前点被移走之后,会有一个新的点补上来(左儿子或右儿子),按照优先级,优先级大的补上来
                Rotate(id,1),Remove(ch[id][1],v);//我们会发现,右旋是与左儿子交换,当前点变成右节点;左旋则是与右儿子交换,当前点变为左节点
                }
            else Rotate(id,0),Remove(ch[id][0],v);
            pushup(id);
            }
        else id = 0;//发现本节点是叶子节点,直接删除
        return ;//这个return对应的是检索到值de所有情况
        }
    v < val[id] ? Remove(ch[id][0],v) : Remove(ch[id][1],v);//继续BST性质
    pushup(id);
    }
int get_rank(int id,int v){
    if(!id)return 0;//若查询值不存在,返回
    if(v == val[id])return size[ch[id][0]] + 1;//查询到该值,由BST性质可知:该点左边值都比该点的值(查询值)小,故rank为左儿子大小 + 1
    else if(v < val[id])return get_rank(ch[id][0],v);//发现需查询的点在该点左边,往左边递归查询
    else return size[ch[id][0]] + cnt[id] + get_rank(ch[id][1],v);//若查询值大于该点值。说明询问点在当前点的右侧,且此点的值都小于查询值,所以要加上cnt[id]
    }
int get_val(int id,int rank){
    if(!id)return INF;//一直向右找找不到,说明是正无穷
    if(rank <= size[ch[id][0]])return get_val(ch[id][0],rank);//左边排名已经大于rank了,说明rank对应的值在左儿子那里
        else if(rank <= size[ch[id][0]] + cnt[id])return val[id];//上一步排除了在左区间的情况,若是rank在左与中(目前节点)中,则直接返回目前节点(中区间)的值
    else return get_val(ch[id][1],rank - size[ch[id][0]] - cnt[id]);//剩下只能在右区间找了,rank减去左区间大小和中区间,继续递归
    }
int get_pre(int v){
    int id = root,pre;//递归不好返回,以循环求解
    while(id){//查到节点不存在为止
        if(val[id] < v)pre = val[id],id = ch[id][1];//满足当前节点比目标小,往当前节点的右侧寻找最优值
        else id = ch[id][0];//无论是比目标节点大还是等于目标节点,都不满足前驱条件,应往更小处靠近
        }
    return pre;
    }
int get_next(int v){
    int id = root,next;
    while(id){
        if(val[id] > v)next = val[id],id = ch[id][0];//同理,满足条件向左寻找更小解(也就是最优解)
        else id = ch[id][1];//与上方同理
        }
    return next;
    }
int main(){
    build();//不要忘记初始化[运行build()会连同root一并初始化,所以很重要]
    na = RD();
    for(int i = 1;i <= na;i++){
        int cmd = RD(),x = RD();
        if(cmd == 1)insert(root,x);//函数都写好了,注意:需要递归的函数都从根开始,不需要递归的函数直接查询
        else if(cmd == 2)Remove(root,x);
        else if(cmd == 3)printf("%d\n",get_rank(root,x) - 1);//注意:因为初始化时插入了INF和-INF,所以查询排名时要减1(-INF不是第一小,是“第零小”)
            else if(cmd == 4)printf("%d\n",get_val(root,x + 1));//同理,用排名查询值得时候要查x + 1名,因为第一名(其实不是)是-INF
        else if(cmd == 5)printf("%d\n",get_pre(x));
        else if(cmd == 6)printf("%d\n",get_next(x));
        }
    return 0;
    }

评论

  • ww3113306
    能不能解释一下各个数组是存了些什么?
  • zhaoyifan
    博主好板子(●'◡'●)
  • Brave_Cattle
    博主讲的可以,要是能多一些关于变量的解释就更好了
  • 尊者祀雪
    不错
  • hacker047
    虽然板子好,但是缩行太严重..................
  • jinbo8848
    orz
  • XSamsara
    我喜欢这种格式
  • lzqwq
    orz神板子
  • pechpo
    神板子
  • drophell
    超喜欢
作者: litble 更新时间: 2017-07-10 13:55  在Ta的博客查看 举报    135  

我是用了当treap模板题做的。

解释一下变量吧......s(x,0)表示左儿子,s(x,1)表示右儿子,siz是子树的大小,w是当前点的权值,pos是随机出来的一个值,用于保证treap的尽量平衡。

有人说我缩行严重QAQ......?我明明没有一行超过了80行被D线的......而且同一行的语句从逻辑上来说是有关联的啊......?

treap的旋转操作:

void up(int i){siz[i]=siz[s[i][0]]+siz[s[i][1]]+1;}
void spin(int &i,int p){
    int t=s[i][p];
    s[i][p]=s[t][!p],s[t][!p]=i,up(i),up(t),i=t;
}

那么讲讲treap做法:

1.插入:给每个点随机一个优先级,然后如果子节点的优先级要小于父节点,我们就把子节点旋转上去。

void ins(int x,int &i){
    if(!i){i=++tot,siz[i]=1,w[i]=x,pos[i]=rand();return;}
    siz[i]++;
    if(x<=w[i]){ins(x,s[i][0]);if(pos[s[i][0]]<pos[i])spin(i,0);}
    else {ins(x,s[i][1]);if(pos[s[i][1]]<pos[i])spin(i,1);}
}

2.删除:将这个点优先级小的子节点旋转上来,一直将其旋到叶子,然后删除。

void del(int x,int &i){
    if(w[i]==x){
        if(s[i][0]*s[i][1]==0){i=s[i][0]+s[i][1];return;}
        if(pos[s[i][0]]>pos[s[i][1]]){spin(i,1);del(x,s[i][0]);}
        else {spin(i,0);del(x,s[i][1]);}
    }
    else if(w[i]>x)del(x,s[i][0]);
    else del(x,s[i][1]);
    up(i);
}

3.查找x数的排名

只要维护左右子树的大小就可以了,但是要注意一点:因为我们查询的是最小的排名,所以当我们查到x数的时候,不应该之间返回,而应该递归下去,直到到达0为止(开始就是因为这个才WA的,也注意不要写如果其左儿子还是x就继续递归否则返回,因为可能还有x在其左儿子的右子树中。)

int find(int x,int i){
    if(!i)return 1;
    if(w[i]>=x)return find(x,s[i][0]);
    return find(x,s[i][1])+siz[s[i][0]]+1;
}

4.查找排名为x的数

这个就更简单了不是吗?

int ask(int x,int i){
    if(siz[s[i][0]]==x-1)return w[i];
    if(siz[s[i][0]]>=x)return ask(x,s[i][0]);
    return ask(x-siz[s[i][0]]-1,s[i][1]);
}

5/6:查找前驱/后继

前驱:找到一个比x小的数,就记录这个数并判断这个数的右子树(比这个数大的数)中是否还有比x小的数。如果没找到,就往左子树中继续找。

后继同理。

int pre(int x,int i){
    if(!i)return -2000000005;
    if(w[i]<x)return max(w[i],pre(x,s[i][1]));
    else return pre(x,s[i][0]);
}
int nxt(int x,int i){
    if(!i)return 2000000005;
    if(w[i]>x)return min(w[i],nxt(x,s[i][0]));
    else return nxt(x,s[i][1]);
}

评论

  • 御坂20001号
    还没有评论
  • 御坂20001号
    ????
  • 持之以珩400ACpj
    666
  • AgOH
    666
  • wenjing233
    excause me?
  • 孑彧
    %%%%%%%%tql
  • 废柴叔丿
    ????
  • shao_ping
    emm?
  • 废柴叔丿
    exm???
  • SCuP
    ???
作者: Alpha 更新时间: 2018-12-11 15:41  在Ta的博客查看 举报    99  

UPDATE:额外增加了内容

vector 解法

25行实现普通平衡树,你值得拥有。

这里我解释一下,vector能过绝非基于数据很水

vector作为STL的一种容器,支持insert,erase,下标访问等多种操作。

操作1:为了维护序列有序性,我们要将元素插在特定的位置,复杂度O(n)

操作2:同操作1

操作3:我们可以二分该数的位置来求出排名,复杂度O(log(n))

操作4:直接访问下标,复杂度O(1)

操作5:同操作3

操作6:同操作5

可以看出这个算法的复杂度为O(nQ)

但是vector本身其实做了很多针对机器底层的优化,而且vector直接对内存操作,比一般的数组不知快了多少。

经过测试,vector在平衡树维护,平衡树合并,线段树套平衡树中表现优异,并不因数据强度而改变其特性。

所以以后各位不用学普通平衡树了

#include <bits/stdc++.h>
#define L lower_bound(A.begin(),A.end(),x)
#define R upper_bound(A.begin(),A.end(),x)
using namespace std;
int main()
{
    vector<int> A;
    int T;
    cin>>T;
    while(T--)
    {
        int opt,x;
        cin>>opt>>x;
        switch(opt)
        {
            case 1:A.insert(L,x);break;
            case 2:A.erase(L);break;
            case 3:cout<<(L-A.begin())+1<<endl;break;
            case 4:cout<<A[x-1]<<endl;break;
            case 5:cout<<*(--L)<<endl;break;
            case 6:cout<<*R<<endl;break;
        }
    }
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。