[Algorithm]Splay(1) - PerSeAwe - 博客园
今天好好研究了下传说中的Splay，如果真的比Treap强大的话那就将常用的平衡树换成Splay。
看了一上午别人的论文什么的，又在纸上反复的做了推理，下午尝试着将几个不同的Splay写法进行整理，晚上的时候用splay解决了几个问题。总体来讲，splay的确是一个非常强大的数据结构。当做平衡树只是它的用处之一，作为"伸展树"，它还能做些别人做不了的事情。
首先把今天的结论放在最前面：（只是个人的看法，因为对Splay了解不多，有错误请指出，万分感激）
1.splay的旋转操作与Treap是完全相同的(或者说二叉平衡树都是相同的)， 唯一的不同就是Splay有其独特的操作"伸展"。这也就意味着Splay的代码量稍微大一些，速度也稍微慢一些，但是其功能比treap强大而且不需要维护额外的随机值。如果题目仅仅需要进行一下非常基本，如插入，查找，删除之类的基本平衡树操作。那treap应该还是首选，因为treap的维护实在是太简单了。不过一旦涉及到一下较为特殊的操作，那就只能用splay了。
2.另外一个经常与splay进行对比的就是线段树了，与treap和splay相反的是，好像在维护区间这方面，splay的要比线段树快上那么一些。splay的常数比线段树大太多了，能用线段树的时候不要用splay了，虽然splay的维护操作很神奇。但是同样的，因为线段树的结构和操作实在是太简单了，所以代码量要比splay少那么一个级别吧。
综上所述，当遇到基本的操作时，treap和线段树因为其优秀的代码复杂度应该是首选，但是一旦出现比较复杂或是比较奇特的维护时，就应该用splay在强行乱搞来解决。我一下在想起来去年zbwmqlw神牛给我们讲课讨论的时候，碰到一道数据结构题目的时候，最常用的一句话就是："呀，用splay硬搞一下就行了。"splay的功能真是强大的太过分了。不过，话说回来，上面说这么多，只是对我像我一样的普通人，对于像nehzilrz这样的神驼来说，完全不存在这样的问题。（强烈不建议初学者观看）
Read full article from [Algorithm]Splay(1) - PerSeAwe - 博客园
No comments:
Post a Comment