平衡树之Treap

二叉搜索树

性质：一个节点x左子树所有点的关键字都比x的关键字小，右子树所有点的关键字都比x的关键字大

treap

“树堆” “Tree+Heap”

性质：每个点随机分配一个权值，使treap同时满足堆性质和二叉搜索树性质

复杂度：期望O(logn)

设每个节点的关键字是key，随机权值是rand

如果v是u的左儿子，则key[v]<key[u]

如果v是u的右儿子，则key[v]>key[u]

如果v是u的子节点，则rand[u]>rand[v]

treap维护权值的时候一般会把相同的权值放在同一个节点上

所以一个treap节点需要维护以下信息：

1.左右儿子

2.关键字

3.关键字出现次数

4.堆随机值

5.节点大小（即子树大小）

旋转

平衡二叉搜索树主要通过旋转来保持树的平衡，即保证复杂度

旋转有单旋和双旋，treap只需要单旋，这一点比较简单

void lturn(int &k)//treap的旋转 
{
	int t=tr[k].r;
	tr[k].r=tr[t].l;
	tr[t].l=k;
	tr[t].size=tr[k].size;
	update(k);
	k=t;
}

void rturn(int &k)
{
	int t=tr[k].l;
	tr[k].l=tr[t].r;
	tr[t].r=k;
	tr[t].size=tr[k].size;
	update(k);
	k=t;
}

treap的插入

先给这个节点分配一个随机的堆权值

然后把这个节点按照BST的规则插入到一个叶子上:

从根节点开始，逐个判断当前节点的值与插入值的大小关系。如果插入值小于当前节点值，则递归至左儿子；大于则递归至右儿子；

然后通过旋转来调整，使得treap满足堆性质

void insert(int &k,int x)//treap的插入 
{
	if(!k)
	{
		size++;
		k=size;
		tr[k].size=tr[k].w=1;
		tr[k].v=x;
		tr[k].rnd=rand();
		return ;
	}
	tr[k].size++;
	if(tr[k].v==x)
		tr[k].w++;
	else if(x>tr[k].v)
	{
		insert(tr[k].r,x);
		if(tr[tr[k].r].rnd<tr[k].rnd)
			lturn(k);
	}
	else
	{
		insert(tr[k].l,x);
		if(tr[tr[k].l].rnd<tr[k].rnd)
			rturn(k);
	}
}

treap的删除

和普通的BST删除一样：

如果插入值小于当前节点值，则递归至左儿子；大于则递归至右儿子

若当前节点数值的出现次数大于1，则减一（通常将同一个权值缩掉）

若当前节点数值的出现次数等于1：

若当前节点没有左儿子与右儿子，则直接删除该节点（置为0）；

若当前节点没有左儿子或右儿子，则将左儿子或右儿子替代该节点

若当前节点有左儿子与右儿子，则不断旋转当前节点，并走到当前节点新的对应位置，直到没有左儿子和右儿子为止。

void del(int &k,int x)//treap的删除
{
	if(!k)
		return;
	if(tr[k]==x)
	{
		if(tr[k].w>1)//若不止相同值的个数有多个，删去一个 
		{
			tr[k].w--;
			tr[k].size--;
			return ;	
		}
		if(tr[k].l*tr[k].r==0)//有一个儿子为空 
			k=tr[k].l+tr[k].r;
		else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd)
			rturn(k),del(k,x);
		else
			lturn(k),del(k,x);
	}
	else if(x>tr[k].v)
		tr[k].size--,del(tr[k].r,x);
	else
		tr[k].size--,del(tr[k].l,x);	
} 

treap的查询

递归到叶子节点，一路维护信息即可

int query_rank(int k,int x)//treap的查询
{
	if(!k)
		return 0;
	if(tr[k].v==x)	
		return tr[tr[k].l].size+1;
	else if(x>tr[k].v)
		return tr[tr[k].l].size+tr[k].w+query_rank(tr[k].r+x);
	else
		return query_rank(tr[k].l,x); 
} 

int query_num(int k,int x)
{
	if(!k)
		return 0;
	if(x<=tr[tr[k].l].size)
		return query_num(tr[k].l,x);
	else if(x>tr[tr[k].l].size+tr[k].w)
		return query_num(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
	else
		return tr[k].v;
}

treap还可以支持维护序列时的分裂合并，这里不详细讲了

#include<iostream>
#include<cstdio>

struct data()
{
	int l;
	int r;
	int v;
	int size;
	int rnd;
	int w;
}tr[100005];

int n,size,root,ans;

void update(int k)//更新节点信息 
{
	tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w;
}

void lturn(int &k)//treap的旋转 
{
	int t=tr[k].r;
	tr[k].r=tr[t].l;
	tr[t].l=k;
	tr[t].size=tr[k].size;
	update(k);
	k=t;
}

void rturn(int &k)
{
	int t=tr[k].l;
	tr[k].l=tr[t].r;
	tr[t].r=k;
	tr[t].size=tr[k].size;
	update(k);
	k=t;
}

void insert(int &k,int x)//treap的插入 
{
	if(!k)
	{
		size++;
		k=size;
		tr[k].size=tr[k].w=1;
		tr[k].v=x;
		tr[k].rnd=rand();
		return ;
	}
	tr[k].size++;
	if(tr[k].v==x)
		tr[k].w++;
	else if(x>tr[k].v)
	{
		insert(tr[k].r,x);
		if(tr[tr[k].r].rnd<tr[k].rnd)
			lturn(k);
	}
	else
	{
		insert(tr[k].l,x);
		if(tr[tr[k].l].rnd<tr[k].rnd)
			rturn(k);
	}
}

void del(int &k,int x)//treap的删除
{
	if(!k)
		return;
	if(tr[k]==x)
	{
		if(tr[k].w>1)//若不止相同值的个数有多个，删去一个 
		{
			tr[k].w--;
			tr[k].size--;
			return ;	
		}
		if(tr[k].l*tr[k].r==0)//有一个儿子为空 
			k=tr[k].l+tr[k].r;
		else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd)
			rturn(k),del(k,x);
		else
			lturn(k),del(k,x);
	}
	else if(x>tr[k].v)
		tr[k].size--,del(tr[k].r,x);
	else
		tr[k].size--,del(tr[k].l,x);	
} 

int query_rank(int k,int x)//treap的查询
{
	if(!k)
		return 0;
	if(tr[k].v==x)	
		return tr[tr[k].l].size+1;
	else if(x>tr[k].v)
		return tr[tr[k].l].size+tr[k].w+query_rank(tr[k].r+x);
	else
		return query_rank(tr[k].l,x); 
} 

int query_num(int k,int x)
{
	if(!k)
		return 0;
	if(x<=tr[tr[k].l].size)
		return query_num(tr[k].l,x);
	else if(x>tr[tr[k].l].size+tr[k].w)
		return query_num(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
	else
		return tr[k].v;
}

平衡树之Treap

原文：https://www.cnblogs.com/liumengliang/p/13357109.html