证明对 TREE-SUCCESSOR 的 k 次连续调用需要 O(k + h) 时间
Prove that k successive calls to TREE-SUCCESSOR take O(k + h) time
这个问题已经存在一段时间了，但我还有一个问题请教。我将讨论以下解决方案。
问题：证明无论我们在高度为h的二叉搜索树中的哪个节点开始，都会k连续调用TREE-SUCCESSOR花 O(k + h) 时间。
给定下面的树后继算法，给定一个 x，它将找到它是 x 右子树的最左节点：
Assumptions：假设TREE-SUCCESSOR()的最坏情况运行时间为O(h)，其中h为二叉搜索树的高度并且树不会在方法的连续调用之间改变。最坏的情况发生在下一个后继者是深度为 h 的叶子时。
您需要调用一次该方法以获得下一个继任者，并且您需要 O(h) 时间。一旦你有了下一个继任者，你就可以简单地存储它，对于其他每个调用，你可以 return 它在 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).
的最坏情况
编辑：我可能假设 k 对 TREE-SUCCESSOR() 的连续调用意味着：TREE-SUCCESSOR()+⋯+TREE-SUCCESSOR(): k times?
众所周知，使用此方法 in-order 遍历二叉树需要 O(n) 时间。您的问题是证明二叉树的部分遍历的等效语句。
您必须证明的陈述的较弱版本是每个连续调用的 摊销 成本是 O(1)。我会使用 potential method 证明 that 语句。您需要的证明可以使用类似的方法：
为了证明 k 次连续调用需要 O(k+h) 时间，我们找到一个在当前节点上运行的“bank 函数”B，并证明：
- y = TREE-SUCCESSOR(x) 所需的时间在 O(1 + B(y) - B(x)) ;和
- 0 <= B(x) <= h 所有 x
从 (1) 可以看出，在 k 次连续调用后 y = TREE-SUCCESSORk(x)，总时间在O(k + B(y)-B(x))，从(2)可以得出B(y)-B(x)在O(h)，所以这证明时间在O(k + h)
有效的银行函数是B(x) = (h + dL(x) - dR(x))/2，其中 dL 是路径上的 left-child 个链接数从根到x，dR是从根到x的路径上right-child个链接数
考虑 non-bounded 在 TREE-SUCCESOR(x):
中工作的情况
- 当 x 拥有权限 child 时，额外的工作量与 TREE-MINIMUM 中添加的 left-child 链接数成正比。即dL的变化。 right-child 链接的数量只增加了 1，因此额外的工作量与 B.
的变化成正比
- 当 x 没有权限 child 时，额外的工作量与我们通过遍历到 parent 删除的 right-child 个链接的数量成正比。即dR的减少。 left-child 链接的数量仅变化 1，因此额外的工作再次与 B.
的变化成正比
只有这两种情况，在这两种情况下我们的总工作量为 O(1 + B(y) - B(x))。条件 1 为真。根据 B 的定义，条件 2 也同样成立，因此命题得到证明。
这个问题已经存在一段时间了，但我还有一个问题请教。我将讨论以下解决方案。
问题：证明无论我们在高度为h的二叉搜索树中的哪个节点开始，都会k连续调用TREE-SUCCESSOR花 O(k + h) 时间。
给定下面的树后继算法，给定一个 x，它将找到它是 x 右子树的最左节点：
Assumptions：假设TREE-SUCCESSOR()的最坏情况运行时间为O(h)，其中h为二叉搜索树的高度并且树不会在方法的连续调用之间改变。最坏的情况发生在下一个后继者是深度为 h 的叶子时。
您需要调用一次该方法以获得下一个继任者，并且您需要 O(h) 时间。一旦你有了下一个继任者，你就可以简单地存储它，对于其他每个调用，你可以 return 它在 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).
编辑：我可能假设 k 对 TREE-SUCCESSOR() 的连续调用意味着：TREE-SUCCESSOR()+⋯+TREE-SUCCESSOR(): k times?
众所周知，使用此方法 in-order 遍历二叉树需要 O(n) 时间。您的问题是证明二叉树的部分遍历的等效语句。
您必须证明的陈述的较弱版本是每个连续调用的 摊销 成本是 O(1)。我会使用 potential method 证明 that 语句。您需要的证明可以使用类似的方法：
为了证明 k 次连续调用需要 O(k+h) 时间，我们找到一个在当前节点上运行的“bank 函数”B，并证明：
- y = TREE-SUCCESSOR(x) 所需的时间在 O(1 + B(y) - B(x)) ;和
- 0 <= B(x) <= h 所有 x
从 (1) 可以看出，在 k 次连续调用后 y = TREE-SUCCESSORk(x)，总时间在O(k + B(y)-B(x))，从(2)可以得出B(y)-B(x)在O(h)，所以这证明时间在O(k + h)
有效的银行函数是B(x) = (h + dL(x) - dR(x))/2，其中 dL 是路径上的 left-child 个链接数从根到x，dR是从根到x的路径上right-child个链接数
考虑 non-bounded 在 TREE-SUCCESOR(x):
中工作的情况- 当 x 拥有权限 child 时，额外的工作量与 TREE-MINIMUM 中添加的 left-child 链接数成正比。即dL的变化。 right-child 链接的数量只增加了 1，因此额外的工作量与 B. 的变化成正比
- 当 x 没有权限 child 时，额外的工作量与我们通过遍历到 parent 删除的 right-child 个链接的数量成正比。即dR的减少。 left-child 链接的数量仅变化 1，因此额外的工作再次与 B. 的变化成正比
只有这两种情况，在这两种情况下我们的总工作量为 O(1 + B(y) - B(x))。条件 1 为真。根据 B 的定义，条件 2 也同样成立，因此命题得到证明。