为什么摊开树的摊开分析只关注摊开操作而不考虑向下搜索

Question

展开树中的每个字典操作都使用一个展开操作将节点带到树的根。这种散放操作的摊销效率通常使用潜在方法进行分析，并在许多在线资源（包括维基百科）页面中进行了描述。然后将该散放操作的摊销时间报告为O（m lg n）。

然而，我没有找到对完整字典操作的实际分析，例如插入、删除。。。这些操作中的每一个操作除了使用splay操作外，还使用向下搜索树来找到要插入或删除的节点的正确位置。只有找到该节点后，才能开始展开操作。

人们倾向于发表这样的声明：

• “八字树操作的复杂性与相关八字树操作的复杂性相同”
• [“在我们的分析中，我们注意到执行搜索、插入或删除的时间与相关显示的时间成正比”，《古德里奇之书》第456页，标题为“C语言中的数据结构和算法”

我有两个问题：

• 如何得出这样的结论，即执行搜索的时间与splay的时间成正比？这种暗示向下遍历到节点的时间也与splay的平局成正比？
• 向下遍历的摊销时间效率是多少？它是一个常数吗，仅仅因为您不通过简单地向下遍历来改变树的结构（因此您的潜力保持不变）？这个常数不是=N吗，因为这是最坏的情况？

一个人怎样才能得出这个结论？

Answer 1

一个人如何才能得出这样的结论，即执行搜索的时间与展开的时间成正比？这意味着向下遍历节点的时间也与八字形的连接成正比？

splay阶段在搜索阶段遍历的每个节点上运行。由于在搜索阶段每个节点所做的工作是恒定的，我们推断，在任何操作序列上，搜索=O（splay），因此O（search splay）=O（splay）。

向下遍历的摊销时间效率是多少？它是一个常数吗，仅仅因为你不通过简单的向下遍历来改变树的结构（所以你的潜力保持不变）？因为这是最坏的情况，所以这个常数不是大于N吗？

是的，如果有可能在事后不展开搜索。出于前面讨论的原因，我们将它们视为不可分割的，因此我们有效地用一个常数乘以一个长时间splay用于覆盖搜索的摊销积分。