题意:裸的平衡树题
平衡树功能:插入,删除最大,删除最小
挂一个SBT模板吧,明天就校赛了,所以重写了一下SBT,把原来的删除操作改了下:
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 1111111,INF = 10000001;
struct Key{
int k,p;
Key(){}
Key(int kk,int pp):k(kk),p(pp){}
bool operator < (const Key &ke) const{
return p<ke.p;
}
bool operator >= (const Key &ke) const{
return !(*this<ke);
}
bool operator == (const Key &ke) const{
return p==ke.p;
}
}k[MAXN];
int l[MAXN],r[MAXN],pool[MAXN],size[MAXN],T,top,node;
void build(){
T = top = node = 0;
}
void left_rotate(int &x){
int q = r[x];
r[x] = l[q];
l[q] = x;
size[q] = size[x];
size[x] = size[l[x]]+size[r[x]]+1;
x = q;
}
void right_rotate(int &x){
int q = l[x];
l[x] = r[q];
r[q] = x;
size[q] = size[x];
size[x] = size[l[x]]+size[r[x]]+1;
x = q;
}
int newnode(Key key){
int x;
if(top!=0){
x = pool[--top];
}else{
x = ++node;
}
k[x] = key;
size[x] = 1; l[x] = r[x] = 0;
return x;
}
void delnode(int x){
pool[top++] = x;
size[x] = l[x] = r[x] = 0;
}
void Maintain(int &T,bool flag){
if(!flag){
if(size[l[l[T]]]>size[r[T]]){
right_rotate(T);
}else if(size[r[l[T]]]>size[r[T]]){
left_rotate(l[T]);
right_rotate(T);
}else{
return;
}
}else{
if(size[r[r[T]]]>size[l[T]]){
left_rotate(T);
}else if(size[l[r[T]]]>size[l[T]]){
right_rotate(r[T]);
left_rotate(T);
}else{
return;
}
}
Maintain(l[T],0);
Maintain(r[T],1);
Maintain(T,0);
Maintain(T,1);
}
void Insert(int &T,Key key){
if(!T){
T = newnode(key);
return;
}
size[T]++;
if(key<k[T])Insert(l[T],key);
else Insert(r[T],key);
Maintain(T,key>=k[T]);
}
Key Delete(int &T,Key key){
if(!T)return Key(INF,INF);//no element to delete
size[T]--;
if((key==k[T])||(key<k[T]&&l[T]==0)||(key>=k[T]&&r[T]==0)){
Key ret = k[T]; int x = T;
if(l[T]==0||r[T]==0){
T = l[T]+r[T];
delnode(x);//释放结点内存
}else{
key.p++;
k[T] = Delete(r[T],key);
}
return ret;
}
if(key<k[T])Delete(l[T],key);
else Delete(r[T],key);
}
Key DeleteMax(int &T){
if(!T)return Key(INF,INF);
if(r[T])return DeleteMax(r[T]);
int x = T; Key key = k[T];
T = l[T];
delnode(x);
return key;
}
Key DeleteMin(int &T){
if(!T)return Key(INF,INF);
if(l[T])return DeleteMin(l[T]);
int x = T; Key key = k[T];
T = r[T];
delnode(x);
return key;
}
Key Select(int T,int st){
if(!T)return Key(INF,INF);
int rank = size[l[T]]+1;
if(st==rank)return k[T];
else if(st<rank)return Select(l[T],st);
else return Select(r[T],st-rank);
}
int Rank(int T,Key key){
if(!T)return -1;
if(key==k[T])return size[l[T]]+1;
else if(key<K[T])return Rank(l[T],key);
else return size[l[T]]+1+Rank(r[T],key);
}
int main(){
int op,rst,sec;
build();
//freopen("out.txt","w",stdout);
while(scanf("%d",&op),op){
if(op==1){
scanf("%d%d",&rst,&sec);
Insert(T,Key(rst,sec));
}else if(op==2){
Key key = Select(T,size[T]);
if(key.k==INF)printf("0\n");
else printf("%d\n",key.k);
Delete(T,key);
}else{
Key key = Select(T,1);
if(key.k==INF)printf("0\n");
else printf("%d\n",key.k);
Delete(T,key);
}
}
return 0;
}
分享到:
相关推荐
将bst文件放到MiKTeX的bst文件夹下自己新建的gbt7714-2005文件下,1)作者名称如 KERNER B S 的样式 GBT7714-2005NLang.bst 2)作者名称如 KERNER B S 的样式 GBT7714-2005NLang_UP.bst 3)作者名称如 Kerner B S 的...
BME280 The BME280 is an integrated environmental sensor developed specifically for mobile applications where size and low power consumption are key design constraints. The unit combines individual ...
BST-BMP180-DS000-07.pdf英文资料
51代码,51单片机所有代码,定时器、数码管、iIC、led、数码管
BOSH bmp189 气体传感器说明文档,希望对初学者有用
舵机供电模块超声波模块供电口舵机模块电机模块红外检测模块检测提示模块电源提示灯亚博 BST-V51 智能小车底板电路原理图。
视频,源代码,光盘配套一切资料
bst-bmi270-sf000 数据手册1
希望通过这个小东西可以帮到大家这是一个四位数码管时钟代码
bmi088 芯片手册
A application about binary search tree, Insert, Delete, Find, Print node.
BST-物料纠偏系统ERK 1000H使用手册pdf,BST-物料纠偏系统ERK 1000H使用手册
ST digital pressure sensor BMP280 spec
有助于理解二叉搜索树以及自平衡二叉搜索树
This is BMP280 data sheet, you can reference it.
bst-bmi160-彩页1
BMP180 是测气压和温度的芯片,本资源是他的规格书,希望能给大家提供方便!
bst-dhw-fl022 评估板1
BST_from_preorder_traversal.cpp - 2sum.cpp - remove_adjacent_duplicates.cpp - 子集.cpp - 子集_2.cpp - Remove_Nth_Node_From_End_of_List.cpp - invert_Binary_Tree.cpp - 对称树.cpp - BST_Or_Not.cpp - ...
BST 中的第 K 个最小元素 - 问题 :right_arrow: 计算全为 1 的平方子矩阵 - 问题 :right_arrow: 第 4 周 按频率排序字符 - 问题 :right_arrow: 区间列表交点 - 问题 :right_arrow: 从前序遍历构建二叉搜索树 - 问题 ...