0. 前言
前置知识：二叉查找树。
我们知道，二叉查找树是会被恶意数据卡成\(O(n^2)\)的。(如下图)
这很显然不是我们想要的，我们需要找到一种方法来让树保持平衡。
于是我们就有了各式各样的平衡树，而在OI中应用最为广泛的就是Splay和fhq_treap了，
并且这两个数据结构互相不能替代。
Splay：码量一般，常数较大，能够进行序列操作，LCT的专用树，不能可持久化。
fhq_treap：码量一般，常数较大，能够进行序列操作，维护LCT的时间复杂度多一只log，可以可持久化。
总而言之，一般来说学这两个就够了（
1. 树旋转
Splay使用树旋转来保持平衡。所以说我们要先学会树旋转。
如下图，我们只关心框出的子树。容易证明，这种操作没有破坏BST的性质。
我们称下图中的左旋为"将x旋转到父节点"，右旋为"将f旋转到父节点"。
换言之，旋转谁就是说将哪个节点提升到其父节点的位置。
不妨用\(\text{connect}(u,v)\)表示连接\(u,v\)，且\(v\)是\(u\)的父亲。\(u,v\)原有的父子关系被删除。
记节点\(x\)的父亲为\(f\)，祖父为\(g\)，\(x\)的靠近\(f\)的儿子为\(u\)(这里指图中的B/B‘)，并且现在要旋转节点\(x\)。
可以分为以下三步：
- \(\text{connect}(u,f)\)
- \(\text{connect}(x,g)\)
- \(\text{connect}(f,x)\)
图上看就是这样：
2. 单旋"spaly"
接下来我们介绍单旋的写法，也被称为"spaly"，复杂度是假的。