Ryan_<

treap构造比线段树要容易得多~主要核心就是【通过旋转让BST的Pro域满足堆的性质】

所以线段树笔记还没写完呢..发条文章只是证明自己还在努力往前走;<

#include<iostream>
#include<cstring>
#include<algorithm>
#include<ctime>
//#include<Ryan.Treap>
//这里的heap为小根堆(这里的小并不严格）
//0表示无该节点，叶节点的左右结点均为0
using namespace std;
const int M=10000+5;
struct Treap
{
	int key;//值
	int pro;//优先级
	int L,r;//左右结点编号
	int Ln,rn;//左右子树节点个数
}Tree[M];
void Zig(int &p)
//左旋：当前根节点变为其右节点的左子节点，其右节点变为根节点
{
	int t=Tree[p].r;//p的右节点叫r
	//关键变化:t将他的左节点给p作为右节点
	//t的左节点由p补上
	//这两个步骤显然是不能颠倒的
	Tree[p].r=Tree[t].L;
	Tree[t].L=p;
	//显而易见的变化：
	//因为t把它的左子树给p当做右子树
	Tree[p].rn=Tree[t].Ln;
	Tree[t].Ln=1+Tree[p].Ln+Tree[p].rn;
	p=t;//苍天已死，黄天当立——根节点改变
}
void Zag(int &p)
//右旋:当前根节点变为其左节点的右子节点，其左节点变为根节点
{
	int t=Tree[p].L;
	Tree[p].L=Tree[t].r;
	Tree[t].r=p;
	Tree[p].Ln=Tree[t].rn;
	Tree[t].rn1+Tree[p].Ln+Tree[p].rn;
	p=t;
}
void Insert(int &p,int x)//父节点编号
{
	if(p==0)//该节点没有父节点
	{
		tot++;p=tot;
		Tree[p].key=x;
		Tree[p].L=Tree[p].r=0;
		Tree[p].Ln=Tree[p].rn=0;
		Tree[p].pro=rand%10000;
		return;//递归的出口
	}
	if(x<=Tree[p].key)
	//递归插入左子树到叶节点，然后逐层往上依据优先级旋转调整位置
	{
		Insert(Tree[p].L,x);
		Tree[p].Ln++;
		if(Tree[Tree[p].L].pro<Tree[p].pro) Zag(p);
	}
	else
	{
		Insert(Tree[p].r,x);
		Tree[p].rn++;
		if(Tree[Tree[p].r].pro<Tree[p].pro) Zig(p);
	}
}
void Del(int &p,int x)//在编号为p的子树中删除数值x
{
	if(x<Tree[p].key)
	{
		Tree[p].Ln--;//先改变p的属性
		Del(Tree[p].L,x);//再从左子树中递归删除
	}
	else if(x>Tree[p].key)
	{
		Tree[p].rn--;
		Del(Tree[p].r,x);
	}
	else if(x==Tree[p].key)//找到要删除数值对应的节点
	{
		if(!Tree[p].L&&!Tree[p].r)
		//递归出口！
		{
			p=0;
			Tree[p].key=0;
//		Tree[p].pro=0;
			return;
		}
		int lp=INF,rp=INF;//inf应用于一端子树不存在的情况
		if(Tree[p].L) lp=Tree[Tree[p].L].pro;
		if(Tree[p].r) rp=Tree[Tree[p].r].pro;
//有点像物理过程？权值重吊在下面,权值轻的被拉上去
		if(lp<=rp)
		{
			Zag();
			Tree[p].rn--;//这个好好理解！
			Del(Tree[p].r,x);
		}
		else
		{
			Zig();
			Tree[p].Ln--;
			Del(Tree[p].L,x);
		}
	}
}
bool Find(int p,int x)
{
	if(p==0) return 0;
	else if(x==Tree[p].key) return 1;
	else if(x<Tree[p].key) return Find(Tree[p].L,x);
									else return Find(Tree[p].r,x);
}
int Findk(int p,int k)//不可以加&
{
	if(1+Tree[p].Ln+Tree[p].rn<k) return -1;
	if(1+Tree[p].Ln==k) return Tree[p].key;
	if(k<Tree[p].Ln) return Findk(Tree[p].L,k);
	else return Findk(Tree[p].r,k-1-Tree[p].Ln);
}
/*生成随机数*/
#include<iostream>
int main()
{
	int x;
	srand((unsigned)time(NULL));//初始化随机函数
	for(int i=1;i<=10;i++)
	{
		x=rand()%100;
		cout<<x<<endl;
	}
	return 0; 
}