给定高度为h的二叉搜索树 (BST) ,从任意节点开始,连续应用BST InOrder Successor 算法k次需要O(k+h)时间,在由之前的通话。
伪代码:
get_kth_successor(node):
for times = 1 to k:
node = successor(node)
return node
Run Code Online (Sandbox Code Playgroud)
我如何证明这个时间复杂度?
特别是,我试图在k和访问的节点数之间建立关系,但在这里找不到任何模式。