【数据结构】Treap的实现与应用

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】Treap的实现与应用，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

本篇博客作者：czj

Treap的本质是一颗二叉查找树，只是在每个结点上都附加了一个优先级的信息。保证每个点的优先级都比左右儿子小，利用优先级，我们可以把这颗树看成一个小根堆。
Treap树在随机给优先级的情况下，可以在期望O(logn)的时间复杂度里完成：

  • 一个结点的插入。
  • 一个结点的删除。
  • 查询第K大的值。
  • 给定一个值返回它是第几大。

以上四种操作。

那么话不多说，先上模板。这里准备了两个模板，第一个来自红书，代码量89行（有三个冗余函数居然还短些），第二个据说来自刘汝佳的《训练指南》，代码量99行但是变量名比较短，或许打起来可以更快些。

第一个模板：

#include <bits/stdc++.h>

using namespace std;
const int maxNode = 444444;
const int INF = 0x3f3f3f3f;

struct Treap {
    int root,treapCnt,key[maxNode],priority[maxNode],childs[maxNode][2],cnt[maxNode],size[maxNode];

    Treap() {
        root = 0;
        treapCnt = 1;
        priority[0] = INF;
        size[0] = 0;
    }
    void update(int x) {
        size[x] = size[childs[x][0]] + cnt[x] + size[childs[x][1]];
    }
    void rotate(int &x,int t) {
        int y = childs[x][t];
        childs[x][t] = childs[y][1 - t];
        childs[y][1 - t] = x;
        update(x);
        update(y);
        x = y;
    }
    void __insert(int &x,int k) {
        if(x) {
            if(key[x] == k) {
                cnt[x]++;
            } else {
                int t = key[x] < k;
                __insert(childs[x][t],k);
                if(priority[childs[x][t]] < priority[x]) {
                    rotate(x,t);
                }
            }
        } else {
            x = treapCnt++;
            key[x] = k;
            cnt[x] = 1;
            priority[x] = rand();
            childs[x][0] = childs[x][1] = 0;
        }
        update(x);
    }

    void __erase(int &x,int k) {
        if(key[x] == k) {
            if(cnt[x] > 1) {
                cnt[x]--;
            } else {
                if(childs[x][0] == 0 && childs[x][1] == 0) {
                    x = 0;
                    return;
                }
                int t = priority[childs[x][0]] > priority[childs[x][1]];
                rotate(x,t);
                __erase(x,k);
            }
        } else {
            __erase(childs[x][key[x] < k],k);
        }
        update(x);
    }
    int __getKth(int &x,int k) {
        if(k <= size[childs[x][0]]) {
            return __getKth(childs[x][0],k);
        }
        k -= size[childs[x][0]] + cnt[x];
        if(k <= 0) {
            return key[x];
        }
        return __getKth(childs[x][1],k);
    }

    void insert(int k) {
        __insert(root,k);
    }

    void erase(int k) {
        __erase(root,k);
    }

    int getKth(int k) {
        return __getKth(root,k);
    }
};

int main() {

    return 0;
}

注释详见红书190页。

第二个模板：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
using namespace std;
struct Node
{
    Node *ch[2];
    int r,v,s;//s表示节点数

    Node(int v):v(v)
    {
        ch[0]=ch[1]=NULL;
        r=rand();//在cstdlib头声明
        s=1;
    }

