文章目錄

• 引入概念
• 全套模板
• • 變量聲明
  • update
  • ==rotate旋轉(zhuǎn)==
  • splay操作
  • insert插入
  • delete刪除
  • 查找x的位置
  • 查找第k大
  • 前驅(qū)/后繼
• 極小值-inf和極大值inf的作用
• 例題：P3369 【模板】普通平衡樹(shù)
• • 題目
  • code

聲明一下，許多代碼的注解都在模板代碼里面寫(xiě)了的，所以正文可能不會(huì)很多
其次是$splay$很多操作$treap$我都已經(jīng)詳解過(guò)了，只需要掌握不一樣的旋轉(zhuǎn)板塊即可

引入概念

在這之前大家要了解二叉搜索樹(shù)或者treap再或者非旋treap，也可以不了解，我會(huì)再次盡全力詳細(xì)的給大家講懵splay

二叉搜索樹(shù)：是一種數(shù)據(jù)結(jié)構(gòu)，每個(gè)點(diǎn)都存有各自的鍵值，按中序遍歷這棵樹(shù)，按鍵值生成的序列是有序的

顯而易見(jiàn)對(duì)于給定的序列$n$，它的二叉搜索樹(shù)不是唯一的
煮個(gè)栗子：$12345$，就能畫(huà)出很多不一樣的二叉搜索樹(shù)

---

伸展樹(shù)（Splay Tree），也叫分裂樹(shù)，是一種二叉排序樹(shù)，它能在$O(logn)$內(nèi)完成插入、查找和刪除操作
它由丹尼爾·斯立特Daniel Sleator 和 羅伯特·恩卓·塔揚(yáng)Robert Endre Tarjan在1985年發(fā)明的

在伸展樹(shù)上的一般操作都基于伸展操作：
假設(shè)想要對(duì)一個(gè)二叉查找樹(shù)執(zhí)行一系列的查找操作，為了使整個(gè)查找時(shí)間更小，被查頻率高的那些條目就應(yīng)當(dāng)經(jīng)常處于靠近樹(shù)根的位置
于是想到設(shè)計(jì)一個(gè)簡(jiǎn)單方法：
在每次查找之后對(duì)樹(shù)進(jìn)行重構(gòu)，把被查找的條目搬移到離樹(shù)根近一些的地方
伸展樹(shù)應(yīng)運(yùn)而生：
伸展樹(shù)是一種自調(diào)整形式的二叉查找樹(shù)，它會(huì)沿著從某個(gè)節(jié)點(diǎn)到樹(shù)根之間的路徑，通過(guò)一系列的旋轉(zhuǎn)把這個(gè)節(jié)點(diǎn)搬移到樹(shù)根去
它的優(yōu)勢(shì)在于不需要記錄用于平衡樹(shù)的冗余信息

假設(shè)想要對(duì)一個(gè)二叉查找樹(shù)執(zhí)行一系列的查找操作
為了使整個(gè)查找時(shí)間更小，被查頻率高的那些條目就應(yīng)當(dāng)經(jīng)常處于靠近樹(shù)根的位置
于是想到設(shè)計(jì)一個(gè)簡(jiǎn)單方法：
在每次查找之后對(duì)樹(shù)進(jìn)行重構(gòu)，把被查找的條目搬移到離樹(shù)根近一些的地方
splay tree應(yīng)運(yùn)而生。splay tree是一種自調(diào)整形式的二叉查找樹(shù)，它會(huì)沿著從某個(gè)節(jié)點(diǎn)到樹(shù)根之間的路徑，通過(guò)一系列的旋轉(zhuǎn)把這個(gè)節(jié)點(diǎn)搬移到樹(shù)根去

———————百度百科老師親身授課，講懵一群中華少年

這張圖太好看了，忍不住盜過(guò)來(lái)

---

重點(diǎn)的就是模板，模板的原理會(huì)在該模板板塊介紹，不要慌~~

全套模板

---

變量聲明

我用的是結(jié)構(gòu)體$tree$，方便學(xué)習(xí)$LCT$（暴露了） 后面的封裝
$tree[i].val$：表示該點(diǎn)的值
$tree[i].cnt$：表示該點(diǎn)在樹(shù)上的出現(xiàn)次數(shù)
$tree[i].siz$：表示該點(diǎn)的子樹(shù)大小，包括自己在內(nèi)
$tree[i].f$：表示該點(diǎn)的爸爸（誒真乖）
$tree[i].son[2]$：表示該點(diǎn)的兩個(gè)兒子：$son[0]$左兒子，$son[1]$右兒子

