Splay Tree的摊销分析
Amortized Analysis of Splay Tree
Splay Tree 插入/删除可以用不同的方式完成。一种流行的方法是 插入密钥并将其展开到根 。但是我也读过另一种不同的方法，这个想法是 split 将它分成 2 棵树，这样 left 的值 <= 插入键右边的值 > 插入键 。备用删除方法也是如此，要删除的键展开到根，然后合并左右树。
但据我了解，
- 如果按递增顺序插入，拆分树总是会导致正确的树为空，因此每次按此顺序插入任何键时都会增加不平衡。
- 删除也一样，如果我们总是删除树中的最大元素，合并操作时右子树将是空的。而且存在巨大的不平衡。
我的问题是，在这个替代过程中，摊销的 运行 时间是否也保持 O(logN)？如果是这样，怎么办？我尝试在互联网上搜索但找不到任何答案。任何一种直觉都会很有帮助:)
是的，摊销时间仍然是 O(log(n))。
直觉是 splay 树在单个操作的成本和不平衡之间的相互作用。的确，你可以看着一个操作说“这非常昂贵”或“这会导致很多不平衡”，但你需要同时考虑这两件事。
使用您的第一个示例，插入确实会导致巨大的不平衡，但每个插入都是 O(1)。在 m 次这样的操作结束时，树是不平衡的，但此时，成本仅为 O(m)。在此之后，第一个不同的操作可能非常昂贵，但它也会减少不平衡。
删除系列的直觉是相似的。直观上，它也在这两者之间取得了平衡。
Splay Tree 插入/删除可以用不同的方式完成。一种流行的方法是 插入密钥并将其展开到根 。但是我也读过另一种不同的方法，这个想法是 split 将它分成 2 棵树，这样 left 的值 <= 插入键右边的值 > 插入键 。备用删除方法也是如此，要删除的键展开到根，然后合并左右树。
但据我了解，
- 如果按递增顺序插入，拆分树总是会导致正确的树为空，因此每次按此顺序插入任何键时都会增加不平衡。
- 删除也一样，如果我们总是删除树中的最大元素，合并操作时右子树将是空的。而且存在巨大的不平衡。
我的问题是，在这个替代过程中，摊销的 运行 时间是否也保持 O(logN)？如果是这样，怎么办？我尝试在互联网上搜索但找不到任何答案。任何一种直觉都会很有帮助:)
是的，摊销时间仍然是 O(log(n))。
直觉是 splay 树在单个操作的成本和不平衡之间的相互作用。的确，你可以看着一个操作说“这非常昂贵”或“这会导致很多不平衡”，但你需要同时考虑这两件事。
使用您的第一个示例，插入确实会导致巨大的不平衡，但每个插入都是 O(1)。在 m 次这样的操作结束时，树是不平衡的，但此时，成本仅为 O(m)。在此之后，第一个不同的操作可能非常昂贵，但它也会减少不平衡。
删除系列的直觉是相似的。直观上，它也在这两者之间取得了平衡。