有人专门研究过splay的旋转顺序对时间效率的影响吗?

回复帖子

@杜岱玮 2018-05-17 02:24 回复

rt,这题我用标准splay T了一个点。但改成统一先提父再提子或一直单级提升就过了。这其中有什么区别?

@杜岱玮 2018-05-17 17:10 回复

@Ghastlcon 谷歌翻译认为"spaly"是捷克语,但它没能给出具体翻译,显然是做的太差了。没办法,只能向dalao虚心求教。

@Ghastlcon 2018-05-17 18:10 回复

@杜岱玮 Spaly 是梗

意思是双旋的是 Splay,单旋的叫做 Spaly

Splay 的复杂度为均摊 $\log N$,而 Spaly 的复杂度没有保证

对于特殊构造的数据,Spaly 会退化从而变得极慢,而 Splay 仍然能正常运作

但是对于随机数据,Spaly 的常数比 Splay 小

@丶Cyanide 2018-07-15 11:08 回复

假如是一条链,只提儿子,就还是一条链;而提父亲就不会这样。