首页 > 试题广场 >

证明：在一棵高度为h的二叉搜索树中，不论从哪个节点开始，k次

[问答题]
证明：在一棵高度为h的二叉搜索树中，不论从哪个节点开始，k次连续的TREE-SUCCESSOR调用所需时间为O(k+h)。 
TREE-MINIMUM(x)
while x.leftNIL
        x=x.left
return x
TREE-SUCCESSOR(x)
if x.rightNIL
   return TREE-MINIMUM(x.right)
y = x.p
while yNIL and x==y.right
        x=y
        y=y.p
return y
查看答案及解析
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小
难度：
0条回答 420浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号