简介
Splay，也就是大名鼎鼎的伸展树，是平衡树的一种，说他平衡，其实不平衡，但是均摊就是logn的！并且，Splay灵活多变堪称区间之王，原理也十分暴力，写起来也还好，引用严指导的话，就是“垃圾代码构造器”。
核心
其核心就在于，能用均摊logn的时间，把一个结点升高，一般是到根结点，然后再进行插入删除等各种操作，也就是说，把一个结点升高，就是一次Splay操作，Splay的所有操作都基于Splay操作，因为它快233。
实现
下面就来讲讲如何Splay。
1，可以直接用单旋上升结点，不过这样容易退化，又名Spaly。
2，用双旋操作优化，之后速度就神速了。
这就草率讲完了。
旋转
旋转，就是在保持BST的性质的同时，改变树的形状的操作。
下面X爷爷，y父亲，z儿子
单旋操作，把一个结点与它父亲旋转（把该节点高度抬高1）
就是Treap的那个，大概给个图吧，这个看看别人博客better。
双选操作，把一个结点与它“爷爷”旋转（把该结点高度抬高2）
这里就玄学了。
分类讨论：
模板
应用
对于单点，就把点抬起来
对于区间，就把区间抬起来，也就是把区间的左端点抬到根，再把右端点抬到根的右子树上，右子树的左子树就是不包含左右端点的区间所在子树。
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：Splay”