Treap（平衡树）
Treap
前置芝士
二叉搜索樹(BST)，見 BST。
平衡二叉樹(AVL)。
先來介紹一下平衡二叉樹。
背景
BST 出現(xiàn)以后，人們很快發(fā)現(xiàn)一個(gè)問題，當(dāng)其維護(hù)一個(gè)有序序列時(shí)，很可能會退化成鏈。如圖：
這樣的話，原來 \(O(\log{n})\) 的復(fù)雜度就退化為 \(O(n)\)，這是我們無法接受的，于是平衡二叉樹橫空出世。
定義
平衡二叉樹:左右子樹的高度相差不超過 1 的 BST（可以為空樹）。平衡，顧名思義，就是要求左右子樹的高度相近。
下面給出一些圖，請判斷是否為平衡二叉樹：
顯然，只有第二棵樹是平衡二叉樹，第一棵樹節(jié)點(diǎn) 5 左右子樹不平衡，第三棵樹不是 BST。
基礎(chǔ)知識
treap，就是“樹堆”，由樹和堆組成，是一種入門級的平衡二叉樹，操作較多，碼量較大，但比較基礎(chǔ)，好理解。
\[Treap=tree+heap \]二叉搜索樹(BST)對于一個(gè)序列來說不唯一，也就是說，在滿足“BST性質(zhì)”的前提下，中序遍歷為相同序列的 BST 不唯一。因此，在 BST 的基礎(chǔ)上加上二叉堆，來保證平衡性。用來維護(hù) BST 的值為“關(guān)鍵碼”，維護(hù)堆的值為權(quán)值，權(quán)值是隨機(jī)產(chǎn)生的，避免退化。維護(hù)堆性質(zhì)的操作為“旋轉(zhuǎn)”。Treap 是一種通過適當(dāng)?shù)男D(zhuǎn)，在維持節(jié)點(diǎn)關(guān)鍵碼滿足 BST 性質(zhì)的同時(shí)，還使每個(gè)節(jié)點(diǎn)上隨機(jī)生成的權(quán)值滿足二叉堆的性質(zhì)的平衡二叉樹。 各個(gè)操作時(shí)間復(fù)雜度為 \(O(\log{n})\)。
基本操作有：
- 插入一個(gè)數(shù) \(x\)。
- 刪除一個(gè)數(shù) \(x\)（若有多個(gè)相同的數(shù)，應(yīng)只刪除一個(gè)）。
- 定義排名為比當(dāng)前數(shù)小的數(shù)的個(gè)數(shù) \(+1\)。查詢 \(x\) 的排名。
- 查詢數(shù)據(jù)結(jié)構(gòu)中排名為 \(x\) 的數(shù)。
- 求 \(x\) 的前驅(qū)（前驅(qū)定義為小于 \(x\)，且最大的數(shù)）。
- 求 \(x\) 的后繼（后繼定義為大于 \(x\)，且最小的數(shù)）。
操作
建樹
與 BST 相同，建立一棵空樹，不過我們需要儲存更多的信息，size 為以該節(jié)點(diǎn)為根的子樹大小，cnt 表示序列中該關(guān)鍵字的個(gè)數(shù)，pushup 和線段樹的一樣，更新父親的信息。
const int N=1e5+5,inf=1<<30;
struct treap
{
int l,r;
int key,dat;//關(guān)鍵字，附加權(quán)值
int size,cnt;//子樹大小，副本數(shù)
}a[N];
int tot,root,n,m;
int New(int k)
{
a[++tot].key=v;
a[tot].dat=rand();
a[tot].cnt=a[tot].size=1;
return tot;
}
void pushup(int u)
{
a[u].size=a[a[u].l].size+a[a[u].r].size+a[u].cnt;
}
void build()
{
New(-inf),New(inf);
root=1,a[root].r=2;
}
旋轉(zhuǎn)
旋轉(zhuǎn)是 Treap 的基本操作，分為左旋和右旋。如圖：
- 右旋：把父親變?yōu)樽髢鹤拥挠覂鹤印?/li>
- 左旋：把父親變?yōu)橛覂鹤拥淖髢鹤印?/li>
如圖，對于黑色節(jié)點(diǎn)來說，左邊右旋后，該節(jié)點(diǎn)的左子樹節(jié)點(diǎn)數(shù)減一，右子樹加一，右邊左旋后，該節(jié)點(diǎn)的左子樹節(jié)點(diǎn)樹加一，右子樹減一。也就是說對于一個(gè)節(jié)點(diǎn)右旋，會增加右子樹的節(jié)點(diǎn)數(shù)，左旋會增加左子樹的節(jié)點(diǎn)數(shù)，利用左旋和右旋我們就可以維護(hù)二叉平衡樹。
以右旋為例，將 \(y\) 變?yōu)?\(x\) 的右兒子，對于 \(x\) 左兒子不變，右兒子變?yōu)?\(y\)，這樣 \(y\) 的左兒子就空出來了，剛好可以把 \(x\) 的右子樹 \(B\) 接上去。具體：\(y\) 的左子樹變?yōu)?\(B\)，\(x\) 的右兒子變?yōu)?\(y\)，\(x\) 代替 \(y\) 原來的位置。
左旋同理：
void zig(int &u)//右旋
{
int q=a[u].l;
a[u].l=a[q].r,a[q].r=u,u=q;
pushup(a[u].r),pushup(u);
}
void zag(int &u)//左旋
{
int q=a[u].r;
a[u].r=a[q].l,a[q].l=u,u=q;
pushup(a[u].l),pushup(u);
}
當(dāng)權(quán)值不滿足大根堆（小也可）性質(zhì)時(shí)，交換父親和兒子，這樣就能使 BST 更平衡。
注意要用 &，這樣的話會一起更新它父親的信息，可以認(rèn)為，\(q\) 完全代替了 \(u\)。
插入
將 \(key\) 為 \(v\) 的數(shù)插入到平衡樹中，若原本已經(jīng)存在，則直接找到位置將 \(cnt\) 加上 1。若不存在，則需將這個(gè)數(shù)插入到葉子節(jié)點(diǎn)，一直向下走直到找到要插入的位置，插入后判斷是否滿足大根堆性質(zhì)，進(jìn)行旋轉(zhuǎn)來維護(hù)。
void insert(int &u,int v)
{
if(u==0) u=New(v);//u指向新的節(jié)點(diǎn)
else if(a[u].key==v) a[u].cnt++;
else if(a[u].key>v)
{
insert(a[u].l,v);
if(a[u].dat<a[a[u].l].dat) zig(u);//不滿足大根堆，交換左兒子和父親
}
else
{
insert(a[u].r,v);
if(a[u].dat<a[a[u].r].dat) zag(u);//不滿足大根堆，交換右兒子和父親
}
pushup(u);
}
刪除
將 \(key\) 為 \(v\) 的數(shù)從平衡樹中刪除，與插入類似，先要找到該節(jié)點(diǎn)。若該節(jié)點(diǎn)的 \(cnt\) 大于 1，直接減去 1 即可。若小于 1，考慮如何刪除，如果該點(diǎn)是葉子節(jié)點(diǎn)那就好辦了，直接用 0 代替，但如果不是，我們也不能直接刪，要通過不斷地旋轉(zhuǎn)把它變成葉子節(jié)點(diǎn)，具體看代碼，自己手推一遍就理解了。
void remove(int &u,int v)
{
if(u==0) return;//沒有這個(gè)數(shù)
if(a[u].key==v)
{
if(a[u].cnt>1) a[u].cnt--;
else if(a[u].l&&a[u].r)//非葉子節(jié)點(diǎn)
{
//保證旋轉(zhuǎn)過后能滿足大根堆的性質(zhì)，哪個(gè)大就把哪個(gè)作為父親
if(a[u].r==0||a[a[u].l].dat>a[a[u].r].dat) zig(u),remove(a[u].r,v);//右旋后父親變?yōu)橛覂鹤? else zag(u),remove(a[u].l,v)
}
else u=0;
}
else a[u].key>v ? remove(a[u].l,v) : remove(a[u].r,v);//一直往下走
pushup(u);
}
查排名
\(v\) 的排名為小于它的個(gè)數(shù) \(+1\)。考慮 BST 中，比當(dāng)前節(jié)點(diǎn)小的點(diǎn)應(yīng)該全部位于左子樹，因此排名就是左子樹的大小 \(+1\)。所以先找到該值，再算個(gè)數(shù)。考慮如何從根節(jié)點(diǎn)往下走：
- \(key==v\)，說明已找到，直接返回左子樹的大小加 1。
- \(key>v\)，則需往左子樹走。
- \(key<v\)，則需往右子樹走，同時(shí)加上左子樹大小和該節(jié)點(diǎn)副本數(shù)。
- \(u==0\)，說明樹中不存在 \(v\) 的節(jié)點(diǎn)，直接加 1。
需要在遞歸出口加上 1。
int get_rank(int u,int v)
{
if(u==0) return 1;
if(a[u].key==v) return a[a[u].l].size+1;
if(a[u].key>v) return get_rank(a[u].l,v);
return get_rank(a[u].r,v)+a[a[u].l].size+a[u].cnt;
}
查值
已知排名為 \(k\)，查詢具體的值。大同小異：
- 若左子樹大小大于等于 \(k\)，說明 \(k\) 在左子樹，往左子樹走。
- 若 \(k\) 大于左子樹大小且小于左子樹大小加副本數(shù)，說明該節(jié)點(diǎn)就是答案。
- 若 \(k\) 大于左子樹大小加副本數(shù)，說明在右子樹，往右子樹繼續(xù)找。
int get_val(int u,int k)
{
if(a[a[u].l].size>=k) return get_val(a[u].l,k);
if(a[a[u].l].size+a[u].cnt>=k) return a[u].key;
return get_val(a[u].r,k-a[a[u].l].size-a[u].cnt);//減去比k小的值的個(gè)數(shù)
}
查前驅(qū)/后繼
前驅(qū)定義為小于 \(x\)，且最大的數(shù)，后繼定義為大于 \(x\)，且最小的數(shù)。
以前驅(qū)為例，一直往下走，不滿足 \(key<x\) 則往左子樹走，否則開始找最大值。
int get_pre(int u,int v)
{
if(u==0) return -inf;
if(a[u].key>=v) return get_pre(a[u].l,v);
return max(a[u].key,get_pre(a[u].r,v));
}
int get_ne(int u,int v)
{
if(u==0) return inf;
if(a[u].key<=v) return get_ne(a[u].r,v);
return min(a[u].key,get_ne(a[u].l,v));
}
P3369 【模板】普通平衡樹
分析
將以上講的所有操作結(jié)合在一起就好了，注意細(xì)節(jié)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lc a[u].l
#define rc a[u].r
#define val a[u].key
const int N=1e5+5,inf=1<<30;
struct treap
{
int l,r;
int key,dat;
int size,cnt;
}a[N];
int tot,root,n,m;
int New(int v)
{
a[++tot].key=v;
a[tot].dat=rand();
a[tot].cnt=a[tot].size=1;
return tot;
}
void pushup(int u)
{
a[u].size=a[lc].size+a[rc].size+a[u].cnt;
}
void build()
{
New(-inf),New(inf);
root=1,a[root].r=2;
}
void zig(int &u)//右旋
{
int q=lc;
lc=a[q].r,a[q].r=u,u=q;
pushup(rc),pushup(u);
}
void zag(int &u)//左旋
{
int q=rc;
rc=a[q].l,a[q].l=u,u=q;
pushup(lc),pushup(u);
}
void insert(int &u,int v)
{
if(u==0) u=New(v);
else if(val==v) a[u].cnt++;
else if(val>v)
{
insert(lc,v);
if(a[lc].dat>a[u].dat) zig(u);//不滿足大根堆，交換左兒子和父親
}
else
{
insert(rc,v);
if(a[rc].dat>a[u].dat) zag(u);//交換右兒子
}
pushup(u);
}
void remove(int &u,int v)
{
if(u==0) return ;
if(val==v)
{
if(a[u].cnt>1) a[u].cnt--;
else if(lc||rc) //有葉子節(jié)點(diǎn)
{
//保證旋轉(zhuǎn)過后能滿足大根堆的性質(zhì)，哪個(gè)大就把哪個(gè)作為父親
if(rc==0||a[lc].dat>a[rc].dat) zig(u),remove(rc,v);//右旋后父親變?yōu)橛覂鹤? else zag(u),remove(lc,v);
pushup(u);
}
else u=0;
}
else val>v ? remove(lc,v) : remove(rc,v);
pushup(u);
}
int get_rank(int u,int v)
{
if(u==0) return 1;
if(val==v) return a[lc].size+1;
if(val>v) return get_rank(lc,v);
return get_rank(rc,v)+a[lc].size+a[u].cnt;
}
int get_val(int u,int k)
{
if(a[lc].size>=k) return get_val(lc,k);
if(a[lc].size+a[u].cnt>=k) return val;
return get_val(rc,k-a[lc].size-a[u].cnt);
}
int get_pre(int u,int v)
{
if(u==0) return -inf;
if(val>=v) return get_pre(lc,v);
return max(val,get_pre(rc,v));
}
int get_ne(int u,int v)
{
if(u==0) return inf;
if(val<=v) return get_ne(rc,v);
return min(val,get_ne(lc,v));
}
int main ()
{
cin>>m;
build();
for(int op,x;m--;)
{
cin>>op>>x;
if(op==1) insert(root,x);
else if(op==2) remove(root,x);
else if(op==3) cout<<get_rank(root,x)-1<<"\n";//減去-inf的點(diǎn)
else if(op==4) cout<<get_val(root,x+1)<<"\n";//存在-inf
else if(op==5) cout<<get_pre(root,x)<<"\n";
else cout<<get_ne(root,x)<<"\n";
}
return 0;
}
結(jié)語
有了 Treap，時(shí)間復(fù)雜度不會退化了，但是——這代碼也太長了。而 FHQ_Treap 和 Splay 就會更好 QAQ。
總結(jié)
以上是生活随笔為你收集整理的Treap（平衡树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 网络-华为、思科交换机配置TFTP自动备
- 下一篇： 初探: 通过pyo3用rust为pyth