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

Question

我需要 CLRS 算法书中的提示来进行此练习:

Prove that no matter what node we start at in a height-h binary search tree, k successive calls to Tree-Successor take O(k+h) time.

Answer 1

• 令 x 为起始节点，z 为 k 次连续调用 TREE-SUCCESSOR 后的结束节点。
• 令 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)。