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的博客查看    607  

本题的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的博客查看    149  

看了那么多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
            while(ptn->lc)
                ptn = ptn->lc;
        return ptn;
    }

    Node* right_node() {    ////直接后继
        Node* ptn = this;
        if(!rc) {
            while(ptn->ftr && ptn->ftr->rc == ptn)
                ptn = ptn->ftr;
            ptn = ptn->ftr;
        } else
            while(ptn->rc)
                ptn = ptn->rc;
        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日,祝大家除夕快乐,拜个早年。

评论

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

我是用了当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]);
}

评论

  • ZCDHJ
    STO
  • 加藤惠
    %%%yyb巨佬
  • xzz小蒟蒻
    %%%yyb
  • FlashHu
    %%%
  • newbie314159
    %%%yyb
  • 加藤惠
    %%%yyb
  • 125E591
    大佬,为什么要加insert(-2147483647);insert(+2147483647);啊
  • ༺四༒方༻
    这道题splay比treap慢很多
  • Ouaoan
    %%%yyb
  • williams2002
    下方? 以后能别写什么楼上楼下的嘛,次序会变得呀!
作者: yybyyb 更新时间: 2017-07-30 23:31  在Ta的博客查看    52  

诶诶诶。

今天不知道怎么了,这么想写题解(可能看到楼下两位都是我认识的大佬把)

%%%下方ylx大佬和下下方cyh大佬

一个用pbds。一个正解treap

没关系,再来一个splay

就这样吧,splay做这道题会比treap快一些把??

splay不断调整自身,达到尽可能平衡的目的

从而防止树退化成链,然后使得O(logn)的复杂度变为了O(n)

splay相比于其他的平衡树已经是非常好写了(尽管我现在还是自己打不出来)

但是只要能够理解他的思路,splay也不是很难。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

#define MAX 500100
int root=0,N,tot=0;

inline int read()
{
       register int x=0,t=1;
       register char ch=getchar();
       while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
       if(ch=='-'){t=-1;ch=getchar();}
       while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
       return x*t;
}

struct Node
{
       int ch[2];//子节点
       int ff;//父节点 
       int cnt;//数量
       int val;//值 
       int son;//儿子数量  
}t[MAX];

void push_up(int u)//计算儿子数 
{
       t[u].son=t[t[u].ch[0]].son+t[t[u].ch[1]].son+t[u].cnt;
}

void rotate(int x)//旋转 
{
       register int y=t[x].ff;
       register int z=t[y].ff;
       register int k=t[y].ch[1]==x;//x是y的左或右儿子
       t[z].ch[t[z].ch[1]==y]=x;  t[x].ff=z;
       t[y].ch[k]=t[x].ch[k^1];   t[t[x].ch[k^1]].ff=y;
       t[x].ch[k^1]=y;              t[y].ff=x;
       push_up(y);push_up(x);   
}

