伸展樹（Splay樹）的簡要操作，伸展splay樹
伸展樹（splay樹），是二叉排序樹的一種。【兩個月之前寫過，今天突然想寫個博客。。。】
伸展樹和一般的二叉排序樹不同的是，在每次執行完插入、查詢、刪除等操作後，都會自動平衡這棵樹。（說是自動，也就是多了一段代碼，把這個節點提到根節點的位置上罷了）
伸展樹的調整是基於兩種旋轉操作的【左旋右旋嘛】。
分別是這樣的（對2號節點操作）：
（有點草率啊這個圖）
對於這兩個操作，只需要處理好指針為空的情況即可（我的splay樹包含了father指針，可能比另一種寫法更繁瑣一些）
![]()
1 void lec(nod x)
2 {
3 nod y=x->fa;
4 y->rs=x->ls;
5 if (x->ls!=NULL)
6 x->ls->fa=y;
7 x->ls=y;
8 x->fa=y->fa;
9 if (y->fa!=NULL)
10 {
11 if (y==y->fa->ls)
12 y->fa->ls=x;
13 else
14 y->fa->rs=x;
15 }
16 y->fa=x;
17 }
18
19 void ric(nod x)
20 {
21 nod y=x->fa;
22 y->ls=x->rs;
23 if (x->rs!=NULL)
24 x->rs->fa=y;
25 x->rs=y;
26 x->fa=y->fa;
27 if (y->fa!=NULL)
28 {
29 if (y==y->fa->ls)
30 y->fa->ls=x;
31 else
32 y->fa->rs=x;
33 }
34 y->fa=x;
35 }
左旋右旋
這樣的話，我們就可以怼出一個splay操作，每次把一個操作節點上移到根節點位置。
![]()
1 void splay(nod x)
2 {
3 nod y;
4 while (x->fa!=NULL)
5 {
6 y=x->fa;
7 if (y->fa==NULL)
8 {
9 if (y->ls==x)
10 ric(x);
11 else
12 lec(x);
13 break;
14 }
15 if (x==y->ls)
16 {
17 if (y==y->fa->ls)
18 ric(y),ric(x);
19 else
20 ric(x),lec(x);
21 }
22 else
23 {
24 if (y==y->fa->ls)
25 lec(x),ric(x);
26 else
27 lec(y),lec(x);
28 }
29 }
30 s=x;
31 }
splay操作
然後只要在每次插入、查找等操作後，加上一句splay（當前結點指針）就好了。。
