-
- 前言
- splay出現的背景
- 它的操作
- push_up
- rotate
- splay
- find
- insert
- next
- delete
- findkth
- main
前言
暑假快過完了,大家感覺是不是很棒!gay房也體驗過最新的斷電模拟器了.
好吧,在開講之前我還是得說一個.刀劍神域的外傳實在太好看了!
除了精彩的戰鬥場面,神一般的人設和強大的劇情,比起前作來看又多了一樣我最喜歡的東西.
神曲!我從一名聽衆到神崎艾莎的粉絲隻經過了一首歌.
Independence
.燃到甚至有點傷感.看過作品的人應該能懂歌曲中隐含的感情.
我是一邊聽這首歌一邊寫的這個部落格,大家也可以一邊聽歌一邊歡樂地享受這一講的内容.
好了講正事.終于要開始研究神奇的資料結構了.
至于講哪個,題目已經說了,我也就不扯淡了.
其實splay還是非常好懂的.
至于線段樹什麼的我自己也是先賀了一遍代碼然後寫一遍部落格,隻要3個月不學自會.
現在離AFO也差不多3個月,大概是能夠會的.
splay出現的背景
大家都知道二叉查找樹有機率會退化成鍊,這樣時間複雜度就會大大增高.
這個時候有個叫Robert Tarjan 的男人和另一個叫Daniel Sleator的人發明了這樣的一種資料結構.
它在每次詢問的時候可以将樹旋轉(也就是splay這個操作)來維護樹的平衡性.
它的操作
我們就以模闆[普通平衡樹]為例來學習這種資料結構.
那麼這種資料結構應該要支援插入删除,求第 k k 大,求排名,求前驅和後繼.
首先我們定義
struct splaytree.
const int yuzu=;
typedef int fuko[yuzu|];
/*事先準備maxsize和大小為maxsize的數組.*/
struct splaytree{
fuko ch[],sz,cnt,fa,val;
/*ch是孩子,标号0,1分别表示左孩子和右孩子;
sz是這個節點的子樹大小(包括自己);
cnt是這個節點儲存的相同的值的個數(萬一出現同樣的數字隻要cnt[u]++就可以了);
fa是節點的父親;
val是節點儲存的值.
按照本題的要求來講開這一些數組就夠了.*/
然而我還要define一些東西.
#define ls(x) ch[0][x]
#define rs(x) ch[1][x]
#define ws(x,y) (rs(x)==y)
/*這個是which_son的簡稱,就是看y是x的左孩子還是右孩子.
如果x的右孩子等于y,傳回1.接下來會很騷,還請注意.*/
}my_;//開一棵名字叫做my_的splay樹.當然要取名為其他東西也是可以的.
注:接下來為了鞏固splay的知識,我都直接在代碼框裡手打代碼,如果出現錯誤還望大家指出.
如果你也初學splay,賀代碼請謹慎,出現錯誤,我不背這個鍋.
push_up
void push_up(int u){
sz[u]=sz[ls(u)]+sz[rs(u)]+cnt[u];
/*這個操作解釋不用很多,就是左孩子的子樹大小+右孩子的子樹大小+節點u包含相同字的個數.*/
}
rotate
這個直接把代碼放上來隻有神仙能看懂.我該畫圖解釋.
注意:二叉查找樹滿足左孩子權值小于節點權值,而右孩子權值嚴格大于節點的權值,以下圖檔中顯現的是節點編号而不是節點權值.
看上圖,我們現在要把節點44旋轉到 2 2 的位置,為了使它仍然滿足二叉查找樹的性質,我們來操作一下.
旋轉完的樹應該是這樣的.
給每個節點代個權值進去會發現它仍然滿足二叉樹的性質.
我們不妨來找旋轉的規律.
首先假設要旋轉的節點是x,它的父親是y,祖父是z.
我們先找出x與y的關系(左右兒子).
然後必然滿足的條件:
1.x的x相對于y的子樹不變.
2.x的相對于x相對于y的子樹變成了y的x相對于y方向的子樹.(仔細思考)
3.x的父親變成z,y變成相對于x原來相對于y的兒子.
接下來寫出旋轉的代碼,可結合上圖分析使用.
void zhuan(int x){//rotate
int y=fa[x],z=fa[y],k=ws(y,x);//取父親和祖父,求x是y的哪一個兒子.
ch[ws(z,y)][z]=x,fa[x]=z;
/*z的y原來相對于z的兒子變成x,x的父親變成z.*/
ch[k][y]=ch[k^][x],fa[ch[k^][x]]=y;
/*x的與原來x相對于y的方向相反的兒子變成y的x相對于y方向的兒子,同理指派父親.*/
ch[k^][x]=y,fa[y]=x;
/*y變成x的與原來x相對于y相反方向的兒子,y的父親變成x.*/
push_up(y),push_up(x);
/*push_up一下.*/
}
給你們10分鐘時間聽歌思考.
……
splay
該樹最核心的操作之一────splay操作出現了.
如果你能夠了解上面的旋轉操作我們就直接上代碼了.
void splay(int x,int g){//将x旋轉成為g的兒子,如果g是0則将x旋轉到根.
for (;fa[x]^g;zhuan(x)){//最後一定會旋轉一次x
int y=fa[x],z=fa[y];
if (z^g) zhuan(ws(z,y)^ws(y,x)?x:y);//如果z不是根就額外轉一次.
/*通過判斷y是z的哪個兒子和x是y的哪個兒子的關系決定是旋轉y還是x.
其實分類讨論zig,zag也是這樣的算法,非常麻煩,用這個就很簡單了.*/
}
if (!g) rt=x;//如果g等于0将x設為根.
}
/*這些操作的意圖都是使樹變得平衡.*/
find
把維護
splay
平衡的代碼寫完了,終于到詢問的時候了.
這個操作能夠找到存放大小為xx的數字的那個節點,并把這個節點splay到根.
void find(int x){
int u=rt;
if (!u) return;//rt為0,該樹中沒有點,直接跳出.
for (;ch[x>val[u]][u]&&val[u]^x;)
u=ch[x>val[u]][u];
/*根據二叉查找樹的性質,根據x關于左右兒子存放的值的關系在左右兒子中查找.注意特判x恰好和u存放的值相等的情況.*/
splay(u,);//将u節點splay到根,為求x是第幾大的數字做鋪墊.
}
insert
插入一個節點.
void insert(int x){
int u=rt,nf=;//nf是現在u的父親.
for (;u&&val[u]^x;) nf=u,u=ch[x>val[u]][u];//按順序找x應該在的位置.
if (u) ++cnt[u];//如果已經存在x,将cnt++.
else{//不存在,新開一個節點.
u=++tot;
if (nf) ch[x>val[nf]][nf]=u;
ls(u)=rs(u)=;
fa[u]=nf,val[u]=x,cnt[u]=,sz[u]=;
}
splay(u,);//不要忘記splay到根,保持樹的平衡性.
}
next
前驅和後繼.
int next(int x,int f){//f前驅為0,後繼為1
find(x);
int u=rt;
if (val[u]>x&&f||val[u]<x&&!f) return u;
/*find過後val[u]如果不等于x,它一定是最接近x的那個數,如果此時val[u]比x大或者小滿足要求的前或者後,就可以直接判斷前驅後繼.*/
u=ch[f][u];//先往u向f的那個方向跳一個兒子.
for (;ch[f^][u];) u=ch[f^][u];
/*接下來一直往反方向跳,就可以得到比x大的最小的數或者比x小的最大的數.*/
return u;
}
delete
借助next可以完成删除操作.
void del(int x){
int lat=next(x,),net=next(x,);
/*定義last為x的前驅,next為x的後繼.*/
splay(lat,),splay(net,lat);
/*把last轉到根,next轉到last的右兒子.顯然一定是轉到右兒子.*/
int nde=ls(net);//那麼值為x的節點此時應該是next的左兒子.
if (cnt[nde]>){//cnt[nde]>1的話可以隻是删掉一個.
cnt[nde]--;
splay(nde,);//轉到根節點.
}
else ls(net)=;
}
findkth
最後是找第k大值.
int kth(int x){
int u=rt;
if (sz[u]<x) return ;
/*如果sz[u]<x說明整棵樹裡沒有k個值,也當然沒有第k大.*/
for (;;){
int y=ls(u);
if (x>sz[y]+cnt[u]){
x-=sz[y]+cnt[u];
u=rs(u);
}
else if (sz[y]>=x) u=y;
else return val[u];
}//這一部分分類讨論估計也不用講了.
}
main
main包就很簡單了.
int main(){
my_.insert(--);
my_.insert(+);
n=read();
for (;n--;){
int op=read();
switch(op){
case : my_.insert(read()); break;
case : my_.del(read()); break;
case : my_.find(read()),write(my_.sz[my_.ls(rt)]),pl; break;
case : write(my_.kth(read()+)),pl; break;
case : write(my_.val[my_.next(read(),)]),pl; break;
case : write(my_.val[my_.next(read(),)]),pl; break;
}
}
}
預告:接下來會寫LCT.
謝謝大家.