algorithm - 伸展树(Splay Tree)的摊销分析

Question

展开树插入/删除可以用不同的方式完成。一种流行的方法是插入 key 并将其展开到根。但是我读过还有一种不同的方法，这个想法是 拆分 它分成两棵树，左边的树有值<=插入键，右边的树有值>插入键。备用删除方法也是如此，将要删除的键张开到根，然后合并左右树。
但按照我的理解，

如果插入是按递增顺序进行的，那么拆分树总是会导致正确的树为空，因此每次按此顺序插入任何键时都会增加不平衡。

删除也是如此，如果我们总是删除树中的最大元素，那么在合并操作中右子树将为空。并且存在巨大的不平衡。

我的问题是，在这个替代过程中，摊销的运行时间是否也停留在 O(logN) ?如果有，怎么做？我尝试在互联网上搜索，但找不到任何答案。任何一种直觉都会非常有帮助:)

Answer 1

是的，摊销时间仍然是 O(log(n))。
直觉是展开树在单个操作的成本和不平衡之间的相互作用。确实，您可以查看一项操作并说“这非常昂贵”或“这会导致很多不平衡”，但是您需要同时考虑这两件事。
使用您的第一个示例，插入确实会导致巨大的不平衡，但它们中的每一个都是 O(1)。在 m 个这样的操作结束时，树是不平衡的，但此时，成本仅为 O(m)。在此之后，第一个不同的操作可能非常昂贵，但它也会减少不平衡。
一系列删除的直觉是相似的。直观地说，它也在这两者之间取得平衡。