在 BST 中寻找 k 个后继者的时间复杂度

Question

给定高度为h的二叉搜索树 (BST) ，从任意节点开始，连续应用BST InOrder Successor 算法k次需要O(k+h)时间，在由之前的通话。

伪代码：

get_kth_successor(node):
    for times = 1 to k:
        node = successor(node)
    return node

我如何证明这个时间复杂度？

特别是，我试图在k和访问的节点数之间建立关系，但在这里找不到任何模式。

Answer 1

请了解以下有关后继遍历的事实：

1. 您可以遍历分支不超过两次：向下和向上。

2. 分支的每次两次访问都对应于找到至少一个后继者：当您通过分支向上回溯时，您将比第一次通过同一分支时向下访问至少一个后继者。

3. 仅遍历一次的分支数量不能超过2h。当您从树的左下角的叶子开始并且必须一直向上到根（后继），然后再次向下到底部叶子以找到根的后继时，就会发生这种最坏的情况。但是，如果此后您需要更多后继者，则必须再次访问其中一些分支（回溯），然后才能第一次遍历其他分支。因此，仅遍历一次的分支总数不能增加超过2h。

因此，要找到k 个后继，您最多需要遍历k 个分支两次（向下和向上，参见点 2）和2h 个分支一次（点 3），这可以归结为最坏情况的分支遍历计数为2k+2h这是O(h+k)。