首页 > 代码库 > Treap和名次树
Treap和名次树
Treap名字的来源：Tree+Heap，正如名字一样，就是一颗简单的BST，一坨堆的合体。BST的不平衡的根本原因在于基于左<=根<=右的模式吃单调序列时候会无脑成长链，而Treap则添加一个优先级属性，值的大小随机生成，用最大堆的方式维护。之所以使用堆，是因为堆是一颗 完全二叉树，而BST梦寐以求的就是完全二叉结构，二者一结合，就产生了一种新的Balanced BST。Treap依赖于随机数，随机生成的优先级属性，通过简单的左右旋可以将长链旋转成近似完全二叉树结构，注意只是近似，平均情况下的树高是（log 1.46n），但是完全二叉是（log 2n），可以说还是有一点点差距的，不过基本接近红黑树的平衡状况。鉴于比红黑树好拍，而且可塑性很强（如果你是用STL红黑树），在不是很追求鲁棒性的前提下，Treap算是神器了。
常规的BST用不着Treap，Treap的一大作用是求第K大数，具体方法是每个结点维护一个附加信息s，s为所有子结点和自身结点的数量，形成一颗 Rank Tree（名次树），如果你是手拍红黑树，可以自己实现，用不着Treap。但是如果使用STL，STL高度封装特性使得我们无法定制自己的树，这点着实 蛋疼。记住Treap的优势：简化的可定制的红黑树！
先来介绍一下Treap的结点结构。
struct node{ node *ch[2]; int v,r,s; //v-value，r-random值，s-附加结点信息 int cmp(int x) { if(x==v) return -1; return x<v?0:1; //0-left，1-right } void maintain() //维护附加信息s { s=1; if(ch[0]!=NULL) s+=ch[0]->s; if(ch[1]!=NULL) s+=ch[1]->s; }}
Treap的主操作由以下几部分构成：rotate、insert，remove。
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) { if(o==NULL) {o=new node;o->ch[0]=o->ch[1]=NULL;o->v=x;o->r=rand();o->s=1;} else { int d=x<o->v?0:1; //不使用cmp的原因：可能有重复元素 insert(o->ch[d],x); if(o->ch[d]->r > o->r) rotate(o,d^1); } o->maintain(); }
void remove(node* &o,int x) { int d=o->cmp(x); if(d==-1) { if(o->ch[0]!=NULL&&o->ch[1]!=NULL) { int d2=o->ch[0]->r>o->ch[1]->r?1:0; rotate(o,d2); remove(o->ch[d2],x); } else {if(o->ch[0]==NULL) o=o->ch[1];else o=o->ch[0];} } else remove(o->ch[d],x); if(o!=NULL) o->maintain(); }
remove的操作比较繁点，分为三种情况:
1.左右子树都存在，得让左右结点较大的r转到根，然后移出原来的根。
2.左右子树存其一，根直接改成左/右即可。
3.左右子树不存在，直接NULL即可。
然后就是RankTree的操作：kth
int kth(node *&o,int k){ if(o == NULL || k<=0 || k>o->s) return 0; 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],k-s-1);}
@练习题
LA5031,查询指定点连通的第K大数。首先得明白连通≠邻接，所以查询某个点的连通点，得从该点的root进行。本题中虽然说是图，但是必须清 楚，图可以由多棵Tree合成。方法是先保持所有结点独立，各自为一颗Tree，然后对于有边的u、v，进行两颗Tree的合并操作。由于合并的时候要批 量修改父节点，这里借助于并查集完成操作。最麻烦的是删除指定一条边，如果正向处理，代码要写好多行。这里借助逆向操作，变删除为添加，就好办多了。注 意，一旦逆向后，原本修改结点的操作也要反过来。cmd里保存的是现有w的之前的w，然后覆盖w，逆向处理的时候修改的之前备份的值，而不是应该修改的 值。
主要操作为addedge，merge，change，query。
merge（src，dest）: 土法子，就是把src所有点取出来insert。递归src左右子树，然后将src根的值insert到dest里面，最后src赋值NULL
addedge（u，v） ：先确认合并的u、v是否在同一集合，如果不在，将结点少的点merge到结点多的点里面（优化）。
change（x,v): 先确定目标点的root，remove掉值为x的点（？？对LRJ的代码产生疑惑，题目说是将指定id的点修改，万一有相同的x，那不就删了多点?) 然后insert值为v的点，修改w保存的值。
query: 每次通过并查集定位指定点的root，然后做kth，累加统计。
Treap和名次树