平衡树——splay

类别：二叉排序树

空间效率：O(n)
时间效率：O(log n)内完成插入、查找、删除操作

创造者：Daniel Sleator和Robert Tarjan

优点：每次查询会调整树的结构，使被查询频率高的条目更靠近树根。

有篇Splay入门必看文章 —— CSDN链接

树的旋转是splay的基础，对于二叉查找树来说，树的旋转不破坏查找树的结构。

Splaying

Splaying是Splay Tree中的基本操作，为了让被查询的条目更接近树根，Splay Tree使用了树的旋转操作，同时保证二叉排序树的性质不变。

Splaying的操作受以下三种因素影响：

节点x是父节点p的左孩子还是右孩子
节点p是不是根节点，如果不是
节点p是父节点g的左孩子还是右孩子

同时有三种基本操作：

Zig Step

当p为根节点时，进行zip step操作。

当x是p的左孩子时，对x右旋；

当x是p的右孩子时，对x左旋。

Zig-Zig Step

当p不是根节点，且x和p同为左孩子或右孩子时进行Zig-Zig操作。

当x和p同为左孩子时，依次将p和x右旋；

当x和p同为右孩子时，依次将p和x左旋。

Zig-Zag Step

当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。

当p为左孩子，x为右孩子时，将x左旋后再右旋。

当p为右孩子，x为左孩子时，将x右旋后再左旋。

应用

Splay Tree可以方便的解决一些区间问题，根据不同形状二叉树先序遍历结果不变的特性，可以将区间按顺序建二叉查找树。

每次自下而上的一套splay都可以将x移动到根节点的位置，利用这个特性，可以方便的利用Lazy的思想进行区间操作。

对于每个节点记录size，代表子树中节点的数目，这样就可以很方便地查找区间中的第k小或第k大元素。

对于一段要处理的区间[x, y]，首先splay x-1到root，再splay y+1到root的右孩子，这时root的右孩子的左孩子对应子树就是整个区间。

这样，大部分区间问题都可以很方便的解决，操作同样也适用于一个或多个条目的添加或删除，和区间的移动。

自学笔记

splay算法的核心就在于旋转

我们每次操作都会涉及到一个点，splay算法则会在每次处理完这个点的信息之后就将这个点旋转到二叉查找树的顶点

对于每一类平衡树来说，二叉查找树就是平衡树的本质，之所以有形形色色的平衡树主要是因为其旋转构图的方式不太一样

其实二叉搜索树已经可以完成平衡树的部分性质，但每种旋转方法其实是在增加功能的同时，有效的减小时间复杂度

说来令人哭笑不得的是，平衡树的优化其实是让二叉树变的随机，而让出题人无法卡住你，但相比而言，还是treap是随机得任性

splay以其独特的旋转方法被称作文艺平衡树，甚至有很多OIer愿意称之为平衡树之王（我对此不发表看法）

下面来一道洛谷的题，很适合用splay过

https://www.luogu.org/problemnew/show/P2234

  1 #pragma GCC optimize(2)
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 const int maxn=99999999;
  6 struct sd{
  7     int son[3],sz,fa,key,re;
  8 //son[]儿子节点，sz子树大小，fa父节点，key节点值，re节点值相同的个数
  9 }node[32800];
 10 bool gg[1000005][2];
 11 int root,size,ans;
 12 int get(int k)//判断是左儿子还是右儿子，从而判断向那个方向转
 13 {
 14     return k==node[node[k].fa].son[1];
 15 }
 16 void update(int k)//更新子树大小
 17 {
 18     node[k].sz=node[node[k].son[0]].sz+node[node[k].son[1]].sz+1;
 19 }
 20 void rotate(int k)//开始旋转
 21 {
 22     int old=node[k].fa,oldf=node[old].fa,which=get(k);
 23     //old--父节点  oldf--祖父节点
 24     node[old].son[which]=node[k].son[1-which];
 25     node[node[k].son[1-which]].fa=old;
 26     node[old].fa=k;
 27     //处理父节点 
 28     node[k].son[1-which]=old;
 29     node[k].fa=oldf;
 30     //处理自己本身结点 
 31     if(oldf)
 32     {
 33         node[oldf].son[node[oldf].son[1]==old]=k;
 34     } 
 35     update(old);
 36     update(k);
 37 }
 38 void splay(int k)
 39 {
 40     while(node[k].fa!=0)
 41     {
 42         rotate(k);
 43         //k=node[k].fa;
 44     }
 45     root=k;
 46 }
 47 void inin(int &k,int x,int from,int kind)//插入节点
 48 {
 49     if(k==0)
 50     {
 51         size++;
 52         k=size;node[k].sz=1;
 53         node[k].re=1;
 54         node[k].key=x;
 55         node[k].fa=from;
 56         node[from].son[kind]=k;
 57         return;
 58     }
 59     node[k].sz++;
 60     if(node[k].key==x)
 61     node[k].re++;
 62     else
 63     {
 64         if(x>node[k].key)
 65         {
 66             from=k;
 67             inin(node[k].son[1],x,from,1);
 68         }
 69         else
 70         {
 71             from=k;
 72             inin(node[k].son[0],x,from,0);
 73         }
 74     }
 75 }
 76 void pre(int k,int x)//查询前驱
 77 {
 78     
 79     if(k==0) return;
 80     if(node[k].key==x&&node[k].re>1)
 81     {
 82         ans=k;
 83         return;
 84     }
 85     if(x>node[k].key)
 86     {
 87         ans=k;
 88         pre(node[k].son[1],x);
 89     } 
 90     else
 91     {
 92         pre(node[k].son[0],x);
 93     }
 94 }
 95 void next(int k,int x)//查询后继
 96 {
 97     if(k==0)return;
 98     if(node[k].key==x&&node[k].re>1)
 99     {
100         ans=k;
101         return;
102     }
103     if(x<node[k].key)
104     {
105         ans=k;
106         next(node[k].son[0],x);
107     }
108     else
109     {
110         next(node[k].son[1],x);
111     }
112 }
113 int main()
114 {
115     memset(gg,false,sizeof(gg));
116     int n;
117     scanf("%d",&n);
118     int gg1;
119     scanf("%d",&gg1);
120     inin(root,gg1,0,2);
121     int tot=gg1;
122     node[0].key=maxn;
123     for(int i=2;i<=n;i++)
124     {
125         int x;
126         scanf("%d",&x);
127         if(x>0&&gg[x][1]==true)
128         continue;
129         if(x<=0&&gg[x][0]==true)
130         continue;
131         if(x>0)
132         gg[x][1]=true;
133         else
134         gg[x][0]=true;
135         inin(root,x,0,2);
136         splay(size);
137         ans=0;
138         pre(root,x);
139         int res1=x-node[ans].key;
140         if(ans==0)res1=maxn;
141         res1=res1>0?res1:res1*-1;
142         ans=0;
143         next(root,x);
144         int res2=x-node[ans].key;
145         if(ans==0)
146         res2=maxn;
147         res2=res2>0?res2:res2*-1;
148         int res=res1<res2?res1:res2;
149         tot+=res;
150     }
151     printf("%d",tot);
152     return 0;
153 }