標簽：合并 有一個 else 簡單 隨機 這一 root 多個 key
性質：一個節點x左子樹所有點的關鍵字都比x的關鍵字小，右子樹所有點的關鍵字都比x的關鍵字大
“樹堆” “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;
}
先給這個節點分配一個隨機的堆權值
然后把這個節點按照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);
}
}
和普通的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);
}
遞歸到葉子節點，一路維護信息即可
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;
}標簽：合并 有一個 else 簡單 隨機 這一 root 多個 key
原文地址：https://www.cnblogs.com/liumengliang/p/13357109.html