    int cmp(int x)
    {
        if(x==v)return -1;
        return x<v?0:1;
    }
    void maintain()
    {
        s=1;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
}; //root全局使用的话可以在这里跟上*root
void rotate(Node* &o,int d)
{
    Node *k=o->ch[d^1];
    o->ch[d^1]=k->ch[d];
    k->ch[d]=o;
    o->maintain();
    k->maintain();
    o=k;
}
void insert(Node* &o,int x)//o子树中事先不存在x
{
    if(o==NULL) o=new Node(x);
    else
    {
        //如这里改成int d=o->cmp(x);
        //就不可以插入相同的值，因为d可能为-1
        int d=x<(o->v)?0:1;
        insert(o->ch[d],x);
        if(o->ch[d]->r > o->r)
            rotate(o,d^1);
    }
    o->maintain();
}

void remove(Node* &o,int x)
{
    if(o==NULL) return ;//空时返回

    int d=o->cmp(x);
    if(d==-1)
    {
        Node *u=o;
        if(o->ch[0] && o->ch[1])
        {
            int d2=(o->ch[0]->r < o->ch[1]->r)?0:1;
            rotate(o,d2);
            remove(o->ch[d2],x);
        }
        else
        {
            if(o->ch[0]==NULL) o=o->ch[1];
            else o=o->ch[0];
            delete u;//这个要放里面
        }
    }
    else remove(o->ch[d],x);
    if(o) o->maintain();//之前o存在,但是删除节点后o可能就是空NULL了,所以需要先判断o是否为空
}

//返回关键字从小到大排序时的第k个值
//若返回第K大的值，只需要把ch[0]和ch[1]全互换就可以了
int kth(Node* o,int k)
{
    assert(o && k>=1 && k<=o->s);//保证输入合法,根据实际问题返回
    int s=(o->ch[0]==NULL)?0:o->ch[0]->s;
    if(k==s+1) return o->v;
    else if(k<=s) return kth(o->ch[0],k);
    else return kth(o->ch[1],k-s-1);
}

//返回值x在树中的排名,就算x不在o树中也能返回排名
//返回值范围在[1,o->s+1]范围内
int rank(Node* o,int x)
{
    if(o==NULL) return 1;//未找到x;

    int num= o->ch[0]==NULL ? 0:o->ch[0]->s;
    if(x==o->v) return num+1;
    else if(x < o->v) return rank(o->ch[0],x);
    else return rank(o->ch[1],x)+num+1;
}


int main()
{
    int n=0;
    while(scanf("%d",&n)==1 && n)
    {
        Node *root=NULL; //初始化为NULL
        for(int i=0; i<n; i++)
        {
            int x;
            scanf("%d",&x);
            if(root==NULL) root=new Node(x);
            else insert(root,x);
        }

        int v;
        while(scanf("%d",&v)==1)
        {
            printf("%d\n",rank(root,v));
        }
    }
    return 0;
}

个人更加喜欢第二个模板，并用它AC了一道模板题：POJ 2985
简要题意：有N只猫,开始每只猫都是一个小组,下面要执行M个操作,操作0 i j 是把i猫和j猫所属的小组合并,操作1 k 是问你当前第k大的小组大小是多少. 且k<=当前的最大组数。
思路：并查集+Treap，并查集维护集合合并，Treap负责查询第K大。可以只把合并后的组扔到Treap里，做一个优化。

AC代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<iostream>
using namespace std;
struct Node
{
    Node *ch[2];
    int r,s;//s表示节点数

    Node(int v):v(v)
    {
        ch[0]=ch[1]=NULL;
        r=rand();//在cstdlib头声明
        s=1;
    }

    int cmp(int x)
    {
        if(x==v)return -1;
        return x<v?0:1;
    }
    void maintain()
    {
        s=1;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
} *root;
void rotate(Node* &o,所以需要先

判断o是否为空
}

//返回关键字从小到大排序时的第k个值
int kth(Node* o,int k)
{
    //assert(o && k>=1 && k<=o->s);//保证输入合法
    if(!(o && k>=1 && k<=o->s)) return 1;
    int s=(o->ch[1]==NULL)?0:o->ch[1]->s;
    if(k==s+1) return o->v;
    else if(k<=s) return kth(o->ch[1],k);
    else return kth(o->ch[0],x)+num+1;
}

const int MAXN = 2e5 + 5;
int far[MAXN],rnk[MAXN],siz[MAXN];

int Find(int x) {
    if(far[x] == x) return x;
    return far[x] = Find(far[x]);
}
void Unite(int x,int y) {
    x = Find(x);
    y = Find(y);
    if(x == y) return;
    if(rnk[x] > rnk[y]) swap(x,y);
    if(siz[x] > 1) remove(root,siz[x]);
    if(siz[y] > 1) remove(root,siz[y]);
    insert(root,siz[x] + siz[y]);
    far[x] = y;
    siz[y] += siz[x];
}
int main()
{
    int N,M;
    cin >> N >> M;
    for(int i = 1; i <= N; i++) {
        far[i] = i;
        rnk[i] = 0;
        siz[i] = 1;
    }
    root = NULL;
    while(M--) {
        int c;
        scanf("%d",&c);
        if(c == 0) {
            int x,y;
            scanf("%d%d",&x,&y);
            Unite(x,y);
        } else {
            int m;
            scanf("%d",&m);
            printf("%d\n",kth(root,m));
        }
    }
    return 0;
}

据说这道题可以用树状数组来A，而且代码比Treap短，我再去学习一波~

原文链接：https://www.f2er.com/datastructure/382291.html

猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test