Treap

  • 算法思想
      • 右旋
      • 左旋
      • 插入
      • 删除
      • 前驱
      • 后继
    • 训练
      • POJ3481
      • UOJ#3224. Tyvj 1728
      • POJ1442
      • HDU4585
  • 总结

算法思想

Treap=Tree+heap，即树堆，顾名思义，其满足二叉搜索树（中序有序性）和堆两种性质。Treap主要是利用堆的性质使得构造出来的树变成平衡二叉树，它的每个节点都有一个随机数，使得Treap满足堆的性质，而节点的真值又满足二叉搜索树的中序有序，其基本操作的期望时间复杂度为O(log⁡n)O(log n)O(logn)，Treap操作简单，较容易理解，可以基本实现随机平衡。

构造Treap过程中，插入节点时会给每个节点附加一个随机数作为优先级，优先级满足堆的性质(最大最小均可)

右旋和左旋是维持Treap高度的关键步骤，该步骤利用了堆的特征来调换点的位置

证明左旋/右旋之后树仍然满足二叉搜索树的性质很简单，由于二叉搜索树的中序有序性，将旋转前与旋转后的树都进行一次中序遍历便可知仍然满足二叉搜索树的性质

Treap笔记-编程之家

右旋

如图，节点p右旋时，会携带其右子树，向右旋转到q的右子树位置，q的右子树放在p的左子树位置，旋转后的树根为q

Treap笔记-编程之家代码

void zig(int &p)
{int q=tr[p].lc;tr[p].lc=tr[q].rc;tr[q].rc=p;p=q;//q为根
}

左旋

节点p左旋，携带其左子树，左旋转到q的左子树位置，q的左子树放在p的右子树位置，旋转后树根为q

Treap笔记-编程之家
代码

void zag(int &p)
{int q=tr[p].rc;tr[p].rc=tr[q].lc;tr[q].lc=p;p=q;//q为根
}

插入

Treap的插入与二叉搜索树一样，根据有序性找位置，然后创建节点，创建节点时，给节点附加一个随机数为优先级，自底向上检查该优先级是否满足堆性质，如果不满足，左旋或右旋

算法步骤(以最大堆为例)

  1. 从根节点p开始，若p为空，创点，插入元素，附加随机数
  2. 元素值与p相等，返回
  3. 小于，p的左子树递归插入，回溯时旋转，若p优先级小于左，右旋
  4. 大于，p右子树递归插入，回溯时旋转，若p优先级小于右，右旋

代码

int New(int v)
{tr[++cnt].val=v;tr[cnt].pri=rand();//获得优先级tr[cnt].rc=tr[cnt],lc=0;return cnt;
}
void Insert(int &p,int val)
{if(!p)//找到空点{p=New(val);return ;		}if(val==tr[p].val)//如果已经存在该元素return ;if(val<tr[p].val){Insert(tr[p].lc,val);//插入左子树if(tr[p].pri<tr[trp[p].lc].pri)//优先级比较zig(p);//右旋}if(val>tr[p].val){Insert(tr[p].rc,val);//插入右子树if(tr[p].pri<tr[trp[p].rc].pri)//优先级比较zag(p);//左旋}
}

删除

删除节点的基本思想：找到待删除的节点，将该节点向优先级大的子节点旋转，一直旋转到叶子，直接删除叶子

算法步骤（以最大堆为例）

  1. 从根节点p开始，若待删除元素val等于p的值，则分情况操作：若p只有左/右子树，子树上提，返回；若p左优先级大于右优先级，右旋，右子树递归；若p左优先级小于右优先级，p左旋，左子树递归
  2. 若val小于p值，左子树递归
  3. 若val大于p值，右子树递归

代码

void Delete(int &p,int val)//在p的子树中删除val
{if(!p)return;//如果找不到if(val==tr[p].val){if(!tr[p].lc||!tr[p].rc)//如果存在一个为空p=tr[p].lc+tr[p];//上提子树else if(tr[tr[p].lc].pri>tr[tr[p].lc].pri)//如果左子的优先级大于右子优先级{zig(p);//右旋Delete(tr[p].rc,val);}else{zag(p);//左旋Delete(tr[p].lc,val);}return ;}if(val<tr[p].val)//如果值小于当前节点值Delete(tr[p].lc,val);elseDelete(tr[p].rc,val);
}

