摸鱼第一,干活第二

It's time for BOOM!(ノ≧∀≦)ノ

【树】Treap——学习笔记

Treap

这是一种非常常用且非常简单易懂的平衡树数据结构,我们知道对于二叉搜索树来说像堆一样的节点结构无疑是最省时的,平均复杂度基本上都是\(O(\log_{2}n)\),而我们可以以此联想到堆——同样是一种平均操作复杂度为\(O(\log_{2}n)\)的数据结构,所以就有人聪明地把“树”和“堆”结合起来:

Tree+Heap=Treap

这种神奇的数据结构就是这么来的。


你需要学习的前置姿势

二叉搜索树

想学Treap连二叉搜索树都不懂,可以出门左转学完再来。

想学Treap连堆都不懂,可以出门左转学完再来。

树节点旋转

旋转的含义即:在不破坏二叉搜索树性质的情况下,修改一个节点与左右儿子关系的操作。

你可以让左儿子代替原节点,称之为右旋;让右儿子代替原节点,称之为左旋

旋转的前提条件是这个节点同时拥有左右儿子。

《【树】Treap——学习笔记》

实现并不困难,只是普通的交换操作罢了,但是一定要注意:在旋转完成后要重新统计旋转的两个节点的子树大小

1
2
3
4
5
6
7
8
9
10
11
12
void ltR(int &x){//左旋
    int y=t[x].r;//记录右儿子下标
    t[x].r=t[y].l,t[y].l=x,//交换
    t[y].s=t[x].s,t[x].s=t[t[x].l].s+t[t[x].r].s+t[x].c,//重新统计子树大小
    x=y;
}
void rtR(int &x){//右旋
    int y=t[x].l;//记录左儿子下标
    t[x].l=t[y].r,t[y].r=x,//交换
    t[y].s=t[x].s,t[x].s=t[t[x].l].s+t[t[x].r].s+t[x].c,//重新统计子树大小
    x=y;
}

以上代码具体执行起来是向这样一样的(以右旋为例):

《【树】Treap——学习笔记》

更好的伪随机生成器

因为来自C标准的rand()和srand()生存速度在OI中会存在TLE的危险,所以我们使用随机种子和线性同余法来生成伪随机数。

这种方法的生成公式为:

\(X_{n+1}=(AX_{n}+B)mod\;C\)

需要注意一点:A、B、C需要互质。这样才能保证随机循环节够大。

1
2
3
int rdm(){//伪随机数
    return seed=int((seed*19260817LL+19890604LL)%2147483647LL);//事实证明这种取值可以让你的程序跑的更快
}

Treap的基本操作

插入

与二叉搜索树的插入相仿,不过在每次插入操作执行完后要通过旋转来维护小根堆,以确保树的平衡。

删除

与二叉搜索树的删除相仿,不同的是如果一个要被删除的节点它同时拥有左右儿子时,我们需要使用旋转操作,在维护小根堆的同时,把删除节点移动到叶子节点或只有左儿子或右儿子的地方。

数据查找排名

与二叉搜索树相同。

排名查找数据

与二叉搜索树相同。

查找数据前驱

与二叉搜索树相同。

查找数据后继

与二叉搜索树相同。

其他操作

其他的操作基本上都可以通过少部分修改或者组合使用以上操作来实现。


模板代码

相信你看了上面的解释,Treap有多么简单你应该知道了吧。那么我把这些操作整理成了万用模板,简单易记:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
template<class T>//模板类
class treap{
    private:
        struct node{//数据结构体
            T a;//节点数据
            int l,r,s,c,n;//左儿子、右儿子、子树大小、相同数量、随机值
        } *t;//树结构
        int seed,top;//随机种子、新节点指针

        int rdm(){//伪随机数
            return seed=int((seed*19260817LL+19890604LL)%2147483647LL);
        }
        void ltR(int &x){//左旋
            int y=t[x].r;//记录右儿子下标
            t[x].r=t[y].l,t[y].l=x,//交换
            t[y].s=t[x].s,t[x].s=t[t[x].l].s+t[t[x].r].s+t[x].c,//重新统计子树大小
            x=y;
        }
        void rtR(int &x){//右旋
            int y=t[x].l;//记录左儿子下标
            t[x].l=t[y].r,t[y].r=x,//交换
            t[y].s=t[x].s,t[x].s=t[t[x].l].s+t[t[x].r].s+t[x].c,//重新统计子树大小
            x=y;
        }
    public:
        int root,ans;//根节点、查询返回值

