活动 - AcWing
宜君网站制作公司哪家好,找创新互联!从网页设计、网站建设、微信开发、APP开发、自适应网站建设等网站项目制作,到程序开发,运营维护。创新互联于2013年创立到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选创新互联。参考—《算法竞赛进阶指南》-lyd
目录
一、概述
二、具体操作详解
1.常见操作
2.结构定义
3.操作基础函数
(1)pushup
(2) 获得一个新节点
(3)左旋右旋
(4)建树
(5)插入操作(如插入k)
(6)删除操作
(7) 查询操作
实际应用
满足bst性质的二叉查找树不是唯一的。我们可以通过改变二叉查找树的形态,使得左右子树大小达到平衡,从而使整棵树的深度维持在logn级别。
改变方式分为“左旋”和“右旋”。具体方式请参考数据结构教材。
Treap是tree和heap的合成词。如果节点值是随机的,那么构成的树深度平均为logn级别。
Treap在插入新节点时,给该节点一个随机的权值。然后像二叉堆的插入过程一样,自底向上检查,当某个节点不满足大根堆性质的时候就执行单旋转,使得该点与其父节点的关系发生对换。
特别地,对于删除操作,我们可以直接把删除节点向下旋转成叶节点,然后直接删掉。
总之,Treap通过适当的单旋转,维持了bst性质,同时还使得节点上随机生成的额外权值满足大根堆性质。所有操作都是logN级别。
二、具体操作详解 1.常见操作2.结构定义int n;
struct Node{
int l,r;
int key,val;
int cnt,size;
}tr[N];
int root,idx;
l,r表示左右子节点编号。key表示节点的值,val表示随机权值。cnt表示当前的key出现了多少次,size表示这整个子树有多少个节点。
cnt和size都是为了满足根据排名求值 和根据值求排名这两个操作设立的
3.操作基础函数 (1)pushup根据子节点计算size。为了3 4操作
void pushup(int p)
{
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
(2) 获得一个新节点int get_node(int key)
{
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=tr[idx].size=1;
return idx;
}
(3)左旋右旋注意引用
void zig(int &p)//右旋
{
int q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
pushup(tr[p].r),pushup(p);
}
void zag(int &p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
pushup(tr[p].l),pushup(p);
}
(4)建树安排两个哨兵。哨兵先后顺序不要反了。
void build()
{
get_node(-INF),get_node(INF);
root=1,tr[root].r=2;
pushup(root);
if(tr[1].val(5)插入操作(如插入k)如果p为空,就创建一个新节点。
如果当前key==k,则该节点cnt++
如果大于k,则在左子树插入,回溯时根据需要右旋
如果小于k,则在右子树插入,回溯时根据需要左旋
最后对每个节点,由于插入改变了子树信息,所以要pushup当前节点
void insert(int &p,int key)
{
if(!p) p=get_node(key);
else if(tr[p].key==key) tr[p].cnt++;
else if(tr[p].key>key)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[tr[p].r].val) zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[tr[p].l].val) zag(p);
}
pushup(p);
}
(6)删除操作如果空节点,则无意义,直接return
如果当前节点key==k:
如果cnt>1,直接cnt--即可
如果不是叶节点:
如果没有右子树,或者需要右旋:就右旋,然后递归在p的右子树上删除
对应的如果没有左子树或者需要左旋:就左旋,然后递归左子树
剩下情况为叶节点:直接p=0删除即可
如果当前节点key>k 递归左子树
else 递归右子树
最后依然需要记得pushup!!!!
void remove(int &p,int key)
{
if(!p) return;
if(tr[p].key==key)
{
if(tr[p].cnt>1) tr[p].cnt--;
else if(tr[p].l||tr[p].r)
{
if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r,key);
}
else
{
zag(p);
remove(tr[p].l,key);
}
}
else p=0;
}
else if(tr[p].key>key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}
(7) 查询操作int get_rank_by_key(int p,int key)
{
if(!p) return 0;
if(tr[p].key==key) return tr[tr[p].l].size+1;
if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank)
{
if(!p) return INF;
if(tr[tr[p].l].size>=rank) return get_key_by_rank(tr[p].l,rank);
if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].key;
return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
int get_prev(int p,int key)
{
if(!p) return -INF;
if(tr[p].key>=key) return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p, int key) // 找到严格大于key的最小数
{
if (!p) return INF;
if (tr[p].key<= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}
完整代码:
#include#include
#includeusing namespace std;
const int N =1e5+10,INF=1e8;
int n;
struct Node{
int l,r;
int key,val;
int cnt,size;
}tr[N];
int root,idx;
void pushup(int p)
{
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
int get_node(int key)
{
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=tr[idx].size=1;
return idx;
}
void zig(int &p)//右旋
{
int q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
pushup(tr[p].r),pushup(p);
}
void zag(int &p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
pushup(tr[p].l),pushup(p);
}
void build()
{
get_node(-INF),get_node(INF);
root=1,tr[root].r=2;
pushup(root);
if(tr[1].valkey)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[tr[p].r].val) zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[tr[p].l].val) zag(p);
}
pushup(p);
}
void remove(int &p,int key)
{
if(!p) return;
if(tr[p].key==key)
{
if(tr[p].cnt>1) tr[p].cnt--;
else if(tr[p].l||tr[p].r)
{
if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r,key);
}
else
{
zag(p);
remove(tr[p].l,key);
}
}
else p=0;
}
else if(tr[p].key>key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}
int get_rank_by_key(int p,int key)
{
if(!p) return 0;
if(tr[p].key==key) return tr[tr[p].l].size+1;
if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank)
{
if(!p) return INF;
if(tr[tr[p].l].size>=rank) return get_key_by_rank(tr[p].l,rank);
if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].key;
return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
int get_prev(int p,int key)
{
if(!p) return -INF;
if(tr[p].key>=key) return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p, int key) // 找到严格大于key的最小数
{
if (!p) return INF;
if (tr[p].key<= key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
build();
cin>>n;
while(n--)
{
int op,x;
cin>>op>>x;
if(op==1) insert(root,x);
else if(op==2) remove(root,x);
else if(op==3) cout<实际应用#include#include
#include#includeusing namespace std;
const int N =33010,INF=1e8;
typedef long long LL;
int n;
struct Node{
int l,r;
int key,val;
}tr[N];
int root,idx;
int get_node(int key)
{
tr[++idx].key=key;
tr[idx].val=rand();
return idx;
}
void zig(int &p)
{
int q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
}
void zag(int &p)
{
int q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
}
void build()
{
get_node(-INF),get_node(INF);
root=1,tr[root].r=2;
//if(tr[root].valkey)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[p].val) zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[p].val) zag(p);
}
}
int get_prev(int p,int key)
{
if(!p) return -INF;
if(tr[p].key>key) return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p,int key)
{
if(!p) return INF;
if(tr[p].key>n;
LL res=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(i==1) res+=x;
else res+= min(x - get_prev(root,x),get_next(root,x)-x);
insert(root,x);
}
cout<你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章题目:数据结构(5)treap-创新互联
文章链接:http://cdkjz.cn/article/deccsh.html