前言：题单在此：HL平衡树0701 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
平衡树
什么是平衡树？
首先我们需要知道二叉查找树的内容。
二叉查找树（BST：Binary Search Tree)
首先，他是一棵二叉树
其次，他的左子树的权值<根节点的权值<右子树的权值
最后，也是最重要的，他的中序遍历顺序等于他的順序遍歷
這些特性使得一棵二叉查找樹支持很多操作
比如查詢，插入，刪除等...
我們從Treap開始
引用Steven24的博客原文，Treap=Tree+Heap
所以照此意思，Treap就應該是樹和堆的結合
的確如此。
但是兩種數據結構看起來是矛盾的，怎麼解決？
所以很巧妙
給每個鍵值一個隨機附加的優先級，讓鍵值滿足BST的結構，讓優先級滿足堆的結構
我們想一種特殊情況
就是我們每一個父親節點只有右兒子，那麼一個BST就變成了一條鏈
不僅如此，插入刪除的時候也很麻煩。因為如果插入或者刪除，整個樹原來的結構就會被打亂，這會為遍歷和查找帶來災難性的後果。
所以我們推出了平衡樹。就是通過將樹旋轉來動態維護這個樹形態是平衡的，這樣查找的複雜度就是O(log)級別的，是一種穩定的複雜度。
樹堆是一種平衡樹，它通過為鍵值（也就是我們需要維護成BST的）賦予優先順序，使之也滿足堆結構來進行旋轉，成為一棵平衡樹。
但是我們需要注意一點：樹堆的優先順序是隨機賦予的。也就是說，這個資料結構其實是一個隨機化的資料結構。這不是樹堆的缺點，因為只有隨機化賦予優先順序，才有可能保證樹堆的複雜度是O(log)的級別。
那麼，上述性質也說明了，樹堆並不是一個規則形態的二叉樹，更不是堆需要滿足的完全二叉樹。甚至它也不符合平衡樹的定義：每個節點左右子樹高度相差≤1≤1，所以我們說樹堆是近似實現平衡。
但是通過形態定義二叉樹的方式並不絕對。我們換一種方式來對平衡樹進行定義：
能夠保證時間複雜度的BST,就是平衡樹。
Treap的操作
光看這個箭頭的話，還是很容易理解什麼是旋轉的。但是可能給讀者造成困擾的是：這個B節點的父親怎麼變了？
原因是這樣的：我們在進行旋轉操作的時候，要保證BST的節點遍歷順序是一樣的，而BST的節點遍歷順序是中序遍歷（這個是按BST的定義來的），也就是說只有這樣才能保證遍歷序不變的情況下調換節點位置。
所以，針對這個圖，我們把“P/F”看成一對節點，就能很好地理解這個“左/右旋”的操作了。
插入
首先我們瞭解一下BST的插入方式。其實很簡單，就是一個新節點插進去，從根節點開始不停地與當前節點比大小，一直到這個節點成為葉子節點為止。
因為Treap要同時維護BST和堆，所以我們還需要在裡面加上旋轉操作。
如果是右兒子的話要左旋，左兒子要右旋（旋轉操作請結合上圖理解）。
然後我們又多統計了一個size的資料，這個資料表示子樹大小，在統計當前數x是第幾大的時候會很方便。
應該很簡單。
Treap插入
struct node
{
int val,pri,size,lson,rson;//val键值，pri优先级，size子树大小。
}tree[maxn];
int tot;
void L_rotate(int &pos)
{
node x=tree[tree[pos].rson];//x表示要转到上面的节点
tree[pos].rson=x.lson;
x.lson=pos;
x.size=tree[pos].size;
maintain(pos);
tree[pos]=x;
}
void R_rotate(int &pos)
{
node x=tree[tree[pos].lson];
tree[pos].lson=x.rson;
x.size=tree[pos].size;
maintain(pos);
tree[pos]=x;
}
void maintain(int pos)
{
tree[pos].size=tree[tree[pos].lson].size+tree[tree[pos].rson].size+1;
}
void insert(int &pos,int x)
{
if(!pos)
{
pos=++tot;
tree[pos].val=x;
tree[pos].pri=rand();
}
if(x<tree[pos].val)
{
insert(tree[pos].lson,x);
if(tree[pos].pri<tree[lson].pri)//如果优先级不匹配，就旋转(这里维护的是大根堆)
R_rotate(pos);
}
else
{
insert(tree[pos].rson,x);
if(tree[pos].pri<tree[rson].pri)
L_rotate(pos);
}
maintain(pos);
}Treap刪除
刪除操作的大體思路和插入是一樣的。也是要保證刪除前後滿足Treap的雙重結構。
大致是這樣的思路：首先找到這個點在哪。然後，如果這個點已經是葉子節點，就直接將其刪除，如果不是，就一層層地將它轉到底部，然後進行刪除。這和我們的插入操作有異曲同工之妙，就是進行操作的一定是葉子節點，如果不是葉子的話是不能粗暴刪除的。需要轉。
Treap刪除
void remove(int &pos,int x)
{
if(!pos)
return;
if(x==tree[pos].val)
{
if(tree[pos].lson|tree[pos].rson)//如果非叶子节点
{
if(tree[tree[pos].lson].pri>tree[tree[pos].rson].pri)
R_rotate(pos),remove(tree[pos].lson,x);
else
L_rotate(pos),remove(tree[pos].rson,x);
maintain(pos);
}
else
pos=0;
}
else
{
if(x<tree[pos].val)
remove(tree[pos].lson,x);
else
remove(tree[pos].rson,x);
}
if(pos)
maintain(pos);
}Treap查詢I
也就是對某數進行排名
查詢操作不涉及修改，根據樹堆的雙重性質，其操作是跟BST是一樣的。
Treap查詢I
int rank(int pos,int x)
{
if(!pos)
return 1;
if(x<tree[pos].val)
return rank(tree[pos].lson,x);
else
return rank(tree[pos].rson,x)+tree[tree[pos].lson].size+1;
}
int rank(int pos,int x,int &cnt)
{
if(!pos)
return -1;
if(x==tree[pos].val)
return cnt+=tree[tree[pos].lson].size;
else
{
if(x<tree[pos].val)
rank(tree[pos].lson,x,cnt);
else
cnt+=(tree[tree[pos].lson].size+1),rank(tree[pos].rson,x,cnt);
}
}Treap查詢II
查詢第k大的數
Treap查詢II
int kth(int pos,int k)
{
if(!pos || k<=0 || k>tree[pos].size)
return -1;
if(k==tree[tree[pos].lson].size+1)
return tree[pos].val;
else if(k<=tree[tree[pos].lson].size)
return kth(tree[pos].lson,k);
else
return kth(tree[pos].rson,k-tree[tree[pos].lson].size-1);
}Treap查詢III
查詢前驅或後繼
Treap查詢III
#define INF 1e9
int prev(int pos,int x)
{
if(!pos)
return -INF;
if(x<tree[pos].val)
return prev(tree[pos].lson,x);
else
return max(tree[pos].val,prev(tree[pos].rson,x));
}
int nxt(int pos,int x)
{
if(!pos)
return INF;
if(x>=tree[pos].val)
return nxt(tree[pos].rson,x);
else
return min(tree[pos].val,nxt(tree[pos].lson,x));
}Treap遍歷
中序遍歷，left->root->right
Treap遍歷
void dfs(int pos)
{
if(tree[pos].lson)
dfs(tree[pos].lson);
printf("%d ",tree[pos].val);
if(tree[pos].rson)
dfs(tree[pos].rson);
}