Hihocoder 1325 平衡树·Treap（平衡树，Treap）
Description
小Ho：小Hi，我发现我们以前讲过的两个数据结构特别相似。
小Hi：你说的是哪两个啊？
小Ho：就是二叉排序树和堆啊，你看这两种数据结构都是构造了一个二叉树，一个节点有一个父亲和两个儿子。 如果用1..n的数组来存储的话，对于二叉树上的一个编号为k的节点，其父亲节点刚好是k/2。并且它的两个儿子节点分别为k2和k2+1，计算起来非常方便呢。
小Hi：没错，但是小Hi你知道有一种办法可以把堆和二叉搜索树合并起来，成为一个新的数据结构么？
小Ho：这我倒没想过。不过二叉搜索树满足左子树<根节点<右子树，而堆是满足根节点小于等于(或大于等于)左右儿子。这两种性质是冲突的啊？
小Hi：恩，你说的没错，这两种性质的确是冲突的。
小Ho：那你说的合并是怎么做到的？
小Hi：当然有办法了，其实它是这样的....
第1行：1个正整数n，表示操作数量，10≤n≤100,000
第2..n+1行：每行1个字母c和1个整数k：
若c为'I'，表示插入一个数字k到树中，-1,000,000,000≤k≤1,000,000,000
若c为'Q'，表示询问树中不超过k的最大数字
Output
若干行：每行1个整数，表示针对询问的回答，保证一定有合法的解
5 I 3 I 2 Q 3 I 5 Q 4
Sample Output
3 3
Http
Hihocoder:http://hihocoder.com/problemset/problem/1325?sid=1122544
Source
二叉平衡树 Treap
解决思路
Treap学习题（待以后补充）
代码
/*
警告：本题代码或许在指针使用上存在问题，等待博主重构数组版。（虽然说这份代码能在Hihocoder上通过，但有读者反映可能会出现RE）
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
class Treap
{
public:
int key,ran;
int size;
Treap * ch[2];
Treap(int k)
{
key=k;
ran=rand();
ch[0]=ch[1]=NULL;
size=1;
}
int compare(int k)
{
if (k==key)
return -1;
return k<key?0:1;
}
void maintain()
{
size=1;
if (ch[0]!=NULL)
size+=ch[0]->size;
if (ch[1]!=NULL)
size+=ch[1]->size;
}
};
const int inf=2147483647;
int n;
void Rotate(Treap* &T,int f);//0代表左旋，1代表右旋
void Insert(Treap* &T,int value);
int Find(Treap * T,int value);
int Find_k(Treap * T,int value);
void print(Treap *T);
int main()
{
Treap* root=NULL;
cin>>n;
for (int i=1;i<=n;i++)
{
char ch;
int x;
cin>>ch>>x;
if (ch=='I')
{
//cout<<"x "<<x<<endl;
Insert(root,x);
}
else
{
//cout<<Find(root,x)<<"aa"<<endl;
cout<<Find_k(root,x)<<endl;
}
//cout<<i<<":"<<endl;
//print(root);
//cout<<endl;
}
}
void Rotate(Treap* &T,int f)
{
Treap* son=T->ch[f^1];//左旋处理的是右子树，而右旋处理的是左子树
T->ch[f^1]=son->ch[f];
son->ch[f]=T;
T->maintain();
son->maintain();
T=son;
}
void Insert(Treap* &T,int value)
{
if (T==NULL)
T=new Treap(value);
else
{
int f=value<(T->key) ? 0 :1;
//cout<<value<<' '<<f<<' '<<(T->ch[0]==NULL)<<(T->ch[1]==NULL)<<endl;
Insert(T->ch[f],value);
if ((T->ch[f]->ran)>(T->ran))
Rotate(T,f^1);//如果是右子树则左旋，如果是左子树则右旋
}
T->maintain();
}
int Find(Treap * T,int value)
{
while (T!=NULL)
{
//cout<<"Find_In"<<endl;
int f=T->compare(value);
if (f==-1)
return 1;
T=T->ch[f];
}
return 0;
}
int Find_k(Treap * T,int value)
{
//cout<<"In"<<endl;
//cout<<T->ch[0]<<' '<<T->ch[1]<<endl;
//int Ans=T->key;
//cout<<"Init_Ans:"<<Ans<<endl;
int Ans=-inf;
while (T!=NULL)
{
//cout<<"Find_k :"<<T->key<<endl;
//cout<<value<<' '<<T->key<<endl;
if (T->key<=value)
Ans=max(Ans,T->key);
int f=T->compare(value);
if (f==-1) return value;
T=T->ch[f];
//Ans=T->key;
}
return Ans;
}
void Delete(Treap* &T,int value)
{
int f=T->compare(value);
if (f==-1)
{
Treap* &T2=T;//因为后面要修改T指向，所以先用一个T2存下指针
if (T->ch[0]==NULL)
{
T=T->ch[1];
delete T2;
T2=NULL;
}
else
if (T->ch[1]==NULL)
{
T=T->ch[0];
delete T2;
T2=NULL;
}
else
{
int f2=T->ch[0]->ran > T->ch[1]->ran ? 1:0;
Rotate(T,f2);
Delete(T->ch[f2],value);
}
}
else Delete(T->ch[f],value);
if (T!=NULL)
T->maintain();
}
void print(Treap *T)
{
if (T==NULL)
return;
cout<<T->key<<'(';
print(T->ch[0]);
cout<<',';
print(T->ch[1]);
cout<<')';
return;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7144428.html
