伸展树是一种自平衡二叉查找树，它将每次操作的节点都旋转到根节点，伸展树操作的均摊时间复杂度为logn
基本操作
伸展操作
伸展树的最基本的操作当然就是伸展了,这也是它自平衡的基础
splay(x,S)表示在保持伸展树有序性的前提下，通过一系列旋转将伸展树S中的元素x调整至树的根部。
旋转操作就不说了
伸展操作大致分为3种情况(左右对称的算一种)
- x的父亲节点就是根节点：
这时我们只需要单次旋转(x如果是左子节点就右旋,是右子节点就左旋)将x旋转到根即可 - x的父亲节点和x同为左节点(右节点)，如下图中x为4的情况：
这时我们先将父节点旋转到爷爷节点
然后再将x旋转到父节点
这样x就向上移了两层,然后再进行判断并继续上移直到x为根节点
- x为右子节点但x父亲为左子节点或x为左子节点但x父亲为右子节点，如下图x为5的情况：
这时，可以先将x旋转到父节点
然后将x旋转到之前的爷爷节点
这样x也向上移了两层,然后再进行判断并继续上移直到x为根节点
下面是旋转操作和伸展操作的代码(代码中将伸展操作中2，3情况的旋转分开了，也可以将旋转合并成一次操作)
插入操作
插入操作和二叉查找树的相同，只是插入过后执行伸展操作将节点旋转到根节点