证明二叉树中重复调用 successor() 的效率？

Question

我需要 CLRS 算法书中关于此练习的提示：

证明无论我们从高度为 h 的二叉搜索树中的哪个节点开始，k 次连续调用 Tree-Successor 都会花费 O(k+h) 时间.

Answer 1

• 连续调用 TREE-SUCCESSOR 后，设 x 为起始节点，z 为结束节点。
• 令p 为x 和z 之间的简单路径（包含）。
• 令 y 为 p 访问的 x 和 z 的共同祖先。
• p的长度最多为2h，即O(h)。
• 令output 为其值在x.key 和z.key 之间的元素。
• 输出的大小为O(k)。
• 在执行k次连续调用TREE-SUCCESSOR时，
  访问 p 中的节点，
  除了节点 x、y 和 z 之外，
  如果访问p中节点的子树，那么它的所有元素都在output中。
• 所以运行时间是O(h+k)。

Answer 2

提示：举一个小例子，观察结果，尝试推断原因。

首先，需要考虑以下一些事项。

从某个节点开始，连续 k 次调用 Tree-Succcesor 构成部分树遍历。这次步行访问了多少个（至少和最多）节点？ （提示：考虑 key(x)）。请记住，一条边最多被访问两次（为什么？）。

最后提示：结果是O(2h+k)。