algorithm - k 连续调用 bst 中的树后继

Question

证明对树后继的 K 次连续调用需要 O(k+h) 时间。由于每个节点最多被访问两次，因此访问的节点数的最大界限必须是 2k。时间复杂度必须为 O(k)。我不知道 O(h) 的因素在哪里。是不是因为节点被访问但不是后继节点。我无法完全解释自己 O(h) 因素是如何参与整个过程的

PS：我知道这个问题已经存在，但我无法理解解决方案。

Answer 1

符号中的加O(k+h)号是另一种书写形式O(MAX(k, h))。

寻找继任者可能需要很O(h)长时间。要了解为什么会这样，请考虑一种情况，即您正在寻找根的左子树最右边节点的后继节点：它的后继节点位于右子树的底部，因此您必须遍历树的高度两次. 这就是为什么您需要h在计算中包括：如果k与 相比较小h，h则将主导算法的时间。

练习的目的是证明k连续调用后继次数的时间不是 O(k*h)，观察到单个调用可能占用最多 时可以想象O(h)。您通过显示遍历树的高度的成本在调用之间分布来证明这一点k，正如您通过注意到每个节点最多被访问两次所做的那样。