Coldwings『依附蔷薇生长』

忽然发现有一段时间没有做OI的事情了 觉得心里有些欠缺

人生都不完整了 口阿

这次先写了一个关于Splay Tree的东西，很简陋，只能说是简介。

而且看起来有点广告的味道……

没关系，下次写个Segment Tree的，就会技术起来了 哈哈

一、Splay Tree简介

相信大家或多或少的都对Splay Tree有一些了解，这里就不再详细说明Splay Tree的实现方法（毕竟此类说明很容易找到），但仍旧作一个简单的介绍，以方便对Splay Tree不了解的朋友。

Splay Tree是平衡化二叉搜索树的一种实现方法。它提供了一系列快速的访问方式，以二叉搜索树的形式组织数据，并可以实现一些重要的计算。

（考虑到Segment Tree与下面将要讨论的BST有着很大的不同，这里的论述不将其包括在内）

众所周知的，BST（Binary Search Tree 二叉搜索树）的一般用途在于保持可以即时更新的有序数列，并提供一些区间相关的计算（例如区间最大值或者连续最大和等）。BST的时间复杂度取决于其高度，而高度则关乎其“平衡程度”，即越接近完全二叉树就越平衡。BST是通过左旋和右旋两种方式在不影响其性质的情况下调整树的形状的，而调整树的形状使其高度降低的过程被称作是“平衡化”。

与Red-Black Tree、AVL等不同，Splay Tree采取一种在统计上使得访问高度达到lgn的旋转策略，而不是加入额外的标记使其依据标记调整平衡程度的方法，来实现平衡化的。其具体策略与效率证明这里不给出。Splay Tree高效、功能极为强大、实现比较简单，是一种常见的BST实现方法。

二、Splay Tree的优势所在

由于Splay Tree仅仅是不断调整，并没有引入额外的标记，因而树结构与标准BST没有任何不同，从空间角度来看，它比Treap、Red-Black Tree、AVL要高效得多。因为结构不变，因此只要是通过左旋和右旋进行的操作对Splay Tree性质都没有丝毫影响，因而它也提供了BST中最丰富的功能，包括快速的拆分和合并（这里指的是将原树拆分成两棵子树，其中一棵子树所有节点都比另一子树小，以及它的逆过程），并且实现极为便捷。这一点是其它结构较难实现的。其时间效率也相当稳定，和Treap基本相当。

Splay Tree的编程复杂度远小于R-B Tree和AVL，略大于Treap，但是其思维强度很低，加上程序段的高度模块化，Splay Tree的相关操作甚至可以说是“万能函数段”，对于不同的BST结构，Splay Tree的相关函数需要的改动微乎其微（仅仅是比较关键字大小、节点数值的处理略有改动），因此Splay Tree的程序段写过几次之后完全可以“背下来”。我的一位学姐都有过5min一个Splay Tree的纪录。Splay Tree的节点访问几乎完全集中在对根节点的询问上（即使是查找一个节点，按照Splay Tree的方法，也是先找到，然后通过Splay过程将其旋转到根，再进行访问）。这样程序访问和修改接口统一，出错率小，调试也较为方便。敝人甚至能够将Splay Tree通过Lava在文曲星上实现，可见其实现难度很低。

三、Splay Tree的不足

正如上面所言，Splay Tree的不足也相对明显。其程序长度比Treap明显要长，而在竞赛中，特别在神经极为紧张的时候，较长的程序显然会给人额外的心理负担。Splay Tree的时间效率不如AVL之流，和Treap旗鼓相当，但是在某些情况下，Treap可以一开始便通过构建CT的方法快速构造（实事上，这种情况下大都能够直接打乱顺序后加入不进行平衡化的BST，效率甚至比两者都高）。另外，由于Splay Tree要求每次查询都对查询到的节点进行Splay操作，对于修改极小但查询量巨大的情况，Splay Tree速度比Treap等慢，所幸的是这种差距并不是太明显。

四、Splay Tree的应用

这里说明一下，由于敝人有较长时间没有看OI题库，记得具体题号的题目不多；而敝人的SGU题解因为硬盘问题而全部丢失，所以只从VIJOS上翻看了两道题目摆一摆。

VIJOS P1075 强强的战壕

其实本题最好的方法应该是二维树状数组，其次的方法是离散化+Segment Tree。（刚刚鱼牛教育我说其实更好的方法是一维树状数组或者虚二叉树，有不了解的可以请教鱼牛，我是菜……）但是通过Splay Tree同样是可以解决问题的（尽管很是大材小用）。优秀的Splay Tree的效率可以达到离散化+Segment Tree的水平。有趣的是这虽然是个二维的状态，却是可以划归为一维解决的。其实很多的题目中对Splay Tree甚至BST的应用都要通过一定的转化，灵活变换可以提高程序效率，降低编程复杂度。

VIJOS 1083 小白逛公园

此题一度只有敝人AC。PKU上也有一道相同的题目，名字似乎是Feeding the dog。此题我用Segment Tree和Splay Tree分别做过，在进行了反复的优化之后竟然可以使Splay Tree大致达到Segment Tree差不多的速度。题目并不复杂，但是却用到了树的递归性质自底向上求最优解。类似的这样区间内求最大值/最小值/最大和的问题，BST可以很好解决；如果还有节点删除等操作出现的话，Splay Tree将是最方便的选择之一。

五、总结

总体来说，Splay Tree是BST平衡化的一种极为方便快捷的实现方法，很值得一学。当我们需要一个短小的程序来辅助解决搜索剪枝之类的问题时，Treap将是很好的选择；当我们有足够的空间却需要高超的时间效率时，Segment Tree将是我们的强力工具；当我们需要解决众多的数据结构问题、各种复杂的访问与操作时，Splay Tree将是我们的不二法宝。