---

這個(gè)沒(méi)有什么值得講的，不同的題肯定會(huì)有添加或更改，比如最大值就應(yīng)該寫(xiě)成
$tree[x].maxx=max(tree[tree[x].son[0]].maxx,tree[tree[x].son[1]].maxx,tree[x].val)$
這里以求和為例

update

void update ( int x ) {tree[x].siz = tree[tree[x].son[0]].siz + tree[tree[x].son[1]].siz + tree[x].cnt; }

---

rotate旋轉(zhuǎn)

在$treap$期間我們了解了單旋轉(zhuǎn)（只旋一次），但是$splay$則是用雙旋
接著因?yàn)槭嵌鏄?shù)，雙旋就分為了兩種情況，直線型旋轉(zhuǎn)和折線型旋轉(zhuǎn)

---

直線型旋轉(zhuǎn)，即三點(diǎn)成一條直線

這種情況的旋轉(zhuǎn)規(guī)則：先旋轉(zhuǎn)父親，再旋轉(zhuǎn)自己

---

折線型旋轉(zhuǎn)

這種情況的旋轉(zhuǎn)規(guī)則：旋轉(zhuǎn)完自己，再旋轉(zhuǎn)自己（自轉(zhuǎn)兩次）

---

總結(jié)一張圖：

void rotate ( int x ) {//x是要旋轉(zhuǎn)的點(diǎn) int fa = tree[x].f;//x的父親(father縮寫(xiě)) int Gfa = tree[fa].f;//x的祖父/fa的父親(grandfather縮寫(xiě)(*^__^*))int k = ( tree[fa].son[1] == x );//x是fa的哪一個(gè)兒子 0左兒子 1右兒子if( Gfa) tree[Gfa].son[tree[Gfa].son[1] == fa] = x;//兒子非要當(dāng)?shù)?取代了爹原來(lái)在祖父下的位置tree[x].f = Gfa; tree[fa].son[k] = tree[x].son[k ^ 1];if( tree[x].son[k ^ 1] ) tree[tree[x].son[k ^ 1]].f = fa;tree[x].son[k ^ 1] = fa;tree[fa].f = x;update ( fa );//別忘了更新信息update ( x ); }//0^1=1 1^1=0 其實(shí)也可以用取反(!)代替

---

splay操作

我們使用雙旋的做法，因?yàn)槿绻麊涡龑?span id="ze8trgl8bvbq" class="katex--inline">$x$旋到想要的位置，毒瘤會(huì)卡到我們$n^2$
那么如果想旋轉(zhuǎn)到根的話，可以給第二個(gè)參數(shù)傳0

