Splay 的势能分析

众所周知 Splay 的势能分析非常的美，设计了一个非常优美的函数 。总体来说，它还是遵守势能分析的原则：当出现了一个代价非常大的操作的时候，我们的势能一定要进行一个下降，这样才能够抵消或者说中和，使得最终均摊下每一步都代价都不大。

具体的分析网络上比比皆是，我们不多赘述。我们从设计理念上来讲解一下为什么这样设计势能函数，或者说我们应该怎么想到这个势能函数。

大家对 Splay 的担忧其实就集中在：害怕它可能会调整非常多次，因为它每 access 一个 node，就会把它调整为根。如果一次调整了太多下，就完蛋了。所以我们希望调整很多次的操作，能够让势能降低。

我们都知道把一个 node 调整上去会把整个树差不多变平衡，或者说它会把 node 到根的这条链及其子树变得比较平衡。所以其实呼之欲出，我们想要定义一个势能函数，它在平衡的时候势能比较小，在退化成链的时候势能比较大。这样我们调整的次数多，那么让势能降低的也多，这样均摊就好了！

下面阐述一个关键问题：Splay 插入的复杂度。很多人从来不分析这个，至少我在网络上都直接默认插入的复杂度非常 trivial，但是我确实想了很久。插入一个点是不会让势能函数变小的，反而会变大，所以直接分析是不行的。我们注意到，插入的 operation 个数和调整的 operation 个数其实是一样的，所以只需要把势能函数调整一下系数，一定可以做到 cover 掉这个倍数。

完结撒花！