void Splay(int x,int goal)//把x节点旋转到目标位置
{
       while(t[x].ff!=goal)
       {
                 int y=t[x].ff;
                 int z=t[y].ff;
                 if(z!=goal)//旋转  
                    (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
                 rotate(x);
       }
       if(goal==0)
           root=x;//当前的根节点 
}

void insert(int x)//插入x
{
       int u=root,ff=0;
       while(u&&t[u].val!=x)
       {
                 ff=u;
                 u=t[u].ch[x>t[u].val];
       }
       if(u)//已经有这个数字了  
          t[u].cnt++;//计算数字个数 
       else//不存在这个数字,加入新的节点 
       {
                  u=++tot;//总的节点数
               if(ff)
                   t[ff].ch[x>t[ff].val]=u;
               t[tot].ch[0]=0;
               t[tot].ch[1]=0;
               t[tot].ff=ff;  t[tot].val=x;
               t[tot].cnt=1;  t[tot].son=1;
       }
       Splay(u,0);
}

void Find(int x)//查找x的位置 
{
       int u=root;
       if(!u)return;//不存在节点,无法查找排名
       while(t[u].ch[x>t[u].val]&&x!=t[u].val)//找到x所在的位置 
          u=t[u].ch[x>t[u].val]; 
       Splay(u,0);

}

int Next(int x,int f)//查找前驱/后继
{
       Find(x);//查找x的位置(Splay操作到根节点) 
       int u=root;
       if((t[u].val>x&&f)||(t[u].val<x&&!f))return u;//返回结果 
       u=t[u].ch[f];
       while(t[u].ch[f^1])u=t[u].ch[f^1];
       return u;
}

void Delete(int x)//删除x
{
       int last=Next(x,0);//查找前驱
       int next=Next(x,1);//查找后继
       Splay(last,0);Splay(next,last);
       int del=t[next].ch[0];
       if(t[del].cnt>1)
       {
                 t[del].cnt--;//存在多个这个数字,直接减去一个 
                 Splay(del,0);
       }
       else
          t[next].ch[0]=0;//清除掉节点 
}

int K_th(int x)//查找排名为x的值 
{
       int u=root;
       if(t[u].son<x)//不存在这么多个数 
          return false;
       while(2333)
       {
                int y=t[u].ch[0];
                if(x>t[y].son+t[u].cnt)//在排名在u的后面 
                {
                         x-=t[y].son+t[u].cnt;//直接减掉这么多
                     u=t[u].ch[1];//在右子树中继续找  
                }
                else
                   if(t[y].son>=x)//如果y的节点数多于x 
                       u=y;       //在左子树中继续查找
                else
                    return t[u].val;//否则找到了结果,直接返回 
       }
}
int main()
{
       insert(-2147483647);
       insert(+2147483647);
       N=read();
       while(N--)
       {
                 int opt=read();
                 if(opt==1)
                    insert(read());
                 else
                 if(opt==2)
                    Delete(read());
                 else
                 if(opt==3)
                 {
                      Find(read());
                      printf("%d\n",t[t[root].ch[0]].son);
                 }
                 else
                 if(opt==4)
                      printf("%d\n",K_th(read()+1));
                 else
                 if(opt==5)
                    printf("%d\n",t[Next(read(),0)].val);
                 else
                 if(opt==6)
                    printf("%d\n",t[Next(read(),1)].val);
       }
       return 0;
}

评论

  • da32s1da
    太强啦%%%
  • 白哥小葱
    太强了!!!%%%
  • 锦时
    %%%%%%
  • 锦时
    资瓷资瓷资瓷资瓷
  • sahcudjn
    %%%%%太强了
  • Liu_zj
    大佬太强了!正是我所需要的!%%%
  • wI9znK4f
    后排緇栨
  • zhr1502
    %%%%%%%
  • z3475
    %%%%%%%%%
  • Samurai
    %%%%%%%
作者: 中二攻子 更新时间: 2018-07-18 12:01  在Ta的博客查看    44  

非旋转treap!!!(FHQ Treap)

作为一种平衡树,FHQ Treap不需要旋转!!!

FHQ Treap代码简短,常数比splay小,支持区间操作,而且

可持久化!!

但是网上却很少有FHQ Treap的题解,所以本蒟蒻翻遍了各种博客才学会,所以发一篇题解来帮助大家学习(拯救苍生)

很多人认为它不好理解,但是我认为,FHQ Treap只有两段核心代码(拆分与合并),其他变化呀,操作呀,无脑调用就可以,下面介绍一下FHQ Treap:

与Treap相同,FHQ Treap也维护两个值key和val,key值满足堆的性质(大根或小根),val值满足二叉搜索树的性质(lch<now<rch),这里不再赘述。

与Treap不同的是,这里不再用旋转维护堆的性质,而是在合并的同时维护堆的性质,所以实现了“平衡”,而且这里每个节点只存一个数字,也就是说,不会n个相同元素会有n个点而不是一个节点记录cnt。

操作一:split(拆分)

拆分操作的意思是将一个Treap拆成两个Treap(左树和右树),满足左树的所有值<=val,右树的所有值>val,因为原Treap满足堆的性质,自顶向下拆分后的两个树也会满足堆的性质,所以不需判断,作用将会在之后阐述,具体实现见代码:

void split(int now,int &a,int &b,int val){
    //now原Treap,a左树,b右树,val判定值
    //注意传地址符
    if(now==0){
        a=b=0;//若now=0分割完毕;
        return;
    }
    if(t[now].val<=val)//因为now左子树中的所有值都小于now的值,所以若now属于左树,那么他们都属于左树递归now的右子树;
        a=now,split(t[now].rch,t[a].rch,b,val);//a=now已经使a的右子树=now的右子树,不再递归a的右子树;
        else//同上now右子树也都属于左树,递归左子树;
        b=now,split(t[now].lch,a,t[b].lch,val); 
    update(now);//因为后面会用到左(右)树的siz所以更新维护
}

操作二:merge(合并)

合并操作是将两个Treap a,b(满足a中所有元素均小于b中所有元素),合并成一个Treap,合并的原则是满足堆的性质,所以是一种平衡树, 如果你学过左偏树(可并堆)或斜堆,你将会很容易理解(因为差不多),同样,学会FHQ Treap之后,也会很好理解左偏树和斜堆(废话), 那我们进入正题,代码登场!

void merge(int &now,int a,int b){
    //now新树
    if(a==0||b==0){
        now=a+b;//若某个树已空,则将另一个树整体插入
        return;
    }
    //按照key值合并(堆性质)
    if(t[a].key<t[b].key)//若a树key值<b树,那么b树属于a树的后代,因为b树恒大于a树,那么b树一定属于a树的右后代,a的左子树不变,直接赋给now,递归合并a的右子树和b
        now=a,merge(t[now].rch,t[a].rch,b);
    else
        now=b,merge(t[now].lch,a,t[b].lch);//同理,a树一定是b树的左儿子,递归合并b的左儿子和a
    update(now);
}
//这一段代码有点抽象,实在不能理解可以画图模拟

以上就是FHQ Treap的核心代码,接下来进入无脑拆分合并模式,上本题AC代码!!!(只有100行,超级短!!)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
    int siz,val,key,lch,rch;
}t[100005];
int tot,seed=233,root=1;
int Rand(){//随机key值
    return seed=int(seed*482711ll%2147483647);
}
int NEW(int val){//新建节点
    t[++tot].siz=1;
    t[tot].val=val;
    t[tot].key=Rand();
    t[tot].lch=t[tot].rch=0;
    return tot; 
}
void update(int now){//维护子树大小
    t[now].siz=t[t[now].lch].siz+t[t[now].rch].siz+1;
}
void split(int now,int &a,int &b,int val){//拆分操作
    //now原Treap,a左树,b右树,val判定值
    //注意传地址符
    if(now==0){
        a=b=0;//若now=0分割完毕;
        return;
    }
    if(t[now].val<=val)//因为now左子树中的所有值都小于now的值,所以若now属于左树,那么他们都属于左树递归now的右子树;
        a=now,split(t[now].rch,t[a].rch,b,val);//a=now已经使a的右子树=now的右子树,不再递归a的右子树;
        else//同上now右子树也都属于左树,递归左子树;
        b=now,split(t[now].lch,a,t[b].lch,val); 
    update(now);//因为后面会用到左(右)树的siz所以更新维护
}
void merge(int &now,int a,int b){//合并操作
    //now新树
    if(a==0||b==0){
        now=a+b;//若某个树已空,则将另一个树整体插入
        return;
    }
    //按照key值合并(堆性质)
    if(t[a].key<t[b].key)//若a树key值<b树,那么b树属于a树的后代,因为b树恒大于a树,那么b树一定属于a树的右后代,a的左子树不变,直接赋给now,递归合并a的右子树和b
        now=a,merge(t[now].rch,t[a].rch,b);
    else
        now=b,merge(t[now].lch,a,t[b].lch);//同理,a树一定是b树的左儿子,递归合并b的左儿子和a
    update(now);
} 
void find(int now,int rank){//找第k大
    while(t[t[now].lch].siz+1!=rank){
        if(t[t[now].lch].siz>=rank)
            now=t[now].lch;//若左子树大小大于rank,找左子树
        else
            rank-=(t[t[now].lch].siz+1),now=t[now].rch;//找右子树(rank-左子树大小-树根(大小为1))号的元素
    }
    printf("%d\n",t[now].val);
}
void insert(int val){
    int x=0,y=0,z;
    z=NEW(val);//新建节点z,作为z树
    split(root,x,y,val);//将树分为两部分,x树为<=待插入值,y树大于
    merge(x,x,z);//合并x树和新节点z(树),赋给x树
    merge(root,x,y);//合并新x树和y树,赋给根
    //就这么简单
}
void delet(int val){
    int x=0,y=0,z=0;
    split(root,x,y,val);//分为x树为<=待删除,y树大于
    split(x,x,z,val-1);//x树分为新x树<待删除,z树等于待删除
    merge(z,t[z].lch,t[z].rch);//合并z树左右儿子,赋给z树,即丢弃z树根节点(实现删除)
    merge(x,x,z);
    merge(root,x,y);//合并,不在重复
}
void get_rank(int val){
    int x=0,y=0;
    split(root,x,y,val-1);//分为小于待查找值的x树和大于等于的y树
    printf("%d\n",t[x].siz+1);//即为待查找值的编号
    merge(root,x,y);//合并
} 
void get_val(int rank){
    find(root,rank);//find查找即可
}
void get_pre(int val){
    int x=0,y=0;
    split(root,x,y,val-1);//x树为<=val-1值即小于val值
    find(x,t[x].siz);//在小于val值中找最大的(编号为siz的)就是前驱
    merge(root,x,y);
}
void get_nxt(int val){
    int x=0,y=0;
    split(root,x,y,val);//x树小于等于val值,那么y树大于val值
    find(y,1);//在y树中找最小的,即为后继
    merge(root,x,y);//合并
}
int main(){
    int i,j,k,m;
    NEW(2147483627);//初始虚节点
    t[1].siz=0;//siz为0,不算虚节点的大小
    scanf("%d",&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&j,&k);
        if(j==1)insert(k);
        if(j==2)delet(k);
        if(j==3)get_rank(k);
        if(j==4)get_val(k);
        if(j==5)get_pre(k);
        if(j==6)get_nxt(k);
    }
    return 0;
}

终于写完了,真是不容易,不知不觉本蒟蒻也开始写题解了,如果觉得有帮助的话,记得点赞留言给我点支持哦!