void splay ( int x, int goal ) {//將x旋轉(zhuǎn)到goal的兒子 如果goal是0意味著將x轉(zhuǎn)到根while ( tree[x].f != goal ) {int fa = tree[x].f, Gfa = tree[fa].f;if ( Gfa != goal )//如果fa不是根節(jié)點(diǎn)就是兩類(直線 折線)旋轉(zhuǎn)( ( tree[Gfa].son[0] == fa ) ^ ( tree[fa].son[0] == x ) ) ? rotate ( x ) : rotate ( fa );//有點(diǎn)技巧但也很好理解 前兩坨^=0就是直線的意思rotate ( x );}if ( ! goal )root = x;//如果goal是0 將根節(jié)點(diǎn)更新為x }

---

insert插入

先用個(gè)動(dòng)圖直觀感受一下

跟$treap$是孿生兄弟，從根開(kāi)始，根據(jù)值的大小比較判斷是往左走($x<tree[root].val$)還是往右走($x>tree[root].val$)

void insert ( int x ) {int u = root, fa = 0;//當(dāng)前位置u及u的父節(jié)點(diǎn)fwhile ( u && tree[u].val != x ) {//仍有點(diǎn)且并未移動(dòng)到想要的值 fa = u;u = tree[u].son[x > tree[u].val];//x大于當(dāng)前點(diǎn)的值就在右兒子里面找 否則向左找 }if ( u ) //已經(jīng)建過(guò)x這個(gè)值的位置了 tree[u].cnt ++;else {u = ++ Size;//新節(jié)點(diǎn)的位置 if ( fa ) tree[fa].son[x > tree[fa].val] = u;tree[u].son[0] = tree[u].son[1] = 0;//新點(diǎn)目前肯定沒(méi)有兒子tree[u].val = x;tree[u].f = fa;tree[u].cnt = tree[u].siz = 1;}splay ( u, 0 );//把當(dāng)前位置移到根保證結(jié)構(gòu)平衡 因?yàn)榍懊娓牧俗訕?shù)大小必須splay去update保證siz的正確 }

---

delete刪除

思路是首先分別找到$x$的前驅(qū)$p1$和后繼$p2$，那么在當(dāng)前樹(shù)上就滿足$p1<x<p2$并且中間沒(méi)有其它數(shù)
很妙的就是我們把$p1$旋轉(zhuǎn)到根，此時(shí)所有值比$p1$的都在右子樹(shù)，然后把$p2$旋轉(zhuǎn)到$p1$的兒子處，此時(shí)$p2$的左兒子就是$x$且只有一個(gè)，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$p2$的左子樹(shù)要滿足$>p1$，$<p2$，顯而易見(jiàn)因?yàn)槎x這里面只能插$x$，那么直接對(duì)$p2$的左子樹(shù)進(jìn)行操作即可

void Delete ( int x ) {int pre = PreSuf ( x, 0 ), suf = PreSuf ( x, 1 );splay ( pre, 0 );splay ( suf, pre );//pre有可能為0 但這個(gè)時(shí)候suf就應(yīng)該旋轉(zhuǎn)到根int u = tree[suf].son[0];if ( tree[u].cnt > 1 ) {tree[u].cnt --;splay ( u, 0 );}elsetree[suf].son[0] = 0, splay( suf, 0 ); }

查找x的位置

我相信給個(gè)圖，大家就懂了


與插入是一個(gè)意思，此處就不過(guò)多解釋

void find ( int x ) {//查找x的位置并旋轉(zhuǎn)到根節(jié)點(diǎn) if ( ! root ) //樹(shù)是空的return;int u = root;while ( tree[u].son[x > tree[u].val] && x != tree[u].val )//存在兒子并且當(dāng)前點(diǎn)不是我們要找的 u = tree[u].son[x > tree[u].val];splay ( u, 0 ); }

查找第k大

不要多說(shuō)廢話了，不理解可以移步上面的$treap$講解

int findkth ( int x ) {if ( tree[root].siz < x )//整棵樹(shù)的大小都沒(méi)有k即不存在 return -1;int u = root;while ( 1 ) {if ( x <= tree[tree[u].son[0]].siz )u = tree[u].son[0];else if ( x <= tree[u].cnt + tree[tree[u].son[0]].siz )return u;else {x -= ( tree[tree[u].son[0]].siz + tree[u].cnt );u = tree[u].son[1];}} }

前驅(qū)/后繼

前驅(qū)后繼的思路很妙，我們以前驅(qū)為例，把$x$旋到根，那么左子樹(shù)就是比$x$小的，然后就在左兒子里面一直往右兒子走，$likethis\downarrow$

但是如果樹(shù)上沒(méi)有我們要找的$x$，怎么辦呢，這個(gè)時(shí)候的樹(shù)根究竟是什么，根據(jù)我們$find$的原理寫(xiě)法，可以知道我們一定是找的最接近于$x$的值，不是它的前驅(qū)就是它的后繼，那么這個(gè)時(shí)候根就有可能是答案
我們就在$find$后加入兩個(gè)特判

int PreSuf ( int x, int f ) {//f=0找前驅(qū) f=1找后繼 find ( x );//查找后因?yàn)閟play此時(shí)樹(shù)根就是要查詢節(jié)點(diǎn)if ( tree[root].val > x && f )//如果當(dāng)前節(jié)點(diǎn)的值大于x并且要查找的是后繼因?yàn)閒ind原因可以直接返回了 return root;if ( tree[root].val < x && ! f )//與找后繼同理 return root;int u = tree[root].son[f];if ( ! u )return 0;while ( tree[u].son[f ^ 1] )u = tree[u].son[f ^ 1];return u; }

極小值-inf和極大值inf的作用

在沒(méi)看到這個(gè)之前，如果你就拿著模板跑了，恭喜你流失了一天甚至更多的青春
因?yàn)樯鲜瞿０宥际窃诓迦肓松诒那疤嵯虏拍苓\(yùn)行的接下來(lái)讓本蒟蒻來(lái)給你錯(cuò)誤的講講哨兵的優(yōu)秀

如果有哨兵存在，那么這些點(diǎn)永遠(yuǎn)都不會(huì)是死在最前面或者死的時(shí)候墊在最下面，就幫助我們少考慮很多邊界，我昨天沒(méi)有加哨兵，不停地補(bǔ)刀做手術(shù)，還是千瘡百孔，病很多都是并發(fā)癥，醫(yī)不過(guò)來(lái)，加了個(gè)哨兵，自己就好了

最后簡(jiǎn)單提一下封裝的好處，顯然就是整個(gè)在一坨，方便整體移動(dòng)和調(diào)試。代碼分層也很清晰。可以用結(jié)構(gòu)體

struct node {里面放所有splay的操作 }T; 調(diào)用函數(shù)需要寫(xiě)成 T.insert() 之類的

還可以

namespace splay {里面放所有splay操作 } 調(diào)用函數(shù)需要寫(xiě)成 splay :: insert() 之類的

通常是題目解法涉及到多種算法時(shí)，常按算法將各自模板進(jìn)行封裝。這樣你可以很清楚地知道某個(gè)函數(shù)是屬于哪一層的算法。

例題：P3369 【模板】普通平衡樹(shù)

題目

送你離開(kāi)千里之外

code

#include <cstdio> #define maxn 100005 #define INF 0x7f7f7f7f struct node {int f, cnt, val, siz, son[2]; }tree[maxn]; int n, Size, root;void update ( int x ) {tree[x].siz = tree[tree[x].son[0]].siz + tree[tree[x].son[1]].siz + tree[x].cnt; }void rotate ( int x ) { int fa = tree[x].f; int Gfa = tree[fa].f;int k = ( tree[fa].son[1] == x );tree[Gfa].son[tree[Gfa].son[1] == fa] = x;tree[x].f = Gfa; tree[fa].son[k] = tree[x].son[k ^ 1];tree[tree[x].son[k ^ 1]].f = fa;tree[x].son[k ^ 1] = fa;tree[fa].f = x;update ( fa );update ( x ); }void splay ( int x, int goal ) {while ( tree[x].f != goal ) {int fa = tree[x].f, Gfa = tree[fa].f;if ( Gfa != goal )( ( tree[Gfa].son[0] == fa ) ^ ( tree[fa].son[0] == x ) ) ? rotate ( x ) : rotate ( fa );rotate ( x );}if ( ! goal )root = x; }void insert ( int x ) {int u = root, fa = 0;while ( u && tree[u].val != x ) {fa = u;u = tree[u].son[x > tree[u].val]; }if ( u ) tree[u].cnt ++;else {u = ++ Size; if ( fa ) tree[fa].son[x > tree[fa].val] = u;tree[u].son[0] = tree[u].son[1] = 0;tree[u].val = x;tree[u].f = fa;tree[u].cnt = tree[u].siz = 1;}splay ( u, 0 ); }void find ( int x ) {if ( ! root )return;int u = root;while ( tree[u].son[x > tree[u].val] && x != tree[u].val )u = tree[u].son[x > tree[u].val];splay ( u, 0 ); }int PreSuf ( int x, int f ) { find ( x );if ( tree[root].val > x && f )return root;if ( tree[root].val < x && ! f )return root;int u = tree[root].son[f];if ( ! u )return 0;while ( tree[u].son[f ^ 1] )u = tree[u].son[f ^ 1];return u; }void Delete ( int x ) {int pre = PreSuf ( x, 0 ), suf = PreSuf ( x, 1 );splay ( pre, 0 );splay ( suf, pre );int u = tree[suf].son[0];if ( tree[u].cnt > 1 ) {tree[u].cnt --;splay ( u, 0 );}elsetree[suf].son[0] = 0; }int findkth ( int x ) {if ( tree[root].siz < x )return -1;int u = root;while ( 1 ) {if ( x <= tree[tree[u].son[0]].siz )u = tree[u].son[0];else if ( x <= tree[u].cnt + tree[tree[u].son[0]].siz )return u;else {x -= ( tree[tree[u].son[0]].siz + tree[u].cnt );u = tree[u].son[1];}} }int main() {insert ( INF );insert ( -INF );scanf ( "%d", &n );int opt, x;for ( int i = 1;i <= n;i ++ ) {scanf ( "%d %d", &opt, &x );switch ( opt ) {case 1 : insert ( x ); break;case 2 : Delete ( x ); break;case 3 : {find ( x );printf ( "%d\n", tree[tree[root].son[0]].siz );break;}case 4 : {int u = findkth ( x + 1 );printf ( "%d\n", tree[u].val );break;}case 5 : {int u = PreSuf ( x, 0 );printf ( "%d\n", tree[u].val );break;}case 6 : {int u = PreSuf ( x, 1 );printf ( "%d\n", tree[u].val );break;}}}return 0; } #include <cstdio> #define maxn 100005 #define INF 0x7f7f7f7f struct SplayTree {struct node {int f, cnt, val, siz, son[2];void init ( int Val, int fa ) {val = Val;cnt = siz = 1;f = fa;son[0] = son[1] = 0;}}tree[maxn];int root, Size;void update ( int x ) {tree[x].siz = tree[tree[x].son[0]].siz + tree[tree[x].son[1]].siz + tree[x].cnt;}void rotate ( int x ) { int fa = tree[x].f; int Gfa = tree[fa].f;int k = ( tree[fa].son[1] == x );tree[Gfa].son[tree[Gfa].son[1] == fa] = x;tree[x].f = Gfa; tree[fa].son[k] = tree[x].son[k ^ 1];tree[tree[x].son[k ^ 1]].f = fa;tree[x].son[k ^ 1] = fa;tree[fa].f = x;update ( fa );update ( x );}void splay ( int x, int goal ) {while ( tree[x].f != goal ) {int fa = tree[x].f, Gfa = tree[fa].f;if ( Gfa != goal )( ( tree[Gfa].son[0] == fa ) ^ ( tree[fa].son[0] == x ) ) ? rotate ( x ) : rotate ( fa );rotate ( x );}if ( ! goal )root = x;}void insert ( int x ) {int u = root, fa = 0;while ( u && tree[u].val != x ) {fa = u;u = tree[u].son[x > tree[u].val]; }if ( u ) tree[u].cnt ++;else {u = ++ Size; if ( fa ) tree[fa].son[x > tree[fa].val] = u;tree[u].son[0] = tree[u].son[1] = 0;tree[u].val = x;tree[u].f = fa;tree[u].cnt = tree[u].siz = 1;}splay ( u, 0 );}void find ( int x ) {if ( ! root )return;int u = root;while ( tree[u].son[x > tree[u].val] && x != tree[u].val )u = tree[u].son[x > tree[u].val];splay ( u, 0 ); }int PreSuf ( int x, int f ) { find ( x );if ( tree[root].val > x && f )return root;if ( tree[root].val < x && ! f )return root;int u = tree[root].son[f];if ( ! u )return 0;while ( tree[u].son[f ^ 1] )u = tree[u].son[f ^ 1];return u;}void Delete ( int x ) {int pre = PreSuf ( x, 0 ), suf = PreSuf ( x, 1 );splay ( pre, 0 );splay ( suf, pre );int u = tree[suf].son[0];if ( tree[u].cnt > 1 ) {tree[u].cnt --;splay ( u, 0 );}elsetree[suf].son[0] = 0;}int findkth ( int x ) {if ( tree[root].siz < x )return -1;int u = root;while ( 1 ) {if ( x <= tree[tree[u].son[0]].siz )u = tree[u].son[0];else if ( x <= tree[u].cnt + tree[tree[u].son[0]].siz )return u;else {x -= ( tree[tree[u].son[0]].siz + tree[u].cnt );u = tree[u].son[1];}}}}T; int n;int main() {T.insert ( -INF );T.insert ( INF );scanf ( "%d", &n );int opt, x;for ( int i = 1;i <= n;i ++ ) {scanf ( "%d %d", &opt, &x );switch ( opt ) {case 1 : T.insert ( x ); break;case 2 : T.Delete ( x ); break;case 3 : {T.find ( x );printf ( "%d\n", T.tree[T.tree[T.root].son[0]].siz );break;}case 4 : {int u = T.findkth ( x + 1 );printf ( "%d\n", T.tree[u].val );break;}case 5 : {int u = T.PreSuf ( x, 0 );printf ( "%d\n", T.tree[u].val );break;}case 6 : {int u = T.PreSuf ( x, 1 );printf ( "%d\n", T.tree[u].val );break;}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[学习笔记] 伸展树splay详解+全套模板+例题[Luogu P3369 【模板】普通平衡树]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。