nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
# splay tree 伸展树，以其操作splay出名。 伸展树的本质就是bst， ## splay操作 伸展树对splay操作的参数是一个节点，他的结果是将这个节点通过双旋变成根。 ## splay insert 伸展树insert的时候，先按照bst的操作insert，然后将insert的点进行splay操作即可 ## splay search 伸展树search的时候，先按照bst的操作search,对找到的节点进行splay即可 ## splay erase 伸展树erase的时候，先search,这样我们要删除的节点就成为了根，然后按照bst的操作删除即可 ## splay操作详解 ### 重新定义旋转rotate rotate(x)即交换x和x的父亲的位置，即如果x是父亲y的左儿子，则rotate(x)等价与zig(y)，反之则等价于zag(y) ### 定义splay 如果祖父-父亲-自己构成一条直链，则选rotate父亲再rotate自己，若不是直链则rotate自己两次。知道自己成为根。 ## splay复杂度分析 ### splay势能函数 对于一个伸展树T，他的一个节点x的子树大小为$s(x)$,定义一个节点x的势能为$X=log_2(s(x))$ #### 对数函数是一个凸函数 已知a,b>0,则$lg(a)+lg(b)\lt 2lg(\frac{a+b}{2}) = 2lg(a+b)-2$ ### 对于一条直链，我们要先rotate父亲，再rotate自己 设自己为x，父亲为y，祖父为z， 则势能变化为 $$ \begin{aligned} &X'+Y'+Z'-X-Y-Z \\&=Y'+Z'-X-Y\lt X'+Z'-2X \\&=(3X'-3X)+(X+Z'-2X') \end{aligned} $$ 这里的x和z‘的子树大小加起来刚好等于x'的子树大小-1。所以势能变化小于$3(X'-X)-2$ ### 对于一条非直链，我们要rotate自己两次，才能上去，rotate父亲不行的 同理，势能变化为 $$ \begin{aligned} &X'+Y'+Z'-X-Y-Z \\&=Y'+Z'-X-Y\lt Y'+Z'-2X \\&=(2X'-2X)+(Y'+Z'-2X') \end{aligned} $$ 这里的y'和z'的子树大小加起来刚好等于x‘的子树大小-1，所以势能变化小于$2(X'-X)-2$ ### 单旋 易证势能变化小于$X'-X$ ### 整理合并 三种操作的均摊复杂度分别为$O(1)+X'-X$,$O(1)+2(X'-X)-2$,$O(1)+3(X'-X)-2$,对于后面的两种情况,我们增大势的单位来支配隐藏在O(1)中的常数，最终分别为$O(1)+X'-X$,$2(X'-X)$,$3(X'-X)$,再次放缩: $O(1)+3(X'-X)$,$3(X'-X)$,$3(X'-X)$,最后对于所有的旋转求和，因为只有一次单旋所以最终我们得到了均摊复杂度为$O(1)+X'-X\lt O(1)+X'$,显然X'是一个很小的数，他恰好等于伸展树中的元素的个数取对数后的结果。至此所有的操作均取决于splay的复杂度，均为$lg$级别。 ## splay代码
splay树代码