伸展树

和AVL树不一样，伸展树并不保证每次操作的时间复杂度为O(logn)，而保证任何
一个m个操作的序列总时间为O(mlogn)。
伸展树的基本思想是：每个结点被访问时，使用AVL树的旋转操作把它移动到
根。由于旋转是自底向上的，所以需要设置父亲指针，而不像AVL树那样以儿子为轴
旋转。
伸展操作(splaying) 伸展树的核心是伸展操作Splay(x,S)。它是在保持伸展树有
序性的前提下，通过一系列旋转将伸展树S中的元素x调整到树的根部。在调整的过程
中，要根据x的位置分以下三种情况分别处理。
情况一: 节点x的父节点y是根节点。
这时，如果x是y的左孩子，我们进行一次Zig（右旋）操作；如果x是y的右孩子，
则我们进行一次Zag（左旋）操作。经过旋转，x成为二叉查找树S的根节点，调整结
束。如图 3.25所示。
图 3.25: 伸展树旋转：zig旋转和zag旋转
110 数据结构原理
两种旋转不仅代表了伸展操作的情况一，而且也是后两种情况的基础，因此把代
码列在这里。由于旋转过程中需要修改父亲，因此需要记录父亲指针。这里仍然让0充
当虚拟结点，因此可以随意修改它的父亲和儿子。注意建立关系时必须同时修改儿子
的父亲指针和父亲的儿子指针，在下面的代码中这样的成对操作被写在同一行中。一
共有三组成对操作。
情况二：节点x的父节点y不是根节点，y的父节点为z，且x与y同时是各自父
节点的左孩子或者同时是各自父节点的右孩子。
这时，我们进行一次Zig-Zig操作或者Zag-Zag操作。如图 3.26所示
图 3.26: 伸展树旋转：zig-zig旋转
情况三：节点x的父节点y不是根节点，y的父节点为z，x与y中一个是其父节
点的左孩子而另一个是其父节点的右孩子。
这时，我们进行一次Zig-Zag操作或者Zag-Zig操作。如图 3.27所示
图 3.27: 伸展树旋转：zig-zag旋转
综合三种情况的伸展操作是：
void splay(int& x, int& s)
{
int p;
while(father[x])
{
p = father[x];
if(!father[p]) // Zig & Zag
{
if(x == left[p]) RightRotate(x);
else LeftRotate(x);
break;
}
if(x == left[p])
{
if(p == left[father[p]])
{ RightRotate(p); RightRotate(x);} //Zig-Zig
else
3.3 平衡二叉树及其变种 111
{ RightRotate(x); LeftRotate(x); } //Zig-Zag
}
else
{
if(p == right[father[p]]
{ LeftRotate(p); LeftRotate(x); } //Zag-Zag
else
{ LeftRotate(x); RightRotate(x); } //Zag-Zig
}
}
s = x;
}
下面是一个例子。如图 3.28(a)所示，执行Splay(1,S)，我们将元素1调整到了伸展
树S的根部。再执行Splay(2,S)，如图 3.28(b)所示，我们从直观上可以看出在经过调整
后，伸展树比原来“平衡”了许多。伸展操作的过程并不复杂，只需要根据情况进行旋
转就可以了，三种旋转都是由基本的左旋和右旋组成的，实现较为简单。
图 3.28: 伸展操作举例
五种基本操作 利用Splay操作，我们可以在伸展树S上进行五种基本运算。
Find和Insert只是简单的进行通常的操作后伸展操作元素x，需要重点说明的是Delete、
Join和Split。
Delete(x,S)：将元素x从伸展树S所表示的有序集中删除。用伸展树查找找到x的
位置，则x到了根的位置。合并x的左右子树即可。
Join(S1,S2)：将S1与S2合并，其中S1的所有元素都小于S2的所有元素。首先，我
们找到伸展树S1中最大的一个元素x，再通过Splay(x,S1)将x调整到伸展树S1的根。然
后再将S2作为x节点的右子树。这样，就得到了新的伸展树S，如图 3.29所示。
图 3.29: 伸展树的join操作
Split(x,S)：将S分离为S1和S2，其中S1中元素都小于x，S2中元素都大于x。先查
找，将元素x调整到根，则x的左子树就是S1，而右子树为S2。如图 3.30所示。
图 3.30: 伸展树的split操作
其他操作 除了上面介绍的五种基本操作，伸展树还支持求最大值、求最小值、求
112 数据结构原理
前趋、求后继等多种操作，这些基本操作也都是建立在伸展操作的基础上的。各种操
作的代码如下：
int find(int x, int s)
{ int p = BST_Search(x, s); splay(p, s); return p; }
void insert(int x, int& s)
{ int p = BST_Insert(x, s); splay(p, s); return p; }
void remove(int x, int& s)
{ int p = find(x,s); join(left[p], right[p]); }
int maximum(int s)
{ int p = s; while(right[p]) p = right[p]; splay(p,s); return p; }
int minimum(int s)
{ int p = s; while(left[p]) p = left[p]; splay(p,s); return p; }
int prev(int x, int& s)
{ int p = find(x, s); p = left[p]; return maximum(p); }
int next(int x, int& s)
{ int p = find(x, s); p = right[p]; return minimum(p); }
int join(int& s1, int& s2)
{
if(!s1) return s2; if(!s2) return s1;
int p = maximum(s1); right[p] = s2;
return p;
}
void split(int x, int&s, int& s1, int& s2)
{
int p = find(x, s);
s1 = left[p]; s2 = right[p];
}
伸展树最有意思的地方在于伸展操作结束以后，伸展结点一定在根处，因此才有
了join和split这样有意思的操作，delete也变得比普通BST更加简单。
结论(不证)：n个结点的伸展树m次操作的总时间开销为O(mlogn)。
伸展树有一种优化形式，不需要父亲指针，只需要O(1)的附加存储，所有操作自
顶向下，维持L和R两个临时树。有兴趣的读者可以参考相关书籍。

以上来自《算法竞赛入门经典训练指南》

Splay简单粗暴  可是本蒟蒻连简单粗暴的东西都不会的话  这就简直太弱了 ToT

本蒟蒻自己写了一个Splay Tree，还没有完全完成。Splay部分可以合并得更加简单，我写复杂了懒得改，相当于纯把几种情况进行了分类处理

  1 #include<cstdio>  2 #include<algorithm>  3 #include<iostream>  4 #define ie(i,s,t) for(int i=s;i<=t;i++)  5 using namespace std;  6   7 const int maxn=65536;  8 int k,m,x,y,root,tot;  9 int fa[maxn],lc[maxn],rc[maxn],dat[maxn],cou[maxn]; 10  11 void zig(int x) 12 { 13     int fx=fa[x],fy=fa[fx]; 14     if(!fx)return; 15     if(rc[x]) 16     { 17         lc[fx]=rc[x];fa[rc[x]]=fx; 18     }else lc[fx]=0; 19     if(fy) 20         if(lc[fy]==fx)lc[fy]=x;else rc[fy]=x; 21     fa[fx]=x;rc[x]=fx;fa[x]=fy; 22 } 23  24 void zag(int x) 25 { 26     int fx=fa[x],fy=fa[fx]; 27     if(!fx)return; 28     if(lc[x]) 29     { 30         rc[fx]=lc[x];fa[lc[x]]=fx; 31     }else rc[fx]=0; 32     if(fy) 33         if(lc[fy]==fx)lc[fy]=x;else rc[fy]=x; 34     fa[fx]=x;lc[x]=fx;fa[x]=fy; 35 } 36  37  38 void splay(int x)//y-fx x-x 39 { 40     while(fa[x]) 41     { 42         int fx=fa[x],fy=fa[fx]; 43         if(!fy) 44         { 45             if(lc[fx]==x)zig(x); else zag(x); 46         }else 47         if(lc[fx]==x&&lc[fy]==fx) 48         { 49             zig(fx);zig(x); 50         }else 51         if(lc[fx]==x&&rc[fy]==fx) 52         { 53             zag(fx);zig(x); 54         }else 55         if(rc[fx]==x&&lc[fy]==fx) 56         { 57             zig(fx);zag(x); 58         }else 59         if(rc[fx]==x&&rc[fy]==fx) 60         { 61             zag(x);zag(y); 62         } 63    } 64    root=x; 65 } 66  67 void insert(int s,int x) 68 { 69     int pre=s; 70     while(s) 71     { 72         pre=s; 73         if(x==dat[s]){++cou[s];splay(s);return;} 74         s=(x<dat[s])?lc[s]:rc[s]; 75     } 76     fa[++tot]=pre;dat[tot]=x;cou[tot]++; 77     //if(!pre)root=tot; 78     if(x<dat[pre])lc[pre]=tot; else rc[pre]=tot; 79     splay(tot); 80 } 81  82 int find(int s,int x,int y) 83 { 84     int pre=s; 85     while(s) 86     { 87         pre=s; 88         if(x==dat[s]){splay(s);if(y==1)return cou[s];else return s;} 89         s=(x<dat[s])?lc[s]:rc[s]; 90     } 91     splay(s); 92     return 0; 93 } 94  95 void check(int s) 96 { 97     if(lc[s])check(lc[s]); 98     printf("%d ",dat[s]); 99     if(rc[s])check(rc[s]);100 }101 102 int main()103 {104     scanf("%d",&m);105     while(m--)106     {107         scanf("%d",&k);108         switch(k) 109         {110             case 1:{scanf("%d",&x);insert(root,x);break;}    111             case 2:{scanf("%d %d",&x,&y);printf("%d\n",find(root,x,y));break;}        112             case 5:{check(root);cout <<endl;break;}113         }114     }115 }

Splay Tree【Uncompleted】

对于操作：1是Insert(x)；2是Find(x,k) k==1 返回该元素出现次数，k==2 返回该元素地址；5是中序遍历整棵树。

建议学习这一部分的骚年  自己写代码  嗯 That‘s all.

注意：

1. Rotate要处理x，fa[x]，fa[fa[x]]的父亲、孩子的关系
2. Rotate中除了先读父亲的标号外，一律先把if语句全部写完（else等等），再分个写其余的赋值（为什么来着 囧 我忘了……）
3. 还有 囧……我又忘了【待续】