前驱

这里的前驱指的是中序遍历的前驱，即排序的前一个值(升序)

在Treap中求一个节点val的前驱时，从树根喀什，若当前节点值小于val,则暂存该节点的值，因为该节点可能是val的前驱，在当前节点的右子树中寻找(当前值还不够靠近val)，否则在当前节点的左子树中寻找(当前值超过val了)，其过程类似于二分查找

代码

int GetPre(int val)
{int p=root;int res=-1;while(p){if(tr[p].val<val)//如果节点值小于查找值，向右查找{res=tr[p].val;//存储p=tr[p].rc;//尝试更大的值}elsep=tr[p].lc;//值过大，尝试更小的值}return res;
}

后继

与先驱对应，后继为排序中的后一个值

在Treap中求一个节点val的后继，从树根开始，若当前节点的值大于val，暂存该节点的值，在当前节点的左子树中查找(当前值还不够靠近val,查看有没有一个比当前值小的值大于val)，否则在当前节点的右子树中查找(当前值小于val了)，其过程类似于二分查找

代码

int GetNext()
{int p=root;int res=-1;while(p){if(tr[p].val>val)//如果节点值大于于查找值，向左查找{res=tr[p].val;//存储p=tr[p].lc;//尝试更小的值}elsep=tr[p].rc;//值过小，尝试更大的值}return res;
}

训练

POJ3481

题目大意：每个客户有优先级和编号，四种操作，停止系统，将编号K客户及优先级P添加入列表，为优先级最高客户提供服务并删除，为优先级最低客户提供服务并删除

思路：直接Treap，每次直接添加，优先级最高直接操作最右下节点，优先级最低直接操作最左下节点

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
//#include <unordered_map>
#include <map>
#include <set>
#include <numeric>
#include <stack>
#include <sstream>
#include <cmath>
#include <bitset>
//#include <unordered_set>
#include <functional>
#include <list>
#include <vector>
#include <iterator>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 Bint;
const int maxn=1e7+10;
int cnt,root;
struct tree {int val,pri,lc,rc,num;
} tr[maxn];
int New(int val,int num) {//申请新节点tr[++cnt].val=val;//存值tr[cnt].lc=tr[cnt].rc=0;//初始化tr[cnt].num=num;//记录编号tr[cnt].pri=rand();//优先级return cnt;
}
void zig(int &p) {//右旋int q=tr[p].lc;tr[p].lc=tr[q].rc;tr[q].rc=p;p=q;
}
void zag(int &p) {//左旋int q=tr[p].rc;tr[p].rc=tr[q].lc;tr[q].lc=p;p=q;
}
void Insert(int &p,int val,int num) {if(!p) {//空节点p=New(val,num);return ;}if(val<=tr[p].val) { //左子树Insert(tr[p].lc,val,num);if(tr[p].pri<tr[tr[p].lc].pri)//只对左子树进行了修改，所以只操作左子树zig(p);} else { //右子树Insert(tr[p].rc,val,num);if(tr[p].pri<tr[tr[p].rc].pri)//只对右子树进行了修改，所以只操作右子树zag(p);}
}
void Delete(int &p,int val) {if(!p)return;if(val==tr[p].val) {if(!tr[p].lc||!tr[p].rc)p=tr[p].lc+tr[p].rc;else if(tr[tr[p].lc].pri>tr[tr[p].rc].pri) {zig(p);Delete(tr[p].rc,val);//这里的p变成了原先的左子} else {zag(p);Delete(tr[p].lc,val);//这里的p变成了原先的右子}}if(val<tr[p].val)Delete(tr[p].lc,val);elseDelete(tr[p].rc,val);
}
void printMax(int p) {while(tr[p].rc)p=tr[p].rc;cout <<tr[p].num<<endl;Delete(root,tr[p].val);
}
void printMin(int p) {while(tr[p].lc)p=tr[p].lc;cout <<tr[p].num<<endl;Delete(root,tr[p].val);
}
int main() {ios::sync_with_stdio(0),cin.tie();int t,k,p;while(cin >>t&&t) {switch(t) {case 0:return 0;break;case 1:cin >>k>>p;Insert(root,p,k);break;case 2:printMax(root);break;case 3:printMin(root);break;}}return 0;
}

UOJ#3224. Tyvj 1728

题目大意：略

思路：基本的Treap操作，但是要记录节点对应值的个数，这里多设置了两个操作，一个是根据排名找值，一个是根据值找排名，具体思路查看代码

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <time.h>
using namespace std;
const int maxn=2e6+10;
struct tree {int val,lc,rc,num,pri,s;//值,左子,右子,重复个数,根的子树大小
} tr[maxn];
int root,cnt,n,opt,x;
int New(int val) {tr[++cnt].val=val;tr[cnt].lc=tr[cnt].rc=0;tr[cnt].pri=rand();tr[cnt].s=tr[cnt].num=1;//这里相对于模板多加了更新return cnt;
}
void Update(int p) {//更新子树大小tr[p].s=tr[tr[p].lc].s+tr[tr[p].rc].s+tr[p].num;//当前树根子树大小为左子树大小+右子树大小+节点重复值个数
}
void zig(int &p) {int q=tr[p].lc;tr[p].lc=tr[q].rc;tr[q].rc=p;tr[q].s=tr[p].s;//尝试画图分解求和来理解Update(p);//需要更新旋转后的节点p=q;
}
void zag(int &p) {int q=tr[p].rc;tr[p].rc=tr[q].lc;tr[q].lc=p;tr[q].s=tr[p].s;//尝试画图分解求和来理解Update(p);//需要更新旋转后的节点p=q;
}
void Insert(int &p,int val) {if(!p) {p=New(val);return ;}tr[p].s++;//这里很容易忘写了if(val==tr[p].val) {tr[p].num++;return ;}if(val<=tr[p].val) {Insert(tr[p].lc,val);if(tr[p].pri<tr[tr[p].lc].pri)zig(p);} else {Insert(tr[p].rc,val);if(tr[p].pri<tr[tr[p].rc].pri)zag(p);}
}
void Delete(int &p,int val) {if(!p)return ;tr[p].s--;if(val==tr[p].val) {if(tr[p].num>1) {//如果个数大于1，直接减个数tr[p].num--;return ;}if(!tr[p].lc||!tr[p].rc)p=tr[p].lc+tr[p].rc;else if(tr[tr[p].lc].pri>tr[tr[p].rc].pri) {zig(p);Delete(tr[p].rc,val);} else {zag(p);Delete(tr[p].lc,val);}return ;}if(val<tr[p].val)Delete(tr[p].lc,val);elseDelete(tr[p].rc,val);
}
int GetPre(int val) {int p=root,res=0;while(p)if(val>tr[p].val) {res=tr[p].val;p=tr[p].rc;} elsep=tr[p].lc;return res;
}
int GetNext(int val) {int p=root,res=0;while(p)if(val<tr[p].val) {res=tr[p].val;p=tr[p].lc;} elsep=tr[p].rc;return res;
}
int GetRankByVal(int p,int val) {//根据值来找排名if(!p)return 0;if(val==tr[p].val)return tr[tr[p].lc].s+1;//由于是升序，左小右大，统计比值小的有多少个+1else if(val<tr[p].val)return GetRankByVal(tr[p].lc,val);elsereturn GetRankByVal(tr[p].rc,val)+tr[tr[p].lc].s+tr[p].num;//这里类似于前缀和的思想，tr[tr[p].lc].s为比当前值小的个数，tr[p].num为当前值重复的次数
}
int GetValByRank(int p,int r) {//根据排名来找值if(!p)return 0;if(tr[tr[p].lc].s>=r)//缩小了查找的区间return GetValByRank(tr[p].lc,r);if(tr[tr[p].lc].s+tr[p].num>=r)//找到了查找的区间return tr[p].val;return GetValByRank(tr[p].rc,r-tr[tr[p].lc].s-tr[p].num);//在右子树中找排名需要变更，与上一个函数意思类似，注意排名始终是相对于当前值对应的子树的
}
int main() {ios::sync_with_stdio(0),cin.tie(0);cin >>n;while(n--) {cin >>opt>>x;switch(opt) {case 1:Insert(root,x);break;case 2:Delete(root,x);break;case 3:cout <<GetRankByVal(root,x)<<endl;break;case 4:cout <<GetValByRank(root,x)<<endl;break;case 5:cout <<GetPre(x)<<endl;break;case 6:cout <<GetNext(x)<<endl;break;}}return 0;
}

POJ1442

题目大意：一个数据库，存储一个整数数组和一个特殊的i变量，初始时刻数据库为空，i=0，处理一系列命令，有两种命令：①ADD(x)，将元素x放入数据库中;②GET，将i增加1，并给出包含在数据库中所有整数中第i小的值，第i小的值是数据库中按非降序排序后第i个位置的数字，给出M个元素构成的序列A，代表数据库中的一系列元素，给出N个元素构成的序列u，对u序列的第p个元素执行GET命令，输出结果（等价于找A(1）,A（2），…A（u§）序列中第p小的数）

思路：和模板思路差不多，题意需要理解，u=(1,2,6,6)代表在数据库中有1个数时查第1小，有2个数时查第2小，有6个数时查第3小，有6个数时查第4小
在查找第k小的时候，使用和上一题逆转的思路，具体看代码

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
//#include <unordered_map>
#include <map>
#include <set>
#include <numeric>
#include <stack>
#include <sstream>
#include <cmath>
#include <bitset>
//#include <unordered_set>
#include <functional>
#include <list>
#include <vector>
#include <iterator>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 Bint;
const int maxn=1e7+10;
int cnt,root,n,m,A[maxn],u[maxn];
struct node {int pri,val,num,s,lc,rc;
} tr[maxn];
void Update(int p) {tr[p].s=tr[tr[p].lc].s+tr[tr[p].rc].s+tr[p].num;
}
int New(int val) {tr[++cnt].val=val;tr[cnt].lc=tr[cnt].rc=0;tr[cnt].s=tr[cnt].num=1;tr[cnt].pri=rand();return cnt;
}
void zig(int &p) {int q=tr[p].lc;tr[p].lc=tr[q].rc;tr[q].rc=p;tr[q].s=tr[p].s;Update(p);p=q;
}
void zag(int &p) {int q=tr[p].rc;tr[p].rc=tr[q].lc;tr[q].lc=p;tr[q].s=tr[p].s;Update(p);p=q;
}
void Insert(int &p,int val) {if(!p) {p=New(val);return ;}tr[p].s++;if(val==tr[p].val)tr[p].num++;else if(val<tr[p].val) {Insert(tr[p].lc,val);if(tr[tr[p].lc].pri>tr[p].pri)zig(p);} else {Insert(tr[p].rc,val);if(tr[tr[p].rc].pri>tr[p].pri)zag(p);}
}
int Findkth(int &p,int k) {//与上一个题的思路类似，找第k小if(!p)return 0;//如果找不到int t=tr[tr[p].lc].s;//获得以当前节点为根的树规模大小if(k<t+1)return Findkth(tr[p].lc,k);//如果当前规模大于k，左子树else if(k>t+tr[p].num)return Findkth(tr[p].rc,k-(t+tr[p].num));//否则右子树，并且更新需要找的排名return tr[p].val;//找到了，返回值
}
int main() {//srand(time(0));用了就会Runtime Errorwhile(~scanf("%d%d",&n,&m)) {for(int i=1; i<=n; i++)scanf("%d",A+i);for(int j=1; j<=m; j++)scanf("%d",u+j);int i=1,j=1;while(i<=m) {while(j<=u[i])Insert(root,A[j++]);printf("%dn",Findkth(root,i++));}root=cnt=0;}return 0;
}

HDU4585

题目大意：少林寺有N个僧人，每个僧人有一个独特的身份（编号）和战斗等级（数值），均为整数。新僧人必须与一位战斗等级最接近他的老僧人战斗，若有两个老僧人满足这个条件，则新僧人将选择战斗等级更低的，已知第一个僧人编号为1，战斗等级为十万，他刚刚失去了战斗记录，但记得加入的人，请恢复战斗记录

思路：Treap的插入，查找第k小值，按照值找排名，对于插入的数据每次查找它前后相邻的两个节点，比较得最优解，由于题目给定了大小每个数据是不一样的，所以可以建一个索引，其余见代码

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <unordered_map>
#include <map>
#include <set>
#include <numeric>
#include <stack>
#include <sstream>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <functional>
#include <list>
#include <vector>
#include <iterator>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 Bint;
const int maxn=5e6+10;
struct node {int val,lc,rc,pri,num,s;
} tr[maxn];
int cnt,root,n,id[maxn];
void Update(int p) {tr[p].s=tr[tr[p].lc].s+tr[tr[p].rc].s+tr[p].num;
}
int New(int val) {tr[++cnt].val=val;tr[cnt].lc=tr[cnt].rc=0;tr[cnt].s=tr[cnt].num=1;tr[cnt].pri=rand();return cnt;
}
void zig(int &p) {int q=tr[p].lc;tr[p].lc=tr[q].rc;tr[q].rc=p;tr[q].s=tr[p].s;Update(p);p=q;
}
void zag(int &p) {int q=tr[p].rc;tr[p].rc=tr[q].lc;tr[q].lc=p;tr[q].s=tr[p].s;Update(p);p=q;
}
void Insert(int &p,int val) {if(!p) {p=New(val);return;}tr[p].s++;if(val==tr[p].val) {tr[p].num++;return;}if(val<tr[p].val) {Insert(tr[p].lc,val);if(tr[p].pri<tr[tr[p].lc].pri)zig(p);} else {Insert(tr[p].rc,val);if(tr[p].pri<tr[tr[p].rc].pri)zag(p);}
}
int Findkth(int p,int k) {if(!p)return 0;int t=tr[tr[p].lc].s;if(k<t+1)return Findkth(tr[p].lc,k);else if(k>t+tr[p].num)return Findkth(tr[p].rc,k-(t+tr[p].num));return tr[p].val;
}
int Rank(int p,int val) {if(!p)return 0;if(tr[p].val==val)return tr[tr[p].lc].s+1;//因为还要插入一个，所以+1if(val<tr[p].val)return Rank(tr[p].lc,val);//在左子树直接进左return Rank(tr[p].rc,val)+tr[tr[p].lc].s+tr[p].num;//入右子树，但是要加上左子树的规模
}
int main() {ios::sync_with_stdio(0),cin.tie();while(cin >>n&&n) {int ans1=0,ans2=0,a,b;root=cnt=0;memset(id,0,sizeof(id));cin >>a>>b;cout <<a<<" "<<1<<endl;id[b]=a;//记录等级对应的编号，每个等级唯一Insert(root,b);for(int i=1; i<n; i++) {cin >>a>>b;id[b]=a;Insert(root,b);int t;int k=Rank(root,b);ans1=Findkth(root,k-1);ans2=Findkth(root,k+1);if(!ans1)t=ans2;else if(!ans2)t=ans1;elset=(b-ans1<=ans2-b?ans1:ans2);cout <<a<<" "<<id[t]<<endl;}}return 0;
}

总结

Treap是二叉搜索树中较为基础简单的一种，其应用范围有限，完成的功能主要是单点操作，如单点根据排名查找值或根据值查找排名，插入，删除等，Treap可以作为树套树中线段树套平衡树中平衡树的选项，虽然代码较为复杂，但是逻辑还是比较好理清楚的

Treap与其他树的比较：
Treap最突出的特点就是代码量小且容易理解，在大量数据下，其效率高于直接依赖于数据大小关系的AVL树。
Treap与Splay相比则逊色许多了，因为Splay不仅能实现Treap的各种功能，还能进行区间操作。
Treap的结构相较于红黑树更平衡，搜索效率前者高于后者，但是插入删除的效率后者高于前者

更多可参考最强平衡树——Treap[以我的最弱击败你的最强]

Treap的适用范围：其本质与AVL树差不多，不过是维护平衡的方式不同，因此AVL树能做的Treap基本也能做，而且Treap的效率和可靠相对更高，一般处理单点查找、修改、删除以及排名与值之间的相互对应，在题目不复杂的情况下可以使用Treap作为一种维护数据的数据结构，Treap还可以与树套树一起使用