BST時間複雑度

Question

Tがn個のノードと高さhを持つ2分探索木であると仮定します。 Tの各ノードxは 実数x.Keyを格納する。以下のアルゴリズム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（）& x.right（）の戻り左と右の子ノードのX x.key（）、最悪の場合の実行時間のためにノードX

に格納されたキーを返しますこれは基本的に最小（）または最大（）バイナリ検索ツリーアルゴリズムのように動作するので、これはO（ツリーの高さ）になると考えていました。しかし、再帰的なので、最悪の場合の実行時間としてO（h）を実際に書くのは少し躊躇しています。

私はそれについて考えてみると、関数が各x.leftに対してif（s1 < 100）文を実行すると、最悪の場合があります。これは、すべてのノードが訪問されたことを意味します。 （n）？

Answer 1

この関数のワーストケースランタイムがΘ（n）であることは間違いありません。これはif文が常に実行される場合に発生します。その場合、再帰は各ノードを訪問し、再帰的に完全な右のサブツリーにアクセスし、その後、完全に左のサブツリーを再帰的に訪問する。 （ノードごとにO（1）も働くので、これがO（n）まで要約されます）。