时间戳

首页 > 解决方案 > 证明对 TREE-SUCCESSOR 的 k 次连续调用需要 O(k + h) 时间

algorithm - 证明对 TREE-SUCCESSOR 的 k 次连续调用需要 O(k + h) 时间

问题描述

这个问题已经存在了一段时间，但我仍然有一个问题。我将讨论以下解决方案。

问题：证明无论我们从高度h二叉搜索树中的哪个节点开始，k对 TREE-SUCCESSOR 的连续调用都需要O(k + h)时间。

给定下面的树后继算法，给定一个 x，它将找到它的右子树的最左边节点x：

在此处输入图像描述

假设：假设最坏情况的运行时间TREE-SUCCESSOR()为 O(h)，其中 h 是二叉搜索树的高度，并且在方法的连续调用之间树不会改变。最坏的情况发生在下一个后继节点是深度为 h 的叶子节点时。

您需要调用一次方法来获得下一个继任者，并且需要O(h)时间。一旦你有了下一个后继者，你可以简单地存储它，并且对于每个其他调用，你可以将它返回到O(1). 由于您还有k−1剩余通话，因此运行时间为O(k)。结合上面的，你有总运行时间是O(h)+O(k)=O(k+h)。

问题：我不确定最后一个关于我们如何获得运行时间 O(k) 的陈述吗？我假设 k 连续调用TREE-SUCCESSOR()意味着我们在可能相同或不同的节点上调用它 k 次？如果是这样，我们知道最坏的时间TREE-SUCCESSOR 是O(h)，那么我们是如何得到的总时间O(h+k)呢？我可以看到，如果我们调用TREE-SUCCESSOR() k时间，那么我们应该得到最坏的情况O(kh)。

编辑：我可能会假设ksuccissive 调用TREE-SUCCESSOR()意味着：TREE-SUCCESSOR()+⋯+TREE-SUCCESSOR(): k times？

标签： algorithmtime-complexitybinary-treetraversal

解决方案

众所周知，使用这种方法按顺序遍历二叉树需要 O(n) 时间。您的问题是证明二叉树的部分遍历的等效语句。

您必须证明的语句的较弱版本是每个连续调用的摊销成本为 O(1)。我将使用潜在方法证明该陈述。类似的方法可用于您需要的证明：

为了证明 k 次连续调用需要 O(k+h) 时间，我们找到一个在当前节点上运行的“银行函数” B，并证明：

  1. y = TREE-SUCCESSOR(x)所需的时间在O(1 + B(y) - B(x))中；和
  2. 0 <= B(x) <= h对于所有 x

从 (1) 可以得出，在k次连续调用使得y = TREE-SUCCESSOR k (x)之后，总时间在O(k + B(y)-B(x))中，并且从(2) 得出B(y)-B(x)在O(h)中，所以这证明时间在O(k + h)

有效的银行函数是B(x) = (h + d L (x) - d R (x))/2，其中d L是从根到 x 的路径上的左子链接数，d R是从根到 x 的路径上的右子链接数。

考虑TREE-SUCCESOR(x)中无界工作的情况：

  1. 当 x 有一个右孩子时，额外的工作与TREE-MINIMUM中添加的左孩子链接的数量成正比。这就是d L的变化。右子链接的数量仅增加 1，因此额外的工作与B的变化成正比。
  2. 当 x 没有右孩子时，额外的工作与我们通过遍历父节点删除的右孩子链接的数量成正比。这就是d R的减少。左子链接的数量仅变化 1，因此额外的工作再次与B的变化成正比。

这是仅有的两种情况，在这两种情况下，我们的总工作量都是O(1 + B(y) - B(x))。条件 1 为真。从B的定义来看，条件 2 也是微不足道的，因此该陈述得到证明。

推荐阅读