注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

随机平衡树(treap)  

2017-08-08 19:17:45|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        平衡树,说白,就是平衡的二叉排序树,也就是解决了二叉排序树深度不平均的问题。退化成链的问题。
       二叉排序树的简单知识,我在之前竟然写过了!
        http://yhf4aspe.blog.163.com/blog/static/2468030842015820111749393/
===============================
        这次我们来讲treap:
        treap,是实现平衡的一种方式,可以说,玄学!
随机平衡树(treap) - 杨鸿飞 - 杨鸿飞的博客
        这是论文截图,下面还说,修正值是节点在插入到 Treap 中时 随机生成的一个值,它与节点的值无关。
        没想到,搞了个随机,竟能严格证明,期望深度是log级!(当然我不会证)
================================
        插入和删除和查找还是二叉排序树的方法,但要像堆一样维护,所以我们需要一种操作,能改变树的结构,但还能满足二叉排序树的性质,这叫旋转。[竟然还有这种操作!!!]
        Treap只需要左旋和右旋。
随机平衡树(treap) - 杨鸿飞 - 杨鸿飞的博客
        再次用论文……
        当插入和删除时的递归时,用旋转上去(下去)就好,类似于堆的up或down操作。
==========================
        下面送上裸题和程序:
        N个操作,一种是Push(x)把一个数放进去,一种是Delete(x)删掉一个数,一种是Ask(x),求第k小。
        smoj2165

,是#include <algorithm>
#include <iostream>
#include <cstring>
#include <time.h>
#include <cstdio>

using namespace std;

const int ML=1000100;

struct Tnode { int x,s,lc,rc,fix; }tr[ML];

int tp;

int Push(int x)
{
int p=tp++;

tr[p].x=x; tr[p].s=1; tr[p].fix=rand()%ML; tr[p].lc=tr[p].rc=-1;

return p;
}

void Update(int p) { tr[p].s=tr[tr[p].lc].s+tr[tr[p].rc].s+1; } //根据题目而变,此题维护一个size

void Right_XZ(int &p) //取地址符,p会改变的
{
int lcp=tr[p].lc;

tr[p].lc=tr[lcp].rc;
tr[lcp].rc=p;

Update(lcp); Update(p); //记得跟新

p=lcp; //p变了
}

void Left_XZ(int &p) //左旋同理
{
int rcp=tr[p].rc;

tr[p].rc=tr[rcp].lc;
tr[rcp].lc=p;

Update(rcp); Update(p);

p=rcp;
}

void Ins(int &p,int x) //取地址符,p会改变的是上一次的lc或rc
{
if (p==-1) { p=Push(x); return; }

int &llc=tr[p].lc,&rrc=tr[p].rc;

if (x<tr[p].x)
{
Ins(llc,x);

if (tr[p].fix>tr[llc].fix) Right_XZ(p); //维护堆
}
else
{
Ins(rrc,x);

if (tr[p].fix>tr[rrc].fix) Left_XZ(p);
}

Update(p);
}

int Sol(int p,int k)
{
if (p==-1) return 0;

int kk=0;

if (tr[p].lc!=-1) kk=tr[tr[p].lc].s; //左子树全部小于该点,所以该点是第左树.size+1小

if (kk+1==k) return tr[p].x;

if (kk+1<k) return Sol(tr[p].rc,k-kk-1);
else return Sol(tr[p].lc,k);
}

void Del(int &p,int x)
{
if (tr[p].x==x)
{
if (tr[p].lc!=-1 && tr[p].rc!=-1)
{
if (tr[tr[p].lc].fix<tr[tr[p].rc].fix)
{
Right_XZ(p);

Del(tr[p].rc,x);

Update(p);
}
else
{
Left_XZ(p);

Del(tr[p].lc,x);

Update(p);
}
}
else if (tr[p].lc==-1 && tr[p].rc==-1) p=-1;
else if (tr[p].lc==-1 && tr[p].rc!=-1) p=tr[p].rc;
else if (tr[p].lc!=-1 && tr[p].rc==-1) p=tr[p].lc;
//分三种情况,是子树,是在链上,是叶子
return;
}

if (tr[p].x>x) Del(tr[p].lc,x);
else Del(tr[p].rc,x);

Update(p);
}

void Print(int p)
{
if (tr[p].lc!=-1) { cout<<"("; Print(tr[p].lc); cout<<")"; }

cout<<tr[p].x;

if (tr[p].rc!=-1) { cout<<"("; Print(tr[p].rc); cout<<")"; }
}

int main()
{
freopen("2165.in","r",stdin);
freopen("2165.out","w",stdout);

srand(time(NULL));

tp=1;

int root=-1;

int q; scanf("%d",&q);

for ( ; q>0; q--)
{
int ch,k; scanf("%d%d",&ch,&k);

if (ch==1) Ins(root,k);
if (ch==2) printf("%d\n",Sol(root,k));
if (ch==3) Del(root,k);

//Print(1); cout<<endl;
}

return 0;
}



 
 
  评论这张
 
阅读(32)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018