精华内容
下载资源
问答
  • Treap

    2015-12-22 19:20:22
    Treap树堆 是一种 随机平衡二叉树。 相对于正正规规的AVL树,倒是灵活了许多。 Treap 也有旋转模式,但是只有单选转,而且Treap的旋转,怎么旋转,该不该旋转完全是随机化的,这样子在大大减少了编码量的同时,...

    Treap树堆 是一种 随机平衡二叉树。

    相对于正正规规的AVL树,倒是灵活了许多。

    Treap 也有旋转模式,但是只有单选转,而且Treap的旋转,怎么旋转,该不该旋转完全是随机化的,这样子在大大减少了编码量的同时,相对也把效率给提了上去。在最差情况下也比最差情况下的朴素 BST 好


    代码参考 《Data Structure and Algorithm Analysis in C》


    结构体部分:

    typedef struct Treap * Node;  
    
    Node root = 0;        //保存根节点 
    
    Node NulNode = 0;     //传说中的标记节点,不使用NULL是因为怕出错,而且代码写起来较方便
                          //可以理解为代替空指针防止出错的自定义指针 
    
    struct Treap
    {
      Node left, right;   //子节点
      int key;            //值,可自定义 
      int priority;       //优先级,随机生成的一个数,后面会用到。 
    };
    
    


    左右旋转

    Node L_Rotate(Node K2)
    {
    	Node K1 = K2 -> left;
    	K2 -> left = K1 -> right;
    	K1 -> right = K2;
    	return K1;
    }
    
    Node R_Rotate(Node K2)
    {
    	Node K1 = K2 -> right;
    	K2 -> right = K1 -> left;
    	K1 -> left = K2;
    	return K1;
    }
    
    



    插入其实也不难,记得每次执行插入后旋转一次

    Node insert(Node T,int key)
    {
    	// 采用递归写法 
    	 
    	int num = rand() % 10086383;  //产生一个随机数 
    	if(T == NulNode)              //如果树为空,则新建 
    	{
    		T = new Treap();
    		T -> key = key;
    		T -> priority = num;
    		T -> left = T -> right = NulNode;  //初始化 
    		return T;
    	}
    	else
    	{
    		if (key > T->key)      //插入值比当前大,往右。 
    		{
    			T->right = insert(T->right , key);  //注意! T->right = insert(T->right,key) 左边right不能丢 
    			if(T -> left -> priority   <   T -> right -> priority)
    			   T = L_Rotate(T);    //插入后旋转 
    		} 
    		else if (key < T->key)
    		{
    			T->left = insert(T->left , key);
    			if(T -> left -> priority   >   T -> right -> priority)
    			   T = R_Rotate(T);
    		}
    	}
    	return T;
    }


    删除略有些麻烦。

    Node Remove(Node T , int key)
    {
    	if(T!=NulNode)  //如果不为空 
    	{
    	if (key < T ->key)
    	  T->left = Remove(T->left,key);    
    	else if (key > T->key)
    	  T->right = Remove(T->right,key); 
    	else
    	{
    		if(T->left->priority < T -> right -> priority)  
    		   T = L_Rotate(T);
    		else
    		   T = R_Rotate(T);  //调整到所求点为叶节点 
    		
    		if(T != NulNode)
    		  T = Remove(T , key);
    		else
    		{ 
    			delete T -> left;   //要删的节点 仍有左右子树NulNode,
    			                    //为了返回值时,好处理,所以用旋转把key所在地方变为NulNode的子节点后删除。 
    			T->left = NulNode; 
    			
    		}
    	}
    }
    	return T;
    }



    展开全文
  • Treap平衡

    2019-06-05 17:48:28
    浅谈Treap平衡先从二叉查找谈起Treap平衡的旋转操作定义建立新节点右旋 先从二叉查找谈起 二叉查找可以用来在随机数据中高效率地查找一个数。具有以下性质: (1)若左子树不空,则左子树上所有结点的值均...

    先从二叉查找树谈起

    二叉查找树可以用来在随机数据中高效率地查找一个数。具有以下性质:
    (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
    (3)左、右子树也分别为二叉排序树;
    (4)平均的时间复杂度为O(log n);
    (摘自360百科)

    举个栗子:若将数据“5,7,2,1,45,7,2,1,4”插入二叉查找树中,会得到以下的图:

    666
    看上去好像很高效,但是遇到数据“7,5,4,2,17,5,4,2,1”,二叉查找树就没辙了:
    在这里插入图片描述
    时间复杂度一下变为了O(n)。
    所以,为了保持该树的高效,我们可以对这个树进行旋转操作,但是又不改变二叉查找树的性质。今天我要介绍的就是Treap平衡树

    Treap平衡树的旋转操作

    • 定义

    定义自变量:tr[]tr[ ]结构体,其中
    ll表示该节点左儿子的编号;
    rr表示该节点右儿子的编号;
    valval表示该节点的实际权值(输入的权值);
    datdat表示随机赋予的权值(作用待会再讲);
    sizesize表示该节点的子树大小;
    cntcnt表示该节点的重复个数(即输入了几个该节点的权值)
    代码如下

    struct treap
    {
    	int l,r;
    	int val,dat;//val是实际权值,dap是随机权值
    	int size,cnt;//size是子树大小,cnt是元素个数
    }tr[maxn];
    int n;
    int tot,root;
    
    • 建立新节点

    初始化:记录节点编号(tot++),更新权值valvaldatdat,将子树大小和重复次数设为1。

    int New(int val)
    {
    	tot++;
    	tr[tot].val=val;
    	tr[tot].dat=rand();//赋予随机值
    	tr[tot].cnt=tr[tot].size=1;
    	return tot;
    }//建立新节点
    
    • 右旋

    (To be continued)

    展开全文
  • 1A~果然上午看小说,中午吃好吃的,下午效率高23333 说题意,有两种操作 add和query,query每次查询的是第i小的,i是从0开始的,查询之前i++,查询之后不删除。告诉你add数字的依次次序,又告诉你当数组当前有几个数...

    Black Box
    Time Limit: 1000MS   Memory Limit: 10000K
    Total Submissions: 9883   Accepted: 4047

    Description

    Our Black Box represents a primitive database. It can save an integer array and has a special i variable. At the initial moment Black Box is empty and i equals 0. This Black Box processes a sequence of commands (transactions). There are two types of transactions:

    ADD (x): put element x into Black Box;
    GET: increase i by 1 and give an i-minimum out of all integers containing in the Black Box. Keep in mind that i-minimum is a number located at i-th place after Black Box elements sorting by non- descending.

    Let us examine a possible sequence of 11 transactions:

    Example 1
    N Transaction i Black Box contents after transaction Answer 
    
          (elements are arranged by non-descending)   
    
    1 ADD(3)      0 3   
    
    2 GET         1 3                                    3 
    
    3 ADD(1)      1 1, 3   
    
    4 GET         2 1, 3                                 3 
    
    5 ADD(-4)     2 -4, 1, 3   
    
    6 ADD(2)      2 -4, 1, 2, 3   
    
    7 ADD(8)      2 -4, 1, 2, 3, 8   
    
    8 ADD(-1000)  2 -1000, -4, 1, 2, 3, 8   
    
    9 GET         3 -1000, -4, 1, 2, 3, 8                1 
    
    10 GET        4 -1000, -4, 1, 2, 3, 8                2 
    
    11 ADD(2)     4 -1000, -4, 1, 2, 2, 3, 8   

    It is required to work out an efficient algorithm which treats a given sequence of transactions. The maximum number of ADD and GET transactions: 30000 of each type.


    Let us describe the sequence of transactions by two integer arrays:


    1. A(1), A(2), ..., A(M): a sequence of elements which are being included into Black Box. A values are integers not exceeding 2 000 000 000 by their absolute value, M <= 30000. For the Example we have A=(3, 1, -4, 2, 8, -1000, 2).

    2. u(1), u(2), ..., u(N): a sequence setting a number of elements which are being included into Black Box at the moment of first, second, ... and N-transaction GET. For the Example we have u=(1, 2, 6, 6).

    The Black Box algorithm supposes that natural number sequence u(1), u(2), ..., u(N) is sorted in non-descending order, N <= M and for each p (1 <= p <= N) an inequality p <= u(p) <= M is valid. It follows from the fact that for the p-element of our u sequence we perform a GET transaction giving p-minimum number from our A(1), A(2), ..., A(u(p)) sequence.


    Input

    Input contains (in given order): M, N, A(1), A(2), ..., A(M), u(1), u(2), ..., u(N). All numbers are divided by spaces and (or) carriage return characters.

    Output

    Write to the output Black Box answers sequence for a given sequence of transactions, one number each line.

    Sample Input

    7 4
    3 1 -4 2 8 -1000 2
    1 2 6 6

    Sample Output

    3
    3
    1
    2

    Source


    1A~果然上午看小说,中午吃好吃的,下午效率高23333

    说题意,有两种操作 add和query,query每次查询的是第i小的,i是从0开始的,查询之前i++,查询之后不删除。告诉你add数字的依次次序,又告诉你当数组当前有几个数的时候进行了一次查询(这句话我结合示例看了好久才明白什么意思)然后就是小case了

    /*************
    poj1442
    2016.1.26
    984K	204MS	C++	2246B
    *************/
    #include <cstdio>
    #include <cstring>
    #include <ctime>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <cmath>
    #include <utility>
    #include <vector>
    #include <queue>
    #include <map>
    #include <set>
    #define max(x,y) ((x)>(y)?(x):(y))
    #define min(x,y) ((x)>(y)?(y):(x))
    #define INF 0x3f3f3f3f
    #define MAXN 100005
    
    using namespace std;
    
    int cnt=1,rt=0; //节点编号从1开始
    
    struct Tree
    {
      int key, size, pri, son[2]; //保证父亲的pri大于儿子的pri
      void set(int x, int y, int z)
      {
        key=x;
        pri=y;
        size=z;
        son[0]=son[1]=0;
      }
    }T[MAXN];
    
    void rotate(int p, int &x)
    {
      int y=T[x].son[!p];
      T[x].size=T[x].size-T[y].size+T[T[y].son[p]].size;
      T[x].son[!p]=T[y].son[p];
      T[y].size=T[y].size-T[T[y].son[p]].size+T[x].size;
      T[y].son[p]=x;
      x=y;
    }
    
    void ins(int key, int &x)
    {
      if(x == 0)
        T[x = cnt++].set(key, rand(), 1);
      else
      {
        T[x].size++;
        int p=key < T[x].key;
        ins(key, T[x].son[!p]);
        if(T[x].pri < T[T[x].son[!p]].pri)
          rotate(p, x);
      }
    }
    
    void del(int key, int &x) //删除值为key的节点
    {
      if(T[x].key == key)
      {
        if(T[x].son[0] && T[x].son[1])
        {
          int p=T[T[x].son[0]].pri > T[T[x].son[1]].pri;
          rotate(p, x);
          del(key, T[x].son[p]);
        }
        else
        {
          if(!T[x].son[0])
            x=T[x].son[1];
          else
            x=T[x].son[0];
        }
      }
      else
      {
        T[x].size--;
        int p=T[x].key > key;
        del(key, T[x].son[!p]);
      }
    }
    
    int find(int p, int x) //找出第p小的节点的编号
    {
      if(p == T[T[x].son[0]].size+1)
        return x;
      if(p > T[T[x].son[0]].size+1)
        find(p-T[T[x].son[0]].size-1, T[x].son[1]);
      else
        find(p, T[x].son[0]);
    }
    
    
    int ad[30005],qu[30005];
    int main()
    {
      //  freopen("cin.txt","r",stdin);
        int m,n,pos,posq;
        while(~scanf("%d%d",&m,&n))
        {
            rt=0;
            cnt=1;
            for(int i=1;i<=m;i++) scanf("%d",&ad[i]);
            for(int i=1;i<=n;i++) scanf("%d",&qu[i]);
            pos=0,posq=1;
            for(int i=1;i<=m;i++)
            {
                ins(ad[i],rt);
              //  cout<<"1111111"<<endl;
                while(i==qu[posq])
                {
                 //   cout<<"22222222"<<endl;
                    pos++;
                    int p=find(pos,rt);
                    printf("%d\n",T[p].key);
                    posq++;
                }
            }
        }
        return 0;
    }
    


    展开全文
  • 题意:模拟二叉树的构造过程,给出\(n\)个节点,每次从根插入,小于当前节点转到左儿子,否则右...既然这样就容易搞了,Treap分裂找出这两个值比较并维护即可(数据保证每个值只出现一次,更容易维护了) 93ms效率非常可观...

    题意:模拟二叉树的构造过程,给出\(n\)个节点,每次从根插入,小于当前节点转到左儿子,否则右儿子,输出第\([2,n]\)个节点的父亲的权值

    直接手动模拟会被链式结构T掉
    网上找了下发现二叉树的性质是当前插入节点的父亲总是比它小的最大值或比它大的最小值(深度最深者为父亲)
    既然这样就容易搞了,Treap分裂找出这两个值比较并维护即可(数据保证每个值只出现一次,更容易维护了)
    93ms效率非常可观,可持久化Treap天下第一

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<string>
    #include<vector>
    #include<stack>
    #include<queue>
    #include<set>
    #include<map>
    #define rep(i,j,k) for(register int i=j;i<=k;i++)
    #define rrep(i,j,k) for(register int i=j;i>=k;i--)
    #define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
    #define iin(a) scanf("%d",&a)
    #define lin(a) scanf("%lld",&a)
    #define din(a) scanf("%lf",&a)
    #define s0(a) scanf("%s",a)
    #define s1(a) scanf("%s",a+1)
    #define print(a) printf("%lld",(ll)a)
    #define enter putchar('\n')
    #define blank putchar(' ')
    #define println(a) printf("%lld\n",(ll)a)
    #define IOS ios::sync_with_stdio(0)
    using namespace std;
    const int MAXN = 2e5+11;
    const int INF = 0x3f3f3f3f;
    const double EPS = 1e-7;
    typedef long long ll;
    const ll MOD = 1e9+7; 
    unsigned int SEED = 19260817;
    ll read(){
        ll x=0,f=1;register char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    inline int Rand(){
        SEED=SEED*1103515245+12345;
        return SEED/65536;
    }
    struct Treap{
        int son[MAXN][2],root,tot;
        int val[MAXN],fix[MAXN],size[MAXN];
        int dep[MAXN];
        #define lc son[o][0]
        #define rc son[o][1]
        void init(){
            root=0;
            son[0][0]=son[0][1]=0;
            val[0]=fix[0]=size[0]=0;
            dep[0]=0;
            tot=1;
        }
        int node(int v,int d){
            son[tot][0]=son[tot][1]=0;
            val[tot]=v; fix[tot]=Rand();
            size[tot]=1;dep[tot]=d;
            return tot++;
        }
        void pu(int o){
            size[o]=size[lc]+size[rc]+1;
        }
        void split(int o,int pivot,int &a,int &b){
            if(!o){
                a=b=0;
                return;
            }else if(val[o]>pivot){
                b=o;
                split(lc,pivot,a,lc);
                pu(o);
            }else{
                a=o;
                split(rc,pivot,rc,b);
                pu(o);
            }
        }
        int merge(int a,int b){
            if(!a) return b;
            if(!b) return a;
            if(fix[a]<fix[b]){
                son[a][1]=merge(son[a][1],b);
                pu(a);
                return a;
            }else{
                son[b][0]=merge(a,son[b][0]);
                pu(b);
                return b;
            }
        }
        void insert(int v,int d){
            int a,b,t=node(v,d);
            split(root,v,a,b);
            root=merge(merge(a,t),b);
        }
        int kth(int o,int k){
            if(!o)return o;//
            while(1){
                if(k<=size[lc]){
                    o=lc;
                }else if(k==size[lc]+1){
                    return o;
                }else{
                    k-=size[lc]+1;
                    o=rc;
                }
            } 
        }
        int insert(int v){
            int a,b;
            split(root,v-1,a,b);
            int x=kth(a,size[a]);
            int y=kth(b,1);
            bool flag=0;
            if(dep[x]<dep[y]) flag=1;
            root=merge(a,b);
            int d=(flag?dep[y]:dep[x])+1;
            insert(v,d);
            return flag?val[y]:val[x];
        }
    }tp;
    int n,m,a[MAXN],ans[MAXN];
    int main(){
        while(cin>>n){
            tp.init();
            rep(i,1,n) a[i]=read();tp.insert(a[1],1);
            rep(i,2,n) ans[i]=tp.insert(a[i]);
            rep(i,2,n) printf("%d%c",ans[i],i==n?'\n':' ');
        }
        return 0;
    }

    转载于:https://www.cnblogs.com/caturra/p/8823855.html

    展开全文
  • Treap平衡学习笔记

    2020-08-07 23:08:43
    保持树状结构的平衡,防止偏沉或退化成链,优化查询效率 Treap=Tree+Heap 查找+满足 最小堆性质1 的修正值 Treap 可以定义为有以下性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的...
  • Treap(堆)

    千次阅读 2013-10-03 00:42:45
    Treap(堆) 分类: algorithm2013-09-30 10:13 57人阅读 评论(0) 收藏 举报 ...treap ... Treap,就是有另一个随机数满足堆的性质的二叉搜索,其结构相当... 其特点是实现简单,效率高于伸展并且支持大部
  • 平衡 treap 模板

    2019-09-29 11:34:41
    #include<...//treap 就是tree+heap 利用了二叉堆的结构整体趋于平衡(不一定是严格意义上的平衡) //又利用了二叉平衡的排序 才让查找 插入的效率在logn struct data{//该的标号为完全二...
  • 序:正常的BST有可能退化,成为链,大大降低效率,所以有很多方法来保持左右size的平衡,本文将简单介绍Treap,Splay,替罪羊,FHQ Treap; 另:代码都是普通平衡 1.Treap 堆,在数据结构中也称Treap,是指有...
  • Treap

    2017-08-13 16:09:45
    Treap 是一种效率较高、易于编写的平衡二叉查找,和 splay 一样受到广大竞赛选手的青睐。
  • 序:正常的BST有可能退化,成为链,大大降低效率,所以有很多方法来保持左右size的平衡,本文将简单介绍Treap,Splay,替罪羊,FHQ Treap; 另:代码都是普通平衡 1.Treap 堆,在数据结构中也称Treap,是指有...
  • 在数据结构中,的种类不计其数,百度百科上就有50多种, 因此就把最近看的一些二叉查找的特性和用途整理一下: ...为了保证查找的效率,人们提出让尽量平衡的思想,也就是二叉平衡,通过尽量控制
  • 怎么说,今天重温了平衡Treap写法,做了一点心得,稍微总结一下。...平衡事实上只不过用了各种方法将高维持在logN以内,保证查找效率而已,所以平衡本身个人并不认为是一大类,例如Treap的核心是一种
  • 友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap(一种平衡,通过对每个节点随机分配一个priority,同时保证这棵平衡关于priority是一个小根堆以保证效率)。这时候不怎么友爱的510跑了出来,他问了YY小朋友一个极...
  • 初涉平衡treap

    2018-05-07 22:01:00
    因为二叉搜索(BST)非常容易被卡成一条链而影响效率,所以我们需要一种更加平衡的形结构,从而保持$O(logn)$的优秀复杂度。 那么为什么涉及到heap呢?我们知道因为堆有个非常好的性质,它的高度是$logn$的。...
  • 友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap(一种平衡,通过对每个节点随机分配一个priority,同时保证这棵平衡关于priority是一个小根堆以保证效率)。这时候不怎么友爱的510跑了出来,他问了Y...
  • 一、什么是 Treap Treap=Tree+HeapTreap=Tree+HeapTreap=Tree+Heap ...这个单词的构造选取了TreeTreeTree()的前两个字符和HeapHeapHeap(堆)的后三个字符,Treap=Tree+HeapTreap=Tree+HeapTreap=Tree...
  • Treap是一棵二叉搜索,只是每个节点多了一个优先级fix,对于每个节点,该节点的优先级小于等于其所有孩子的优先级。当然,引入优先级fix的目的就是防止退化成一条链,从而影响查找效率。 所以,这样看来就是:...
  • 存一个模板,先将l~r这个区间的treap分离出来,然后在根打上翻转标记,然后在merge,split,dfs等遍历的时候先执行push_down,照旧还是用了并查集随机的形状 当然,在数据范围特别大的时候,并查集会导致空间范围...
  • treap学习笔记

    2019-03-02 22:29:00
    众所周知,二叉查找的查找效率低的原因是不平衡,而我们又不希望用各种奇奇怪怪的旋转来使它平衡,那么该怎么办呢?这时候,FHQ跳出来说了一句:我的treap,不需要旋转! FHQ Treap的基本操作 首先要理解节点的...
  • 虽然他很能吃苦耐劳,但是由于这个书架十分巨大,所以他的工作效率总是很低,以致他面临着被解雇的危险,这也正是他所郁闷的。具体说来,书架由N个书位组成,编号从1到N。每个书位放着一本书,每本书有一个特定的...
  • Treap基本用法总结

    2017-11-25 21:54:00
    一棵二叉搜索可能退化成链,那样各种操作的效率都比较低 于是可爱的Treap在每个节点原先值v的基础上加了一个随机数rnd,的形态要满足是rnd的大根堆或小根堆 可以说是普通BST的进化版吧。 Q:为什么rnd要满足...
  • [转载]Treap

    2013-07-15 16:32:38
    http://www.nocow.cn/index.php/Treap ...Treap ...Treap,就是有另一个随机数满足堆的性质的...其特点是实现简单,效率高于伸展并且支持大部分基本功能,性价比很高。 目录  [隐藏]  1 前言2

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 125
精华内容 50
关键字:

treap树效率