BST时间复杂度

Question

假设T是具有n个节点和高度h的二叉查找树。T的每个节点x存储一个实数x。键。给出以下算法Func1（T. root）的最坏情况时间复杂度。你需要证明你的答案。

Func 1 (x) 
    if (x == NIL) return 0; 
    s1 <- Func1(x.left()); 

    if (s1 < 100) then
       s2 <- Func1(x.Right());
    end
    else
       s2 <- 0; 
    end

    s <- s1 + s2 + x.Key(); 
    return (s); 

x.left（）

对于最坏情况下的运行时，我认为这将是O（树的高度），因为这基本上类似于最小（）或最大（）二元搜索树算法。然而，它是递归的，所以我对是否将O（h）作为最坏的运行时编写有点犹豫。

当我考虑它时，最坏的情况是如果函数执行if（s1

Answer 1

您说得对，此函数的最坏情况运行时是θ（n），如果if语句始终执行，则会发生这种情况。在这种情况下，递归访问每个节点，递归访问完整的右子树，然后递归访问完整的左子树。（它也为每个节点做O（1）工作，这就是为什么它的总和为O（n））。