        treap(int a=1,int b=1):t(new node[a]),seed(b),top(0),root(0),ans(0){}//构造函数
        ~treap(){//析构函数
            delete[] t;//释放树结构
        }
        void ins(int &x,T a){//插入
            if(x==0){//如果从叶子结点到达空节点
                x=++top,t[x]={a,0,0,1,1,rdm()};//生成新节点
                return;
            }
            ++t[x].s;//该节点子树大小+1
            if(t[x].a==a)//如果数据相同
                ++t[x].c;//相同数量+1
            else if(t[x].a<a){//如果数据更大
                ins(t[x].r,a);//插入右子树
                if(t[t[x].r].n<t[x].n)//维护小根堆
                    ltR(x);
            }
            else{//如果数据更小
                ins(t[x].l,a);//插入左子树
                if(t[t[x].l].n<t[x].n)//维护小根堆
                    rtR(x);
            }
        }
        void del(int &x,T a){//删除
            if(x==0)//如果找不到
                return;//(╯°Д°)╯︵┻━┻
            if(t[x].a==a){//如果找到
                if(t[x].c>1)//如果有相同数据节点
                    --t[x].s,--t[x].c;//该节点子树大小-1、相同数量-1
                else if((t[x].l==0)||(t[x].r==0))//如果只有左儿子或右儿子
                    x=t[x].l+t[x].r;//该节点用左儿子或右儿子代替
                else if(t[t[x].l].n<t[t[x].r].n)//如果左儿子堆值更小
                    rtR(x),del(x,a);//把节点旋至右子树删除
                else//如果右儿子堆值更小或相等
                    ltR(x),del(x,a);//把节点旋至左子树删除
            }
            else if(t[x].a<a)//如果数据更大
                --t[x].s,del(t[x].r,a);//该节点子树大小-1、到右子树删除
            else//如果数据更小
                --t[x].s,del(t[x].l,a);//该节点子树大小-1、到左子树删除
        }
        int qRnk(int &x,T a){//查找排名
            if(x==0)//如果没找到
                return 0;//(╯°Д°)╯︵┻━┻
            if(t[x].a==a)//如果找到
                return t[t[x].l].s+1;//返回位置
            else if(t[x].a<a)//如果数据更大
                return qRnk(t[x].r,a)+t[t[x].l].s+t[x].c;//递归返回位置
            else//如果数据更小
                return qRnk(t[x].l,a);//递归返回位置
        }
        T qDat(int &x,int a){//查找数据
            if(x==0)//如果没找到
                return T();//(╯°Д°)╯︵┻━┻
            if(a<=t[t[x].l].s)//如果在左子树中
                return qDat(t[x].l,a);//递归返回数据
            else if(t[t[x].l].s+t[x].c<a)//如果在右子树中
                return qDat(t[x].r,a-t[t[x].l].s-t[x].c);//递归返回数据
            else//如果找到
                return t[x].a;//返回数据
        }
        void qPre(int x,T a){//查询前驱
            if(x==0)//如果没找到
                return;//(╯°Д°)╯︵┻━┻
            if(t[x].a<a)//如果数据更大
                ans=x,//记录下标位置
                qPre(t[x].r,a);//到右子树查询
            else//如果数据更小
                qPre(t[x].l,a);//到左子树查询
        }
        void qPst(int x,T a){//查询后驱
            if(x==0)//如果没找到
                return;//(╯°Д°)╯︵┻━┻
            if(t[x].a>a)//如果数据更小
                ans=x,//记录下标位置
                qPst(t[x].l,a);//到左子树查询
            else//如果数据更大
                qPst(t[x].r,a);//到右子树查询
        }
};

【END】


2018.12.15更新内容

发现关于树节点旋转的图左右旋写反了,已修复。
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code