performance - BST算法中给定范围内节点计数的运行时间

Question

我得到了以下算法的伪代码，其中 r 是 BST 的根，x,y 是 x<y 的数字。

TreeCount(r,x,y)

if r=null:

    return 0

if r<x:

    return TreeCount(r.right,x,y)

if r>y:

    return TreeCount(r.left,x,y)

return 1+TreeCount(r.right,x,y)+TreeCount(r.left,x,y)

我在很多地方看到该算法的时间复杂度为 O(h+k)，其中 k 是具有 [x,y] 值的节点数，但我不明白如何证明这一点。欢迎任何帮助。

标签： performancetime