小编Gam*_*ess的帖子

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

给定高度为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和访问的节点数之间建立关系,但在这里找不到任何模式。

algorithm binary-search-tree

5
推荐指数
1
解决办法
5250
查看次数

标签 统计

algorithm ×1

binary-search-tree ×1