当前位置： 首页 > news >正文

数据结构（5） treap

news 来源：原创 2024/11/27 22:28:34

活动 - AcWing

参考—《算法竞赛进阶指南》-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<tr[2].val) zag(root);
}

（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<iostream>
#include<algorithm>
#include<cstring>
using 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].val<tr[2].val) zag(root);
}

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);
}

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<<get_rank_by_key(root,x)-1<<endl;
        else if(op==4)  cout<<get_key_by_rank(root,x+1)<<endl; 
        else if(op==5)  cout<<get_prev(root,x)<<endl;
        else
        {
            cout<<get_next(root,x)<<endl;
        }
    }
    
    return 0;
}

实际应用

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using 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].val<tr[tr[root].r].val) zag(root);
}

void insert(int &p,int key)
{
    if(!p) p=get_node(key);
    else if(tr[p].key==key) return;
    else if(tr[p].key>key)
    {
        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<key) return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));
}

int main()
{
    build();
    cin>>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<<res;
    return 0;
}

作者：yankai
链接：https://www.acwing.com/activity/content/code/content/5279849/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

相关文章：

  • div+css网站后台模板/搜索引擎营销优缺点
  • 淘宝优惠的网站怎么做/江西百度推广开户多少钱
  • 湖南城市建设职业技术学院官方网站/奇零seo赚钱培训
  • 深圳网站建设服务平台/友情链接联盟
  • 顺德建网站的公司/百度营销后台
  • 济南建设网站的公司吗/武汉关键词包年推广
  • docker-14-容器化安装Linux并查看系统版本
  • 百度安全在线查询提示风险原因分析与解决思路
  • 车载以太网 - 车辆信息和车辆声明 - 09
  • CSRF(跨站请求伪造)
  • 用开放、安全的DDS变革数据的分发
  • 从零开始 verilog 以太网交换机（二）MAC接收控制器的设计与实现
  • Task3 Excel快捷键
  • springcloudalibaba整合nacos
  • 监控安防人员入门基础
  • WebRTC系列-Qos系列之发送NACK
  • Java基本数据类型及其包装类
  • 工业互联网2022：第一梯队成型、专精玩家突围