前言
Spaly是基于二叉查找樹實作的，
什麼是二叉查找樹呢？就是一棵樹呗:joy: ,但是這棵樹滿足性質—一個節點的左孩子一定比它小，右孩子一定比它大
比如說
這就是一棵最基本二叉查找樹
對于每次插入，它的期望複雜度大約是$logn$級别的，但是存在極端情況，比如9999999 9999998 9999997.....1這種資料，會直接被卡成$n^2$
在這種情況下，平衡樹出現了！
Splay簡介
Splay是平衡樹的一種，中文名為伸展樹，由丹尼爾·斯立特Daniel Sleator和羅伯特·恩卓·塔揚Robert Endre Tarjan在1985年發明的(mmp怎麼又是tarjan)
它的主要思想是：對于查找頻率較高的節點，使其處于離根節點相對較近的節點。
這樣就可以保證了查找的效率
那麼現在問題來了：
- 什麼樣的點是查找頻率高的點？
這個玩意兒确實不好統計，但是你可以認為每次被查找的點查找頻率相對較高，說白了就是你把每次查找到的點搬到根節點去
當然你也可以每次查找之後随機一個點作為根，于是Treaplay這種資料結構就誕生啦
- 怎麼實作把節點搬到根這種操作？
這也是Splay這種資料結構所要實作的功能，接下來我們詳細的介紹一下
Splay基本操作
rotate
首先考慮一下，我們要把一個點挪到根，那我們首先要知道怎麼讓一個點挪到它的父節點
情況1
當X是Y的左孩子
這時候如果我們讓X成為Y的父親，隻會影響到3個點的關系
B與X，X與Y，X與R
根據二叉排序樹的性質
B會成為Y的左兒子
Y會成為X的右兒子
X會成為R的兒子，具體是什麼兒子，這個要看Y是R的啥兒子
經過變換之後，大概是這樣
情況2
當X是Y的右孩子
本質上和上面是一樣的，
變換後為
這兩種代碼單獨實作都比較簡單，我就不寫了(實際上是我懶)
但是這兩種旋轉情況很類似，第二種情況實際就是把第一種情況的X,Y換了換位置
我們考慮一下能不能将這兩種情況合并起來實作呢？
答案是肯定的
首先我們要擷取到每一個節點它是它爸爸的哪個孩子，可以這麼寫
bool ident(int x) {
return tree[tree[x].fa].ch[0] == x ? 0 : 1;
} 如果是左孩子的話會傳回0，右孩子會傳回1
那麼我們不難得到R，Y，X這三個節點的資訊
int Y = tree[x].fa;
int R = tree[Y].fa;
int Yson = ident(x); //x是y的哪個孩子
int Rson = ident(Y); B的情況我們可以根據X的情況推算出來，根據^運算的性質，0^1=1,1^1=0,2^1=3,3^1=2，而且B相對于X的位置一定是與X相對于Y的位置是相反的
（否則在旋轉的過程中不會對B産生影響）
int B = tree[x].ch[Yson ^ 1]; 然後我們考慮連接配接的過程
根據上面的圖，不難得到
B成為Y的哪個兒子與X是Y的哪個兒子是一樣的
Y成為X的哪個兒子與X是Y的哪個兒子相反
X成為R的哪個兒子與Y是R的哪個兒子相同
connect(B, Y, Yson);
connect(Y, x, Yson ^ 1);
connect(x, R, Rson); connect函數這麼寫，挺顯然的
void connect(int x, int fa, int how) { //x節點将成為fa節點的how孩子
tree[x].fa = fa;
tree[fa].ch[how] = x;
} 單旋函數就是這樣了，利用這個函數就可以實作把一個節點搬到它的爸爸那兒了，
Splay
Splay(x,to)是實作把x節點搬到to節點
最簡單的辦法，對于x這個節點，每次上旋直到to
但是！
如果你真的這麼寫，可能會T成SB，出題人可能會構造資料把單旋卡成$n^2$，不要問我為什麼！(其實是我不知道)
一個感性的了解是這樣的
把一個點雙旋到根，可以使得從根到它的路徑上的所有點的深度變為大約原來的一半，其它點的深度最多增加2
或者你可以了解一下為啥單旋是錯的
下面我們介紹一下雙旋的Splay
這裡的情況有很多，但是總的來說就三種情況
1.to是x的爸爸，
這樣的話吧x旋轉上去就好
update in 2018.2.19
這裡可能寫錯了一個地方（其實也沒有寫錯）
因為我們在雙旋的時候會改變三個點的關系，為了方别寫，是以我們開始的時候把to設定為to的爸爸
if (tree[tree[x].fa].fa == to) rotate(x);
2.x和他爸爸和他爸爸的爸爸在一條線上
這時候先把Y旋轉上去，再把X旋轉上去就好
else if (ident(x) == ident(tree[x].fa)) rotate(tree[x].fa), rotate(x); 3.x和他爸爸和他爸爸的爸爸不在一條線上
這時候把X旋轉兩次就好
總的代碼：
void splay(int x, int to) {
to = tree[to].fa;
while (tree[x].fa != to) {
if (tree[tree[x].fa].fa == to) rotate(x);
else if (ident(x) == ident(tree[x].fa)) rotate(tree[x].fa), rotate(x);
else rotate(x), rotate(x);
}
} 後記
至此，Spaly的最核心最基本的操作已經講解完畢
至于這玩意兒怎麼用，以及能實作什麼功能，且聽下回分解
作者：自為風月馬前卒
個人部落格http://attack204.com//
出處：http://zwfymqz.cnblogs.com/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。