Splay怎么可能是一条链。。。
by t162 @ 2019-05-19 18:10:56
@[1610403csl](/space/show?uid=61068) 你可能对 splay 的过程有什么误解... $QwQ$
by 龙之吻—水货 @ 2019-05-19 18:12:18
@[1610403csl](/space/show?uid=61068) 你可能对 splay 的意义有什么误解... $QwQ$
by t162 @ 2019-05-19 18:14:39
@[1610403csl](/space/show?uid=61068) Splay很大程度上就是为了解决一条链的情况啊.. 怎么会出现一条链...
by Nicoppa @ 2019-05-19 18:14:45
但是可以直接建成一条链
by cosmicAC @ 2019-05-19 18:20:44
你可能说的是BST（
by _LiM @ 2019-05-19 18:29:59
出现了！BST！
by lukelin @ 2019-05-19 18:45:44
这样依次插入1,2,...,n不就是一条链了？
by 01190220csl @ 2019-05-19 18:47:22
@[龙之吻—水货](/space/show?uid=49866)
by 01190220csl @ 2019-05-19 18:56:31
只做单旋，或者没有对每次访问（包括新增以及查询）的节点都做splay操作，倒是有可能出现退化成链的情况。
正确实现的Splay分摊复杂度一定是$\text{O}(\log N)$/次的，即使中途出现了一条长链，也会马上被双旋操作消掉。
by Orina_zju @ 2019-05-19 19:19:58