algorithm - 八字树的摊销分析

Question

Splay Tree 插入/删除可以通过不同的方式完成。一种流行的方法是插入 key 并将其展开到根。但我也读过另一种不同的方法，其想法是将其拆分为两棵树，左边的树具有值 <= 插入键，右边的树具有值>插入键。备用删除方法也是如此，将要删除的键展开到根，然后合并左右树。

但是按照我的理解，

• 如果按升序插入， split 树总是会导致正确的树为空，从而每次按此顺序插入任何键时都会增加不平衡性。
• 删除也是如此，如果我们总是删除树中的最大元素，那么在合并操作中右子树将为空。而且存在巨大的不平衡。

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

Answer 1

是的，摊销时间仍然是 O(log(n))。

直觉是伸展树(Splay Tree)在单个操作的成本和不平衡之间的相互作用。确实，您可以看着一个操作并说“这非常昂贵”或“这导致了很多不平衡”，但您需要同时考虑这两件事。

使用您的第一个示例，插入确实会导致巨大的不平衡，但每个插入都是 O(1)。在 m 个这样的操作结束时，树是不平衡的，但此时，成本仅为 O(m)。在此之后，第一个不同的操作可能会非常昂贵，但它也会减少不平衡。

一系列删除的直觉是相似的。直观上，它也在这两者之间取得了平衡。