algorithm - 什么是 splay 树中的摊销复杂性？

Question

我试图了解摊销的复杂性并在网上进行了几次搜索，但我还找不到好的资源。

那么谁能解释一下什么是摊销复杂度以及它如何在 splay 树中每个操作变为 O(lg n)？

Answer 1

对伸展树(Splay Tree)执行的任何操作，无论是插入还是删除..等等，成本都由展开操作决定。因此只考虑展开操作的成本，即在要展开的节点上执行的旋转。

The amortized function is given by a=c+3Rfinal(v)-3Rinitial(v)

其中 a 是摊销成本，c 是实际成本，Rfinal 是展开操作后的等级，Rinitial 是旋转前节点的等级。(任何节点的等级由其子树的高度给出，即 log |S| 其中 S 是其下的节点数)

现在考虑要展开的节点是叶子的最坏情况，因此其初始等级由 0 给出。将其展开到顶部后，即作为根节点，其等级变为 log n，其中 n 是树中节点的总数。

 a<= 2+3logn-0
 O(logn).