众所周知Splay因为复杂度含有均摊单次单log的伸展操作导致常数巨大。
之前听说了某种优化:
貌似是当当前结点右子树的大小超过整棵树还是当前结点子树的一半的时候,直接旋转右子树到根,可以把伸展的均摊复杂度降到常数水平。
请问这种东西是否正确,以及严格证明,感性写了几个柿子感觉好像没错......